Polynomial recognition of Switchable graphs

Open Question: Recognition of Switchable Graphs · arXiv:1904.06184

arXiv Informal medium confidence— first stated 2019-04-12

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

Status open high confidence

The question of whether the Switchable class (the hereditary class of graphs whose perfect-matching reconfiguration graph under length-4 flip operations is connected) can be recognized in polynomial time remains open as of May 2026. A Semantic Scholar citation search for arXiv:1904.06184 returned 20 citing papers (2021–2026) spanning reconfiguration hardness, geometric matching flips, and related combinatorics, but none specifically tackles the recognition complexity of the Switchable class. Keyword searches for 'switchable recognition polynomial perfect matching reconfiguration' likewise found no post-2019 resolution.

Reviewer notes. 20 citing papers found via Semantic Scholar (arXiv:2602.09573, 2511.04863, 2510.24226, 2508.18457, 2505.00988, 2502.16398, 2410.14421, 2410.07060, 2409.11723, 2312.07241, 2307.00853, 2210.14608, 2210.12036, 2209.10262, 2206.03879, 2203.13435, 2202.11857, 2102.10568, and two non-arXiv). None address recognition of the Switchable class. The related arXiv:2604.17911 ('Dirac's theorem and the switch geometry of perfect matchings', 2025) studies degree conditions for connectivity of reconfiguration graphs but does not address polynomial recognition of the Switchable hereditary class.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It is not clear whether graphs in the Switchable class (the hereditary class of graphs for which the reconfiguration graph of perfect matchings under flips is connected) can be recognized in polynomial time.

Context

The authors of [14] characterize the hereditary class of general (non-bipartite) graphs for which the reconfiguration graph of perfect matchings under flips is connected, calling it Switchable. The paper notes that the recognition complexity of this class remains open.

Notes. Stated as a passing remark rather than a labelled problem; paper text is truncated before any concluding open-problems section, so additional conjectures may be present in the full paper.

Source paper

The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa · 2019-04-12
https://arxiv.org/abs/1904.06184 PDF source