TY - GEN
T1 - Shortest reconfiguration of perfect matchings via alternating cycles
AU - Ito, Takehiro
AU - Kakimura, Naonori
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Okamoto, Yoshio
N1 - Funding Information:
Funding Takehiro Ito: Partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan. Naonori Kakimura: Partially supported by JSPS KAKENHI Grant Numbers JP17K00028 and JP18H05291, Japan. Naoyuki Kamiyama: Partially supported by JST PRESTO Grant Number JPMJPR1753, Japan. Yusuke Kobayashi: Partly supported by JSPS KAKENHI Grant Numbers JP16K16010, JP17K19960, and JP18H05291, Japan. Yoshio Okamoto: Partially supported by JSPS KAKENHI Grant Number 15K00009 and JST CREST Grant Number JPMJCR1402, and Kayamori Foundation of Informational Science Advancement.
Publisher Copyright:
© Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto.
PY - 2019/9
Y1 - 2019/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85074837915&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074837915&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2019.61
DO - 10.4230/LIPIcs.ESA.2019.61
M3 - Conference contribution
AN - SCOPUS:85074837915
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th Annual European Symposium on Algorithms, ESA 2019
A2 - Bender, Michael A.
A2 - Svensson, Ola
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th Annual European Symposium on Algorithms, ESA 2019
Y2 - 9 September 2019 through 11 September 2019
ER -