Document Open Access Logo

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Authors Hans L. Bodlaender , Carla Groenland , Hugo Jacob , Lars Jaffke , Paloma T. Lima

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2022.8.pdf
  • Filesize: 0.86 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • XNLP
  • linear clique-width
  • W-hierarchy
  • pathwidth
  • linear mim-width
  • bandwidth

Metrics

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

Abstract

In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. 
In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.

Cite As Get BibTex

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima. XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.8

Author Details

Hans L. Bodlaender
  • Utrecht University, The Netherlands
Carla Groenland
  • Utrecht University, The Netherlands
Hugo Jacob
  • ENS Paris-Saclay, France
Lars Jaffke
  • University of Bergen, Norway
Paloma T. Lima
  • IT University of Copenhagen, Denmark

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).
  • Jaffke, Lars: Supported by the Norwegian Research Council (project number 274526) and the Meltzer Research Fund.

References

  1. Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, and Eiji Miyano. Complexity of finding maximum regular induced subgraphs with prescribed degree. Theor. Comput. Sci., 550:21-35, 2014. URL: https://doi.org/10.1016/j.tcs.2014.07.008.
  2. Hans L. Bodlaender. Parameterized complexity of bandwidth of caterpillars and weighted path emulation. In Lukasz Kowalik, Michal Pilipczuk, and Pawel Rzazewski, editors, Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), volume 12911 of Lecture Notes in Computer Science, pages 15-27. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-86838-3_2.
  3. Hans L. Bodlaender, Gunther Cornelissen, and Marieke van der Wegen. Problems hard for treewidth but easy for stable gonality. In Michael A. Bekos and Michael Kaufmann, editors, Proceedings 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), volume 13453 of Lecture Notes in Computer Science, pages 84-97, 2022. URL: https://doi.org/10.1007/978-3-031-15914-5_7.
  4. 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.
  5. Hans L. Bodlaender, Daniel Lokshtanov, and Eelko Penninkx. Planar capacitated dominating set is W[1]-hard. In Jianer Chen and Fedor V. Fomin, editors, Proceedings 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009, volume 5917 of Lecture Notes in Computer Science, pages 50-60. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_4.
  6. Nick Brettell, Jake Horsfield, Andrea Munaro, and Daniël Paulusma. List k-colouring P_t-free graphs: A mim-width perspective. Inf. Process. Lett., 173:106168, 2022. URL: https://doi.org/10.1016/j.ipl.2021.106168.
  7. Hajo Broersma, Petr A. Golovach, and Viresh Patel. Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theor. Comput. Sci., 485:69-84, 2013. URL: https://doi.org/10.1016/j.tcs.2013.03.008.
  8. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.009.
  9. 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.
  10. Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated domination and covering: A parameterized perspective. In Martin Grohe and Rolf Niedermeier, editors, Proceedings 3rd International Workshop on Parameterized and Exact Computation, IWPEC 2008, volume 5018 of Lecture Notes in Computer Science, pages 78-90. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79723-4_9.
  11. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 1999. Google Scholar
  12. 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.
  13. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  14. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput., 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  15. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1-9:27, 2019. URL: https://doi.org/10.1145/3280824.
  16. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. Algorithmica, 82(9):2432-2473, 2020. URL: https://doi.org/10.1007/s00453-020-00692-9.
  17. Sylvain Guillemot. Parameterized complexity and approximability of the Longest Compatible Sequence problem. Discret. Optim., 8(1):50-60, 2011. URL: https://doi.org/10.1016/j.disopt.2010.08.003.
  18. Frank Gurski and Egon Wanke. Line graphs of bounded clique-width. Discret. Math., 307(22):2734-2754, 2007. URL: https://doi.org/10.1016/j.disc.2007.01.020.
  19. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width II. The feedback vertex set problem. Algorithmica, 82:118-145, 2020. Google Scholar
  20. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  21. Luke Mathieson and Stefan Szeider. The parameterized complexity of regular subgraph problems and generalizations. In James Harland and Prabhu Manyem, editors, Proceedings 14th Computing: The Australasian Theory Symposium, CATS 2008, volume 77 of CRPIT, pages 79-86. Australian Computer Society, 2008. URL: http://crpit.scem.westernsydney.edu.au/abstracts/CRPITV77Mathieson.html.
  22. Hannes Moser and Dimitrios M. Thilikos. Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms, 7(2):181-190, 2009. URL: https://doi.org/10.1016/j.jda.2008.09.005.
  23. Michal Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory, 9(4):18:1-18:36, 2018. URL: https://doi.org/10.1145/3154856.
  24. Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, Norway, 2012. Google Scholar
  25. Egon Wanke. k-NLC graphs and polynomial algorithms. Discret. Appl. Math., 54(2-3):251-266, 1994. URL: https://doi.org/10.1016/0166-218X(94)90026-4.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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