LIPIcs.ESA.2020.24.pdf
- Filesize: 0.84 MB
- 15 pages
Document
Reconfiguration of Spanning Trees with Many or Few Leaves
Authors
Nicolas Bousquet 
,
Takehiro Ito ,
Yusuke Kobayashi ,
Akira Suzuki ,
Kunihiro Wasa
-
Part of:
Volume:
28th Annual European Symposium on Algorithms (ESA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-26
File
Document Identifiers
Author Details
Cite AsGet BibTex
Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Many or Few Leaves. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.24
https://doi.org/10.4230/LIPIcs.ESA.2020.24
Abstract
Let G be a graph and T₁,T₂ be two spanning trees of G. We say that T₁ can be transformed into T₂ via an edge flip if there exist two edges e ∈ T₁ and f in T₂ such that T₂ = (T₁⧵e) ∪ f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011].
We investigate the problem of determining, given two spanning trees T₁,T₂ with an additional property Π, if there exists an edge flip transformation from T₁ to T₂ keeping property Π all along.
First we show that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at most k (for any fixed k ≥ 3) leaves is PSPACE-complete.
We then prove that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- combinatorial reconfiguration
- spanning trees
- PSPACE
- polynomial-time algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. In Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, pages 127-139, 2017. URL: https://doi.org/10.1007/978-3-319-68705-6_10.
- Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
- Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest reconfiguration of matchings. In Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, pages 162-174, 2019. URL: https://doi.org/10.1007/978-3-030-30786-8_13.
-
Alan Frieze and Eric Vigoda. A survey on the use of markov chains to randomly sample colourings. Oxford Lecture Series in Mathematics and its Applications, 34:53, 2007.
-
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
- Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, and Youcef Tebbal. The complexity of dominating set reconfiguration. Theor. Comput. Sci., 651(C):37-49, October 2016. URL: https://doi.org/10.1016/j.tcs.2016.08.016.
- Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, and Krishna Vaidyanathan. Reconfiguring spanning and induced subgraphs. Theor. Comput. Sci., 806:553-566, 2020. URL: https://doi.org/10.1016/j.tcs.2019.09.018.
- Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. The coloring reconfiguration problem on specific graph classes. In Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I, pages 152-162, 2017. URL: https://doi.org/10.1007/978-3-319-71150-8_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, October 2005. URL: https://doi.org/10.1016/j.tcs.2005.05.008.
- 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):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
- Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Reconfiguration of minimum steiner trees via vertex exchanges. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany., pages 79:1-79:11, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.79.
- Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
- Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: https://doi.org/10.1017/CBO9781139506748.005.
- 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.