Document Open Access Logo

Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

Authors Nicolas Bousquet , Takehiro Ito , Yusuke Kobayashi , Haruka Mizuta, Paul Ouvrard, Akira Suzuki , Kunihiro Wasa

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.15.pdf
  • Filesize: 0.92 MB
  • 21 pages

Document Identifiers

Author Details

Nicolas Bousquet
  • CNRS, LIRIS, Université de Lyon, France
Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Japan
Yusuke Kobayashi
  • Research Institute for Mathematical Sciences, Kyoto University, Japan
Haruka Mizuta
  • Graduate School of Information Sciences, Tohoku University, Japan
Paul Ouvrard
  • Université de Bordeaux, France
Akira Suzuki
  • Graduate School of Information Sciences, Tohoku University, Japan
Kunihiro Wasa
  • Toyohashi University of Technology, Japan

Funding

This work is partially supported by JSPS and MEAE-MESRI under the Japan-France Integrated Action Program (SAKURA).
  • Bousquet, Nicolas: This work was supported by ANR project GrR (ANR-18-CE40-0032).
  • Ito, Takehiro: Partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814 and JP20H05793, Japan.
  • Kobayashi, Yusuke: Partially supported by JSPS KAKENHI Grant Numbers 18H05291, JP20K11692, and 20H05795, Japan.
  • Ouvrard, Paul: This work was supported by ANR project GrR (ANR-18-CE40-0032).
  • Suzuki, Akira: Partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20K11666 and JP20H05794, Japan.
  • Wasa, Kunihiro: Partially supported by JST CREST Grant Numbers JPMJCR18K3 and JPMJCR1401, and JSPS KAKENHI Grant Numbers 19K20350 and JP20H05793, Japan.

Acknowledgements

The authors thank anonymous reviewers for their valuable comments.

Cite As Get BibTex

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.15

Abstract

We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.

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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Matthieu Barjon, Arnaud Casteigts, Serge Chaumette, Colette Johnen, and Yessin M. Neggaz. Maintaining a spanning forest in highly dynamic networks: The synchronous case. In Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro, editors, Principles of Distributed Systems, pages 277-292, Cham, 2014. Springer International Publishing. Google Scholar
  2. 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, September 7-9, 2020, Pisa, Italy (Virtual Conference), pages 24:1-24:15, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.24.
  3. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of spanning trees with degree constraint or diameter constraint, 2022. URL: http://arxiv.org/abs/2201.04354.
  4. Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-source shortest paths in embedded graphs. SIAM Journal on Computing, 42(4):1542-1571, 2013. URL: https://doi.org/10.1137/120864271.
  5. Artur Czumaj and Willy-B. Strothmann. Bounded degree spanning trees. In Rainer Burkard and Gerhard Woeginger, editors, Algorithms - ESA '97, volume 1284 of LNCS, pages 104-117, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. Google Scholar
  6. Martin Furer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409-423, 1994. URL: https://doi.org/10.1006/jagm.1994.1042.
  7. Michel X. Goemans. Minimum bounded degree spanning trees. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 273-282. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.48.
  8. Refael Hassin and Asaf Levin. Minimum restricted diameter spanning trees. Discrete Applied Mathematics, 137(3):343-357, 2004. URL: https://doi.org/10.1016/S0166-218X(03)00360-3.
  9. Refael Hassin and Arie Tamir. On the minimum diameter spanning tree problem. Inf. Process. Lett., 53(2):109-111, January 1995. URL: https://doi.org/10.1016/0020-0190(94)00183-Y.
  10. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005. URL: https://doi.org/10.1016/j.tcs.2005.05.008.
  11. 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.
  12. Silu Huang, Ada Wai-Chee Fu, and Ruifeng Liu. Minimum spanning trees in temporal graphs. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD '15, pages 419-430, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2723372.2723717.
  13. Giuseppe F. Italiano and Rajiv Ramaswami. Maintaining spanning trees of small diameter. Algorithmica, 22(3):275-304, 1998. URL: https://doi.org/10.1007/PL00009225.
  14. 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.
  15. Richard M. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  16. 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.
  17. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  18. Mohit Singh and Lap Chi Lau. Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM, 62(1), March 2015. URL: https://doi.org/10.1145/2629366.
  19. Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, and Jack Snoeyink. Computing a (1+ε)-approximate geometric minimum-diameter spanning tree. Algorithmica, 38(4):577-589, 2004. URL: https://doi.org/10.1007/s00453-003-1056-z.
  20. Asahi Takaoka. Complexity of Hamiltonian cycle reconfiguration. Algorithms, 11(9), 2018. URL: https://doi.org/10.3390/a11090140.
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