Document Open Access Logo

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors Valentin Bartier, Nicolas Bousquet , Clément Dallard , Kyle Lomer, Amer E. Mouawad

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.44.pdf
  • Filesize: 0.69 MB
  • 17 pages

Document Identifiers

Author Details

Valentin Bartier
  • Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, France
Nicolas Bousquet
  • CNRS, LIRIS, Université de Lyon, Université Claude Bernard Lyon 1, France
Clément Dallard
  • FAMNIT, University of Primorska, Koper, Slovenia
Kyle Lomer
  • Department of Computer Science, American University of Beirut, Lebanon
Amer E. Mouawad
  • Department of Computer Science, American University of Beirut, Lebanon

Funding

  • Bartier, Valentin: This work is supported by ANR project GrR (ANR-18-CE40-0032).
  • Bousquet, Nicolas: This work is supported by ANR project GrR (ANR-18-CE40-0032).
  • Dallard, Clément: This work is supported in part by the Slovenian Research Agency (N1-0102).
  • Mouawad, Amer E.: This work is supported by URB project "A theory of change through the lens of reconfiguration"

Acknowledgements

The authors would like to thank the anonymous reviewer for his/her insightful comments that allowed us to improve Lemma 2 and Theorem 4.

Cite As Get BibTex

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. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.44

Abstract

In the Token Jumping problem we are given a graph G = (V,E) and two independent sets S and T of G, each of size k ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that for every i, |S_i| = k, S_i is an independent set, S = S_0, S_𝓁 = T, and |S_i Δ S_i+1| = 2. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C_4-free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on {C_3,C_4}-free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p ≥ 4, both problems are W[1]-hard on {C_4, ..., C_p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Combinatoric problems
Keywords
  • Combinatorial reconfiguration
  • Independent Set
  • Token Jumping
  • Token Sliding
  • Parameterized Complexity

Metrics

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

Related Versions

References

  1. 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. CoRR, abs/2007.01673, 2020. URL: http://arxiv.org/abs/2007.01673.
  2. 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.
  3. Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. CoRR, abs/1605.00442, 2016. URL: http://arxiv.org/abs/1605.00442.
  4. Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized complexity of independent set in H-free graphs. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, volume 115 of LIPIcs, pages 17:1-17:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.17.
  5. 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
  6. Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token jumping in minor-closed classes. In Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, pages 136-149, 2017. URL: https://doi.org/10.1007/978-3-662-55751-8_12.
  7. 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
  8. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(56):913-919, 2008. Google Scholar
  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. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Polynomial-time algorithm for sliding tokens on trees. In Algorithms and computation, volume 8889 of Lecture Notes in Comput. Sci., pages 389-400. Springer, Cham, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_31.
  11. 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
  12. 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.
  13. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou. The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM Journal on Computing, 38(6):2330-2355, 2009. Google Scholar
  14. 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.
  15. 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. Theoretical Computer Science, 412(12-14):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
  16. Takehiro Ito, Marcin Kamiński, and Erik D. Demaine. Reconfiguration of list edge-colorings in a graph. Discrete Applied Mathematics, 160(15):2199-2207, 2012. Google Scholar
  17. Takehiro Ito, Marcin Kamiński, and Hirotaka Ono. Fixed-parameter tractability of token jumping on planar graphs. In Algorithms and computation, volume 8889 of Lecture Notes in Comput. Sci., pages 208-219. Springer, Cham, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_17.
  18. 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
  19. Takehiro Ito, Hiroyuki Nooka, and Xiao Zhou. Reconfiguration of vertex covers in a graph. IEICE Transactions, 99-D(3):598-606, 2016. URL: http://search.ieice.org/bin/summary.php?id=e99-d_3_598.
  20. Wm. Woolsey Johnson and William E. Story. Notes on the "15" puzzle. American Journal of Mathematics, 2(4):397-404, 1879. Google Scholar
  21. Marcin Kaminski, Paul Medvedev, and Martin Milanic. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9-15, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.004.
  22. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. Google Scholar
  23. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, pages 13-34, 2008. Google Scholar
  24. Jeong Han Kim. The Ramsey number R(3,t) has order of magnitude t²/log t. Random Structures Algorithms, 7(3):173-207, 1995. URL: https://doi.org/10.1002/rsa.3240070302.
  25. 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.
  26. Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. In Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, pages 506-517, 2015. Google Scholar
  27. 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.
  28. Amer E. Mouawad, Naomi Nishimura, Vinayak Pathak, and Venkatesh Raman. Shortest reconfiguration paths in the solution space of boolean formulas. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 985-996, 2015. Google Scholar
  29. Amer E. Mouawad, Naomi Nishimura, and Venkatesh Raman. Vertex cover reconfiguration and beyond. In Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, pages 452-463, 2014. Google Scholar
  30. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  31. Jan van den Heuvel. The complexity of change. Surveys in Combinatorics 2013, 409:127-160, 2013. Google Scholar
  32. Marcin Wrochna. Reconfiguration in bounded bandwidth and treedepth. CoRR, abs/1405.0847, 2014. URL: http://arxiv.org/abs/1405.0847.
  33. 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
  34. 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