On the power of tree-depth for fully polynomial FPT algorithms

DOI10.4230/LIPICS.STACS.2018.41MaRDI QIDQ3304140zbMATH OpenOpenAlexFDO

Authors Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka

Publication date 5 August 2020

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

zbMATH Keywords

divide-and-conquerfully polynomial FPT algorithmtree-depth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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.

Recommendations

• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• scientific article; zbMATH DE number 6850484
• A faster parameterized algorithm for treedepth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

Cites work

• A linear-time algorithm for a special case of disjoint set union
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An O(nm) time algorithm for finding the min length directed cycle in a graph
• Applications of a Planar Separator Theorem
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing all-pairs shortest paths by leveraging low treewidth
• Faster scaling algorithms for general graph matching problems
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 177842 (Why is no real title available?)
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• On the difficulty of some shortest path problems
• Optimal node ranking of tree in linear time
• Ordered colourings
• Paths, Trees, and Flowers
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Rankings of Graphs
• Reachability and Distance Queries via 2-Hop Labels
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Sparsity. Graphs, structures, and algorithms
• Subcubic equivalences between graph centrality problems, APSP and diameter
• The k most vital arcs in the shortest path problem
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(19)

• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Optimal centrality computations within bounded clique-width graphs
• Maximum matching in almost linear time on graphs of bounded clique-width
• Eccentricity queries and beyond using hub labels
• The power of linear-time data reduction for maximum matching
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• The \(b\)-matching problem in distance-hereditary graphs and beyond
• On adaptive algorithms for maximum matching
• Data Reduction for Maximum Matching on Real-World Graphs
• Efficient parameterized algorithms for computing all-pairs shortest paths
• On parameterized complexity of binary networked public goods game
• On the size of minimal separators for treedepth decomposition
• Effective data reduction for strongly stable matching in very sparse graphs
• Closure property of contraction-depth of matroids
• Bounding width on graph classes of constant diameter

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)