LIPIcs.ESA.2019.61.pdf
- Filesize: 1.01 MB
- 15 pages
Document
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Authors
Takehiro Ito 
,
Yoshio Okamoto
-
Part of:
Volume:
27th Annual European Symposium on Algorithms (ESA 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-06
File
Document Identifiers
Author Details
Cite As Get BibTex
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest Reconfiguration of Perfect Matchings via Alternating Cycles. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.61
Abstract
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- Matching
- Combinatorial reconfiguration
- Alternating cycles
- Combinatorial shortest paths
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip distances between graph orientations. CoRR, abs/1902.06103, 2019. To appear in WG 2019. URL: http://arxiv.org/abs/1902.06103.
- Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. CoRR, abs/1904.06184, 2019. To appear in MFCS 2019. URL: http://arxiv.org/abs/1904.06184.
- Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest Reconfiguration of Matchings. CoRR, abs/1812.05419, 2018. To appear in WG 2019. URL: http://arxiv.org/abs/1812.05419.
- Vašek Chvátal. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B, 18(2):138-154, 1975. URL: https://doi.org/10.1016/0095-8956(75)90041-6.
- Michael R. Garey, David S. Johnson, and Robert Endre Tarjan. The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5(4):704-714, 1976. URL: https://doi.org/10.1137/0205049.
- Manoj Gupta, Hitesh Kumar, and Neeldhara Misra. On the Complexity of Optimal Matching Reconfiguration. In Barbara Catania, Rastislav Královic, Jerzy R. Nawrocki, and Giovanni Pighizzini, editors, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings, volume 11376 of Lecture Notes in Computer Science, pages 221-233. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-10801-4_18.
- Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: https://doi.org/10.1017/CBO9781139506748.005.
- 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.
- Marcin Kamiński, Paul Medvedev, and Martin Milanǐc. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.004.
- Denis Naddef. The Hirsch conjecture is true for (0, 1)-polytopes. Mathematical Programming, 45(1-3):109-110, 1989. URL: https://doi.org/10.1007/BF01589099.
- Naomi Nishimura. Introduction to Reconfiguration. Algorithms, 11(4):paper id 52, 2018. URL: https://doi.org/10.3390/a11040052.
- Ján Plesník. The NP-Completeness of the Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two. Information Processing Letters, 8(4):199-201, 1979. URL: https://doi.org/10.1016/0020-0190(79)90023-1.
-
Daniel Ratner and Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. In Tom Kehler, editor, Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA, August 11-15, 1986. Volume 1: Science., pages 168-172. Morgan Kaufmann, 1986.
- Francisco Santos. A counterexample to the Hirsch Conjecture. Annals of Mathematics, 176(1):383-412, 2012. URL: https://doi.org/10.4007/annals.2012.176.1.7.
- Noriyoshi Sukegawa. An asymptotically improved upper bound on the diameter of polyhedra. to appear in Discrete & Computational Geometry. URL: https://doi.org/10.1007/s00454-018-0016-y.