On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

DOI10.4230/LIPICS.STACS.2018.41zbMATH Open1487.68130arXiv1710.04376OpenAlexW2963360194MaRDI QIDQ3304140

Author name not available (Why is that?)

Publication date: 5 August 2020

Abstract: There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, Fomin et al. (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity $O(n^c)$, the goal is to design an algorithm running in $k^{O(1)}{n}^{c^{\prime }}$ time for a parameter $k$ and a constant $c^{\prime }<c$. In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in $O(mathrmtdcdotm)$ time or $O(mathrmtdcdot(m+nlogn))$ time, where $mathrmtd$ is the tree-depth of the input graph. Because any graph of tree-width $mathrmtw$ has tree-depth at most $(mathrmtw+1)lo{g}_{2}n$, our algorithms also run in $O(mathrmtwcdotmlogn)$ time or $O(mathrmtwcdot(m+nlogn)logn)$ time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by Fomin et al.

Full work available at URL: https://arxiv.org/abs/1710.04376

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304140)