Shortest reconfiguration of perfect matchings via alternating cycles
Shortest reconfiguration of perfect matchings via alternating cycles
复制标题
通过交替循环实现完美匹配的最短重构
DOI：
10.1137/20m1364370
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Yoshio Okamoto
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Yoshio Okamoto
受完美匹配多面体邻接性的启发，研究了完美匹配多面体通过交替循环的最短重构问题。也就是说，我们希望找到一个最短的完美匹配序列，它将一个给定的完美匹配转换为另一个给定的完美匹配，使得每对连续完美匹配的对称差是一个循环。该问题等价于完美匹配多面体中的组合最短路问题。我们证明了即使给定的图是平面图或二部图，这个问题也是NP-难的，但当图是外平面图时，这个问题可以在多项式时间内得到解决。
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.