Document Open Access Logo

Galactic Token Sliding

Authors Valentin Bartier, Nicolas Bousquet , Amer E. Mouawad

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.15.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Valentin Bartier
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Nicolas Bousquet
  • Univ Lyon, CNRS, UCBL, INSA Lyon, LIRIS, UMR5205, France
Amer E. Mouawad
  • American University of Beirut, Lebanon
  • University of Bremen, Germany

Funding

This work is supported by PHC Cedre project 2022 "PLR".
  • Bartier, Valentin: Supported by ANR project GrR (ANR-18-CE40-0032).
  • Bousquet, Nicolas: Supported by ANR project GrR (ANR-18-CE40-0032).
  • Mouawad, Amer E.: Research supported by the Alexander von Humboldt Foundation and partially supported by URB project "A theory of change through the lens of reconfiguration".

Cite As Get BibTex

Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic Token Sliding. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.15

Abstract

Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets (each of size k) I_s = I₀, I₁, I₂, …, I_𝓁 = I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. In the Token Jumping variant of the problem, a single step allows a token to jump from one vertex to any other vertex in the graph. In the Token Sliding variant, a token is only allowed to slide from a vertex to one of its neighbors. Like the Independent Set problem, both of the aforementioned problems are known to be W[1]-hard on general graphs (for parameter k). A very fruitful line of research [Bodlaender, 1988; Grohe et al., 2017; Telle and Villanger, 2019; Pilipczuk and Siebertz, 2021] has showed that the Independent Set problem becomes fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, nowhere-dense, and all the way to biclique-free graphs. Over a series of papers, the same was shown to hold for the Token Jumping problem [Ito et al., 2014; Lokshtanov et al., 2018; Siebertz, 2018; Bousquet et al., 2017]. As for the Token Sliding problem, which is mentioned in most of these papers, almost nothing is known beyond the fact that the problem is polynomial-time solvable on trees [Demaine et al., 2015] and interval graphs [Marthe Bonamy and Nicolas Bousquet, 2017]. We remedy this situation by introducing a new model for the reconfiguration of independent sets, which we call galactic reconfiguration. Using this new model, we show that (standard) Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. We believe that the galactic reconfiguration model is of independent interest and could potentially help in resolving the remaining open questions concerning the (parameterized) complexity of Token Sliding.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → W hierarchy
Keywords
  • reconfiguration
  • independent set
  • galactic reconfiguration
  • sparse graphs
  • token sliding
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula. Refuting FPT algorithms for some parameterized problems under gap-eth. In Petr A. Golovach and Meirav Zehavi, editors, 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 2:1-2:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.2.
  2. Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping. Algorithmica, 83(9):2914-2951, 2021. URL: https://doi.org/10.1007/s00453-021-00848-1.
  3. Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic token sliding. CoRR, abs/2204.05549, 2022. URL: https://doi.org/10.48550/arXiv.2204.05549.
  4. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token sliding on split graphs. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 13:1-13:17, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.13.
  5. Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth. In G. Goos, J. Hartmanis, D. Barstow, W. Brauer, P. Brinch Hansen, D. Gries, D. Luckham, C. Moler, A. Pnueli, G. Seegmüller, J. Stoer, N. Wirth, Timo Lepistö, and Arto Salomaa, editors, Automata, Languages and Programming, volume 317, pages 105-118. Springer Berlin Heidelberg, Berlin, Heidelberg, 1988. Series Title: Lecture Notes in Computer Science. URL: https://doi.org/10.1007/3-540-19488-6_110.
  6. Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, volume 10520 of Lecture Notes in Computer Science, pages 127-139. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-68705-6_10.
  7. Paul S. Bonsma, Marcin Kaminski, and Marcin Wrochna. Reconfiguring independent sets in claw-free graphs. In Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, pages 86-97, 2014. Google Scholar
  8. Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token Jumping in Minor-Closed Classes. In Ralf Klasing and Marc Zeitoun, editors, Fundamentals of Computation Theory, volume 10472, pages 136-149. Springer Berlin Heidelberg, Berlin, Heidelberg, 2017. Series Title: Lecture Notes in Computer Science. URL: https://doi.org/10.1007/978-3-662-55751-8_12.
  9. Richard C. Brewster, Sean McGuinness, Benjamin Moore, and Jonathan A. Noel. A dichotomy theorem for circular colouring reconfiguration. Theor. Comput. Sci., 639:1-13, 2016. Google Scholar
  10. 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.
  11. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Linear-time algorithm for sliding tokens on trees. Theoretical Computer Science, 600:132-142, October 2015. URL: https://doi.org/10.1016/j.tcs.2015.07.037.
  12. Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, and Ryuhei Uehara. Sliding token on bipartite permutation graphs. In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 237-247, 2015. Google Scholar
  13. Sevag Gharibian and Jamie Sikora. Ground state connectivity of local hamiltonians. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 617-628, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_50.
  14. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. Journal of the ACM, 64(3):1-32, June 2017. URL: https://doi.org/10.1145/3051095.
  15. 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.
  16. Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. On the parameterized complexity for token jumping on graphs. In Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings, pages 341-351, 2014. Google Scholar
  17. Takehiro Ito, Marcin Kamiński, and Hirotaka Ono. Fixed-Parameter Tractability of Token Jumping on Planar Graphs. In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation, volume 8889, pages 208-219. Springer International Publishing, Cham, 2014. Series Title: Lecture Notes in Computer Science. URL: https://doi.org/10.1007/978-3-319-13075-0_17.
  18. Takehiro Ito, Marcin Kamiński, and Hirotaka Ono. Fixed-parameter tractability of token jumping on planar graphs. In Algorithms and Computation, Lecture Notes in Computer Science, pages 208-219. Springer International Publishing, 2014. Google Scholar
  19. Takehiro Ito, Hiroyuki Nooka, and Xiao Zhou. Reconfiguration of vertex covers in a graph. IEICE Transactions, 99-D(3):598-606, 2016. Google Scholar
  20. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. Google Scholar
  21. 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.
  22. Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.S. Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. Journal of Computer and System Sciences, 95:122-131, August 2018. URL: https://doi.org/10.1016/j.jcss.2018.02.004.
  23. Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Comput. Geom., 49:17-23, 2015. URL: https://doi.org/10.1016/j.comgeo.2014.11.001.
  24. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  25. Michał Pilipczuk and Sebastian Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. European Journal of Combinatorics, 94:103309, May 2021. URL: https://doi.org/10.1016/j.ejc.2021.103309.
  26. Sebastian Siebertz. Reconfiguration on Nowhere Dense Graph Classes. The Electronic Journal of Combinatorics, 25(3):P3.24, August 2018. URL: https://doi.org/10.37236/7458.
  27. J.A. Telle and Y. Villanger. FPT algorithms for domination in sparse graphs and beyond. Theoretical Computer Science, 770:62-68, May 2019. URL: https://doi.org/10.1016/j.tcs.2018.10.030.
  28. Jan van den Heuvel. The complexity of change. Surveys in Combinatorics 2013, 409:127-160, 2013. Google Scholar
  29. Marcin Wrochna. Reconfiguration in bounded bandwidth and treedepth. CoRR, 2014. URL: http://arxiv.org/abs/1405.0847.
  30. Marcin Wrochna. Homomorphism reconfiguration via homotopy. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 730-742, 2015. Google Scholar
  31. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
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