Document Open Access Logo

The Perfect Matching Reconfiguration Problem

Authors Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito , Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.80.pdf
  • Filesize: 1.06 MB
  • 14 pages

Document Identifiers

Author Details

Marthe Bonamy
  • CNRS, LaBRI, Université de Bordeaux, Talence, France
Nicolas Bousquet
  • CNRS, Laboratoire G-SCOP, Grenoble-INP, Univ. Grenoble-Alpes, Grenoble, France
Marc Heinrich
  • LIRIS, Université Claude Bernard Lyon 1, Lyon, France
Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yusuke Kobayashi
  • Research Institute for Mathematical Sciences, Kyoto University, Kyoto, Japan
Arnaud Mary
  • LBBE, Université Claude Bernard Lyon 1, Lyon, France
Moritz Mühlenthaler
  • Fakultät für Mathematik, TU Dortmund University, Dortmund, Germany
Kunihiro Wasa
  • Principles of Informatics Research Division, National Institute of Informatics, Tokyo, Japan

Funding

  • Bonamy, Marthe: Partially supported by ANR project GrR (ANR-18-CE40-0032).
  • Bousquet, Nicolas: Partially supported by ANR project GrR (ANR-18-CE40-0032).
  • Heinrich, Marc: Partially supported by ANR project GrR (ANR-18-CE40-0032).
  • Ito, Takehiro: Partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan.
  • Kobayashi, Yusuke: Supported by JST ACT-I Grant Number JPMJPR17UB, and JSPS KAKENHI Grant Numbers JP16K16010, JP16H03118, JP17K19960 and JP18H05291, Japan.
  • Mary, Arnaud: Partially supported by ANR project GrR (ANR-18-CE40-0032).
  • Wasa, Kunihiro: Partially supported by JST CREST Grant Number JPMJCR1401 and JPMJCR18K3, and JSPS KAKENHI Grant Number JP19K20350, Japan.

Acknowledgements

This work is partially supported by JSPS and MAEDI under the Japan-France Integrated Action Program (SAKURA).

Cite As Get BibTex

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.80

Abstract

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Combinatorial Reconfiguration
  • Graph Algorithms
  • Perfect Matching

Metrics

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

References

  1. Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangulations of a simple polygon is NP-complete. Discrete & Computational Geometry, 54(2):368-389, 2015. Google Scholar
  2. Sergey Bereg and Hiro Ito. Transforming Graphs with the Same Graphic Sequence. Journal of Information Processing, 25:627-633, 2017. Google Scholar
  3. Marthe Bonamy and Nicolas Bousquet. Reconfiguring independent sets in cographs. arXiv preprint arXiv:1406.1433, 2014. Google Scholar
  4. Paul Bonsma. Independent set reconfiguration in cographs and their generalizations. Journal of Graph Theory, 83(2):164-195, 2016. Google Scholar
  5. Paul Bonsma, Marcin Kamiński, and Marcin Wrochna. Reconfiguring Independent Sets in Claw-Free Graphs. In Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory ( 2014), volume 8503 of Lecture Notes in Computer Science, pages 86-97, 2014. Google Scholar
  6. Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token Jumping in Minor-Closed Classes. In Proceedings of the 21st International Symposium on Fundamentals of Computation Theory ( 2017), volume 10472 of Lecture Notes in Computer Science, pages 136-149, 2017. Google Scholar
  7. 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. Google Scholar
  8. Persi Diaconis, Ronald Graham, and Susan P. Holmes. Statistical problems involving permutations with restricted positions, volume 36 of Lecture Notes-Monograph Series, pages 195-222. Institute of Mathematical Statistics, Beachwood, OH, 2001. Google Scholar
  9. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Heidelberg, third edition, 2005. Google Scholar
  10. Feodor F. Dragan. On Greedy Matching Ordering and Greedy Matchable Graphs (Extended Abstract). In Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science ( 1997), volume 1335 of Lecture Notes in Computer Science, pages 184-198, 1997. Google Scholar
  11. Feodor F. Dragan. Strongly orderable graphs A common generalization of strongly chordal and chordal bipartite graphs. Discrete Applied Mathematics, 99(1-3):427-442, 2000. Google Scholar
  12. Martin Dyer and Haiko Müller. Counting perfect matchings and the switch chain. arXiv preprint arXiv:1705.05790, 2017. Google Scholar
  13. Martin E. Dyer, Mark Jerrum, and Haiko Müller. On the Switch Markov Chain for Perfect Matchings. Journal of the ACM, 64(2):12:1-12:33, 2017. Google Scholar
  14. Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT press, 1989. Google Scholar
  15. S. L. Hakimi. On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness. Journal of the Society for Industrial and Applied Mathematics, 11(1):135-147, 1963. Google Scholar
  16. 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. Google Scholar
  17. Jan van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, pages 127-160. Cambridge University Press, 2013. Google Scholar
  18. Michael E. Houle, Ferran Hurtado, Marc Noy, and Eduardo Rivera-Campo. Graphs of triangulations and perfect matchings. Graphs and Combinatorics, 21(3):325-331, 2005. Google Scholar
  19. Wen-Lian Hsu. A Simple Test for Interval Graphs. In Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science ( 1992), volume 657 of Lecture Notes in Computer Science, pages 11-16, 1992. Google Scholar
  20. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry, 22(3):333-346, 1999. Google Scholar
  21. 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. Google Scholar
  22. Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. On the Parameterized Complexity for Token Jumping on Graphs. In Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation ( 2014), volume 8402 of Lecture Notes in Computer Science, pages 341-351, 2014. Google Scholar
  23. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. Google Scholar
  24. Charles L. Lawson. Software for C₁ surface interpolation. In Mathematical software, pages 161-194. Elsevier, 1977. Google Scholar
  25. Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Computational Geometry, 49:17-23, 2015. Google Scholar
  26. Haruka Mizuta, Takehiro Ito, and Xiao Zhou. Reconfiguration of Steiner Trees in an Unweighted Graph. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100-A(7):1532-1540, 2017. Google Scholar
  27. Naomi Nishimura. Introduction to Reconfiguration. Algorithms, 11(4):52, 2018. Google Scholar
  28. Nicolau C. Saldanha, Carlos Tomei, Mario A. Casarin, and Domingos Romualdo. Spaces of domino tilings. Discrete & Computational Geometry, 14(2):207-233, 1995. Google Scholar
  29. Walter J. Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities. Journal of Computer and System Sciences, 4:177-192, 1970. Google Scholar
  30. James K. Senior. Partitions and Their Representative Graphs. American Journal of Mathematics, 73(3):663-689, 1951. Google Scholar
  31. Daniel Stefankovic, Eric Vigoda, and John Wilmes. On Counting Perfect Matchings in General Graphs. In Proceedings of the 13th Latin American Theoretical Informatics Symposium ( 2018), volume 10807 of Lecture Notes in Computer Science, pages 873-885, 2018. Google Scholar
  32. Todd G. Will. Switching Distance Between Graphs with the Same Degrees. SIAM Journal on Discrete Mathematics, 12(3):298-306, 1999. Google Scholar
  33. Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer and System Sciences, 93:1-10, 2018. Google Scholar
  34. Tom C. van der Zanden. Parameterized Complexity of Graph Constraint Logic. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation ( 2015), volume 43 of Leibniz International Proceedings in Informatics, pages 282-293, 2015. Google Scholar
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