Document Open Access Logo

Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes

Authors Mark de Berg, Bart M. P. Jansen, Debankur Mukherjee

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.34.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Mark de Berg
Bart M. P. Jansen
Debankur Mukherjee

Cite As Get BibTex

Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.34

Abstract

Traditionally, reconfiguration problems ask the question whether a given solution of an optimization problem can be transformed to a target solution in a sequence of small steps that preserve feasibility of the intermediate solutions. In this paper, rather than asking this question from an algorithmic perspective, we analyze the combinatorial structure behind it. We consider the problem of reconfiguring one independent set into another, using two different processes: (1) exchanging exactly k vertices in each step, or (2) removing or adding one vertex in each step while ensuring the intermediate sets contain at most k fewer vertices than the initial solution. We are interested in determining the minimum value of k for which this reconfiguration is possible, and bound these threshold values in terms of several structural graph parameters. For hereditary graph classes we identify structures that cause the reconfiguration threshold to be large.

Subject Classification

Keywords
  • Reconfiguration
  • Independent set
  • Token Addition Removal
  • Token Sliding

Metrics

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

References

  1. Aviv Adler, Mark de Berg, Dan Halperin, and Kiril Solovey. Efficient multi-robot motion planning for unlabeled discs in simple polygons. In Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics, pages 1-17, 2015. URL: http://dx.doi.org/10.1007/978-3-319-16595-0_1.
  2. B. V. Subramanya Bharadwaj and L. Sunil Chandran. Bounds on isoperimetric values of trees. Discrete Mathematics, 309(4):834-842, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.01.021.
  3. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2):1-45, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00228-4.
  4. Paul Bonsma. Independent set reconfiguration in cographs. In Graph-Theoretic Concepts in Computer Science: 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, pages 105-116, 2014. URL: http://dx.doi.org/10.1007/978-3-319-12340-0_9.
  5. Paul Bonsma, Marcin Kamiński, 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. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_8.
  6. Gruia Calinescu, Adrian Dumitrescu, and János Pach. Reconfigurations in graphs and grids. In LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings, pages 262-273, 2006. URL: http://dx.doi.org/10.1007/11682462_27.
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer Publishing Company, Incorporated, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  8. Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. Independent set reconfiguration thresholds of hereditary graph classes. arXiv:1610.03766, 2016. URL: http://arxiv.org/abs/1610.03766.
  9. 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, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.07.037.
  10. Reinhard Diestel. Graph theory. Springer-Verlag Berlin Heidelberg, 2010. Google Scholar
  11. G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, s3-2(1):69-81, 1952. URL: http://dx.doi.org/10.1112/plms/s3-2.1.69.
  12. Adrian Dumitrescu and János Pach. Pushing squares around. Graphs and Combinatorics, 22(1):37-50, 2006. URL: http://dx.doi.org/10.1007/s00373-005-0640-1.
  13. 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. URL: http://dx.doi.org/10.1007/978-3-662-48971-0_21.
  14. Gilad Goraly and Refael Hassin. Multi-color pebble motion on graphs. Algorithmica, 58(3):610-636, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9290-7.
  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: http://dx.doi.org/10.1016/j.tcs.2005.05.008.
  16. 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: http://dx.doi.org/10.1016/j.tcs.2010.12.005.
  17. Libin Jiang, Mathieu Leconte, Jian Ni, R. Srikant, and Jean Walrand. Fast mixing of parallel Glauber dynamics and low-delay CSMA scheduling. IEEE Transactions on Information Theory, 58(10):6541-6555, 2012. URL: http://dx.doi.org/10.1109/TIT.2012.2204032.
  18. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.004.
  19. Prashant Kataria and Rajarshi Roy. Parallel Glauber dynamics-based scheduling in static wireless grid networks with polynomially fading interference. Electronics Letters, 51(23):1948-1950, 2015. URL: http://dx.doi.org/10.1049/el.2014.3385.
  20. Nancy G. Kinnersley and Michael A. Langston. Obstruction set isolation for the gate matrix layout problem. Discrete Applied Mathematics, 54(2-3):169-213, 1994. URL: http://dx.doi.org/10.1016/0166-218X(94)90021-3.
  21. 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. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_42.
  22. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. In Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 281-294, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_24.
  23. Francesca R. Nardi, Alessandro Zocca, and Sem C. Borst. Hitting time asymptotics for hard-core interactions on grids. Journal of Statistical Physics, 162(2):522-576, 2016. URL: http://dx.doi.org/10.1007/s10955-015-1391-x.
  24. Marcin Wrochna. Reconfiguration in bounded bandwidth and treedepth. arXiv:1405.0847, 2014. URL: http://arxiv.org/abs/1405.0847.
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