Document Open Access Logo

On the Complexity of Problems on Tree-Structured Graphs

Authors Hans L. Bodlaender , Carla Groenland , Hugo Jacob , Marcin Pilipczuk , Michał Pilipczuk

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2022.6.pdf
  • Filesize: 1.03 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Parameterized Complexity
  • Treewidth
  • XALP
  • XNLP

Metrics

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

Abstract

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)n^O(1) time and f(k)log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on "tree-structured graphs" are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. 
Besides finding a "natural home" for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)n^O(1) and use f(k)log n space. Moreover, we introduce "tree-shaped" variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.

Cite As Get BibTex

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.6

Author Details

Hans L. Bodlaender
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Carla Groenland
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Hugo Jacob
  • ENS Paris-Saclay, France
Marcin Pilipczuk
  • University of Warsaw, Poland
Michał Pilipczuk
  • University of Warsaw, Poland

Funding

  • Groenland, Carla: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180).
  • Pilipczuk, Marcin: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704.
  • Pilipczuk, Michał: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 948057.

Acknowledgements

We would like to thank the organizers of the workshop on Parameterized complexity and discrete optimization, organized at HIM in Bonn, for providing a productive research environment. We would also like to thank our referees for useful suggestions.

References

  1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Ann. Pure Appl. Log., 73:235-276, 1995. URL: https://doi.org/10.1016/0168-0072(94)00034-Z.
  2. Michael Alekhnovich and Alexander A. Razborov. Satisfiability, branch-width and tseitin tautologies. In Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS '02, pages 593-603, USA, 2002. IEEE Computer Society. Google Scholar
  3. Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang. Width-parametrized SAT: time-space tradeoffs. Theory of Computing, 10:297-339, 2014. URL: https://doi.org/10.4086/toc.2014.v010a012.
  4. Hans L. Bodlaender, Gunther Cornelissen, and Marieke van der Wegen. Problems hard for treewidth but easy for stable gonality. arXiv, abs/2202.06838, 2022. Extended abstract to appear in Proceedings WG 2022. URL: http://arxiv.org/abs/2202.06838.
  5. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List colouring trees in logarithmic space. arXiv, abs/2206.09750, 2022. URL: http://arxiv.org/abs/2206.09750.
  6. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the parameterized complexity of computing tree-partitions. arXiv, abs/2206.11832, 2022. URL: http://arxiv.org/abs/2206.11832.
  7. Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. XNLP-completeness for parameterized problems on graphs with a linear structure. arXiv, abs/2201.13119, 2022. URL: http://arxiv.org/abs/2201.13119.
  8. Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the complexity of problems on tree-structured graphs. CoRR, 2022. URL: https://doi.org/10.48550/arXiv.2206.11828.
  9. Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, and Céline M. F. Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. In Proceedings 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 193-204, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00027.
  10. Yijia Chen, Michael Elberfeld, and Moritz Müller. The parameterized space complexity of model-checking bounded variable first-order logic. Log. Methods Comput. Sci., 15(3), 2019. URL: https://doi.org/10.23638/LMCS-15(3:31)2019.
  11. Stephen A. Cook. The complexity of theorem-proving procedures. In Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman, editors, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, STOC 1971, pages 151-158. ACM, 1971. URL: https://doi.org/10.1145/800157.805047.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput., 24(4):873-921, 1995. URL: https://doi.org/10.1137/S0097539792228228.
  14. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1&2):109-131, 1995. URL: https://doi.org/10.1016/0304-3975(94)00097-3.
  15. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  16. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  17. Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. URL: https://doi.org/10.1007/s00453-014-9944-y.
  18. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. URL: https://doi.org/10.1016/j.ic.2010.11.026.
  19. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  20. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoretical Computer Science, 918:60-76, 2022. URL: https://doi.org/10.1016/j.tcs.2022.03.021.
  21. Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2):135-155, 1997. URL: https://doi.org/10.1016/S0166-218X(96)00085-6.
  22. Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of pebble games and complete problems. SIAM Journal on Computing, 8(4):574-586, 1979. URL: https://doi.org/10.1137/0208046.
  23. Michal Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Transactions on Computation Theory, 9(4):18:1-18:36, 2018. URL: https://doi.org/10.1145/3154856.
  24. Walter L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21(2):218-235, 1980. URL: https://doi.org/10.1016/0022-0000(80)90036-7.
  25. Stefan Szeider. Not so easy problems for tree decomposable graphs. In Advances in Discrete Mathematics and Applications: Mysore, 2008, volume 13 of Ramanujan Math. Soc. Lect. Notes Ser., pages 179-190. Ramanujan Math. Soc., Mysore, 2010. URL: http://arxiv.org/abs/1107.1177.
  26. H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43(2):380-404, 1991. URL: https://doi.org/10.1016/0022-0000(91)90020-6.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact