License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.80
URN: urn:nbn:de:0030-drops-110248
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11024/
Go to the corresponding LIPIcs Volume Portal

Bonamy, Marthe ; Bousquet, Nicolas ; Heinrich, Marc ; Ito, Takehiro ; Kobayashi, Yusuke ; Mary, Arnaud ; Mühlenthaler, Moritz ; Wasa, Kunihiro

The Perfect Matching Reconfiguration Problem

pdf-format:
LIPIcs-MFCS-2019-80.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{bonamy_et_al:LIPIcs:2019:11024,
  author =	{Marthe Bonamy and Nicolas Bousquet and Marc Heinrich and Takehiro Ito and Yusuke Kobayashi and Arnaud Mary and Moritz M{\"u}hlenthaler and Kunihiro Wasa},
  title =	{{The Perfect Matching Reconfiguration Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11024},
  URN =		{urn:nbn:de:0030-drops-110248},
  doi =		{10.4230/LIPIcs.MFCS.2019.80},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching}
}

Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI