Document Open Access Logo

Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited

Authors Tatsuya Gima , Takehiro Ito , Yasuaki Kobayashi , Yota Otachi

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.61.pdf
  • Filesize: 0.86 MB
  • 15 pages

Document Identifiers

Author Details

Tatsuya Gima
  • Nagoya University, Japan
Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yasuaki Kobayashi
  • Hokkaido University, Sapporo, Japan
Yota Otachi
  • Nagoya University, Japan

Funding

  • Ito, Takehiro: JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814, JP20H05793
  • Kobayashi, Yasuaki: JSPS KAKENHI Grant Numbers JP20H05793, JP20H00595, JP20K19742
  • Otachi, Yota: JSPS KAKENHI Grant Numbers JP18H04091, JP20H05793, JP21K11752, JP22H00513

Cite As Get BibTex

Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi. Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.61

Abstract

Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting, Mouawad et al. [IPEC 2014] presented an algorithmic meta-theorem for reconfiguration problems that says if the feasibility can be expressed in monadic second-order logic (MSO), then the problem is fixed-parameter tractable parameterized by treewidth + 𝓁, where 𝓁 is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna [J. Comput. Syst. Sci. 2018] that if 𝓁 is not part of the parameter, then the problem is PSPACE-complete even on graphs of bounded bandwidth.
In this paper, we present the first algorithmic meta-theorems for the case where 𝓁 is not part of the parameter, using some structural graph parameters incomparable with bandwidth. We show that if the feasibility is defined in MSO, then the reconfiguration problem under the so-called token jumping rule is fixed-parameter tractable parameterized by neighborhood diversity. We also show that the problem is fixed-parameter tractable parameterized by treedepth + k, where k is the size of sets being transformed. We finally complement the positive result for treedepth by showing that the problem is PSPACE-complete on forests of depth 3.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Combinatorial reconfiguration
  • monadic second-order logic
  • fixed-parameter tractability
  • treedepth
  • neighborhood diversity

Metrics

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

Related Versions

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308-340, 1991. URL: https://doi.org/10.1016/0196-6774(91)90006-K.
  2. Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, and Yota Otachi. Independent set reconfiguration parameterized by modular-width. Algorithmica, 82(9):2586-2605, 2020. URL: https://doi.org/10.1007/s00453-020-00700-y.
  3. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token sliding on split graphs. Theory Comput. Syst., 65(4):662-686, 2021. URL: https://doi.org/10.1007/s00224-020-09967-8.
  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 FOCS 2021, pages 193-204. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00027.
  5. Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized complexities of dominating and independent set reconfiguration. In IPEC 2021, volume 214 of LIPIcs, pages 9:1-9:16, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.9.
  6. Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7(5&6):555-581, 1992. URL: https://doi.org/10.1007/BF01758777.
  7. Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, and Andrew Winslow. Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect. Theor. Comput. Sci., 806:332-343, 2020. URL: https://doi.org/10.1016/j.tcs.2019.05.028.
  8. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  9. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  10. Bruno Courcelle. The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. RAIRO Theor. Informatics Appl., 26:257-286, 1992. URL: https://doi.org/10.1051/ita/1992260302571.
  11. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach. Cambridge University Press, 2012. URL: https://www.cambridge.org/knowledge/isbn/item5758776/.
  12. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  13. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  14. Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, and Yushi Uno. Reconfiguring undirected paths. In WADS 2019, volume 11646 of Lecture Notes in Computer Science, pages 353-365, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_26.
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  16. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  17. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci., 343(1-2):72-96, 2005. URL: https://doi.org/10.1016/j.tcs.2005.05.008.
  18. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
  19. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9-15, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.004.
  20. Dusan Knop, Martin Koutecký, Tomás Masarík, and Tomás Toufar. Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci., 15(4), 2019. URL: https://doi.org/10.23638/LMCS-15(4:12)2019.
  21. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. URL: https://doi.org/10.1007/s00453-011-9554-x.
  22. Michael Lampis. Model checking lower bounds for simple graphs. Log. Methods Comput. Sci., 10(1), 2014. URL: https://doi.org/10.2168/LMCS-10(1:18)2014.
  23. Michael Lampis and Valia Mitsou. Fine-grained meta-theorems for vertex integrity. In ISAAC 2021, volume 212 of LIPIcs, pages 34:1-34:15, 2021. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2021.34.
  24. Daniel Lokshtanov and Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms, 15(1):7:1-7:19, 2019. URL: https://doi.org/10.1145/3280825.
  25. Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. J. Comput. Syst. Sci., 95:122-131, 2018. URL: https://doi.org/10.1016/j.jcss.2018.02.004.
  26. Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. On the parameterized complexity of reconfiguration of connected dominating sets. Algorithmica, 84(2):482-509, 2022. URL: https://doi.org/10.1007/s00453-021-00909-5.
  27. Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discret. Math., 201(1-3):189-241, 1999. URL: https://doi.org/10.1016/S0012-365X(98)00319-7.
  28. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Sebastian Siebertz. Vertex cover reconfiguration and beyond. Algorithms, 11(2):20, 2018. URL: https://doi.org/10.3390/a11020020.
  29. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmica, 78(1):274-297, 2017. URL: https://doi.org/10.1007/s00453-016-0159-2.
  30. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Marcin Wrochna. Reconfiguration over tree decompositions. In IPEC 2014, volume 8894 of Lecture Notes in Computer Science, pages 246-257. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-13524-3_21.
  31. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. URL: https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001.
  32. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  33. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 931-942, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_77.
  34. Larry J. Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Department of Electrical Engineering, MIT, 1974. URL: http://hdl.handle.net/1721.1/15540.
  35. Akira Suzuki, Amer E. Mouawad, and Naomi Nishimura. Reconfiguration of dominating sets. J. Comb. Optim., 32(4):1182-1195, 2016. URL: https://doi.org/10.1007/s10878-015-9947-x.
  36. Éva Tardos. A strongly polynomial minimum cost circulation algorithm. Comb., 5(3):247-256, 1985. URL: https://doi.org/10.1007/BF02579369.
  37. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In ICALP 2008, volume 5125 of Lecture Notes in Computer Science, pages 634-645. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_52.
  38. Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: https://doi.org/10.1017/CBO9781139506748.005.
  39. Moshe Y. Vardi. The complexity of relational query languages. In STOC 1982, pages 137-146, 1982. URL: https://doi.org/10.1145/800070.802186.
  40. Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci., 93:1-10, 2018. URL: https://doi.org/10.1016/j.jcss.2017.11.003.
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