Skip to Main content Skip to Navigation
Conference papers

The Perfect Matching Reconfiguration Problem

Abstract : We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.
Document type :
Conference papers
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-02335588
Contributor : Marie-France Sagot <>
Submitted on : Monday, October 28, 2019 - 1:30:20 PM
Last modification on : Monday, September 6, 2021 - 3:12:01 PM
Long-term archiving on: : Wednesday, January 29, 2020 - 3:38:51 PM

File

LIPIcs-MFCS-2019-80.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, et al.. The Perfect Matching Reconfiguration Problem. MFCS 2019 - 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany. pp.1-14, ⟨10.4230/LIPIcs.MFCS.2019.80⟩. ⟨hal-02335588⟩

Share

Metrics

Record views

208

Files downloads

939