@inproceedings{2256a918b19b46cb976e95218f6cde51,
title = "Shortest reconfiguration of perfect matchings via alternating cycles",
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.",
keywords = "Alternating cycles, Combinatorial reconfiguration, Combinatorial shortest paths, Matching",
author = "Takehiro Ito and Naonori Kakimura and Naoyuki Kamiyama and Yusuke Kobayashi and Yoshio Okamoto",
note = "Publisher Copyright: {\textcopyright} Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto.; 27th Annual European Symposium on Algorithms, ESA 2019 ; Conference date: 09-09-2019 Through 11-09-2019",
year = "2019",
month = sep,
doi = "10.4230/LIPIcs.ESA.2019.61",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Bender, \{Michael A.\} and Ola Svensson and Grzegorz Herman",
booktitle = "27th Annual European Symposium on Algorithms, ESA 2019",
}