Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

Authors Takehiro Ito , Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.61.pdf
  • Filesize: 1.01 MB
  • 15 pages

Document Identifiers

Author Details

Takehiro Ito
  • Tohoku University, Sendai, Japan
Naonori Kakimura
  • Keio University, Yokohama, Japan
Naoyuki Kamiyama
  • Kyushu University, Fukuoka, Japan
  • JST, PRESTO, Kawaguchi, Japan
Yusuke Kobayashi
  • Kyoto University, Kyoto, Japan
Yoshio Okamoto
  • University of Electro-Communications, Chofu, Japan
  • RIKEN Center for Advanced Intelligence Project, Tokyo, Japan

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Naomi Nishimura. Introduction to Reconfiguration. Algorithms, 11(4):paper id 52, 2018. URL: https://doi.org/10.3390/a11040052.
  12. 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.
  13. 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. Google Scholar
  14. 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.
  15. 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.
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