Document Open Access Logo

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

Authors Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.41.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Yoichi Iwata
Tomoaki Ogasawara
Naoto Ohsaka

Cite As Get BibTex

Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.41

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, the concept of "FPT inside P" has been introduced.
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'} time for a parameter k and a constant c'<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(td m) time or O(td (m+nlog n)) time, where td is the tree-depth of the input graph.
Because any graph of tree-width tw has tree-depth at most (tw+1)log_2 n, our algorithms also run in O(tw mlog n) time or O(tw (m+nlog n)log n) 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. (SODA 2017).

Subject Classification

Keywords
  • Fully Polynomial FPT Algorithm
  • Tree-Depth
  • Divide-and-Conquer

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In SODA, pages 1681-1697, 2015. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In SODA, pages 377-391, 2016. Google Scholar
  3. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In SIGMOD, pages 349-360, 2013. Google Scholar
  4. Takuya Akiba, Christian Sommer, and Ken-ichi Kawarabayashi. Shortest-path queries for complex networks: exploiting low tree-width outside the core. In EDBT, pages 144-155, 2012. Google Scholar
  5. Norbert Blum. A new approach to maximum matching in general graphs. In ICALP, pages 586-597, 1990. Google Scholar
  6. Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, and Zsolt Tuza. Rankings of Graphs. SIAM J. Discrete Math., 11(1):168-181, 1998. Google Scholar
  7. Shiva Chaudhuri and Christos D. Zaroliagis. Shortest paths in digraphs of small treewidth. part I: sequential algorithms. Algorithmica, 27(3):212-226, 2000. Google Scholar
  8. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and Distance Queries via 2-Hop Labels. SIAM J. Comput., 32(5):1338-1355, 2003. Google Scholar
  9. David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. CoRR, abs/1707.05016, 2017. URL: http://arxiv.org/abs/1707.05016.
  10. Jack Edmonds. Paths, trees, and flowers. Canad. J. Math., 17(3):449-467, 1965. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In SODA, pages 1419-1432, 2017. Google Scholar
  12. Harold N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In SODA, pages 434-443, 1990. Google Scholar
  13. Harold N. Gabow. Data Structures for Weighted Matching and Extensions to b-matching and f-factors. CoRR, abs/1611.07541, 2016. URL: http://arxiv.org/abs/1611.07541.
  14. Harold N. Gabow and Robert Endre Tarjan. A Linear-Time Algorithm for a Special Case of Disjoint Set Union. J. Comput. Syst. Sci., 30(2):209-221, 1985. Google Scholar
  15. Harold N. Gabow and Robert Endre Tarjan. Faster Scaling Algorithms for General Graph-Matching Problems. J. ACM, 38(4):815-853, 1991. Google Scholar
  16. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theor. Comput. Sci., 689:67-95, 2017. Google Scholar
  17. Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett., 109(7):352-355, 2009. Google Scholar
  18. John Hershberger, Subhash Suri, and Amit M. Bhosle. On the difficulty of some shortest path problems. ACM Trans. Algorithms, 3(1):5:1-5:15, 2007. Google Scholar
  19. David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM J. Comput., 22(6):1199-1217, 1993. Google Scholar
  20. Meir Katchalski, William McCuaig, and Suzanne M. Seager. Ordered colourings. Discrete Mathematics, 142(1-3):141-154, 1995. Google Scholar
  21. Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. Google Scholar
  22. Kavindra Malik, Ashok K. Mittal, and Santosh K. Gupta. The k most vital arcs in the shortest path problem. Oper. Res. Lett., 8(4):223-227, 1989. Google Scholar
  23. George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The power of data reduction for matching. CoRR, abs/1609.08879, 2016. URL: http://arxiv.org/abs/1609.08879.
  24. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  25. Jaroslav Nešetřil and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. Google Scholar
  26. James B. Orlin and Antonio Sedeño-Noda. An O(nm) time algorithm for finding the min length directed cycle in a graph. In SODA, pages 1866-1879, 2017. Google Scholar
  27. Léon Planken, Mathijs de Weerdt, and Roman van der Krogt. Computing all-pairs shortest paths by leveraging low treewidth. J. Artif. Intell. Res., 43:353-388, 2012. Google Scholar
  28. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms, 8(4):33:1-33:11, 2012. Google Scholar
  29. Alejandro A. Schäffer. Optimal Node Ranking of Trees in Linear Time. Inf. Process. Lett., 33(2):91-96, 1989. Google Scholar
  30. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer, 2003. Google Scholar
  31. Vijay V. Vazirani. A theory of alternating paths and blossoms for proving correctness of the O(√V E) general graph maximum matching algorithm. Combinatorica, 14(1):71-109, 1994. Google Scholar
  32. Fang Wei. TEDI: efficient shortest path query answering on graphs. In SIGMOD, pages 99-110, 2010. Google Scholar
  33. Virginia Vassilevska Williams and Ryan Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In FOCS, pages 645-654, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact