Paper Info
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.
Year
DOI
Venue
2019
10.4230/LIPIcs.ESA.2019.61
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
Matching,Combinatorial reconfiguration,Alternating cycles,Combinatorial shortest paths
Conference
144
Issue
ISSN
Citations 
340
1868-8969
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Takehiro Ito126040.71
Naonori Kakimura25921.18
Naoyuki Kamiyama38023.40
Yusuke Kobayashi410621.98
Yoshio Okamoto517028.50