2026-07-26T17:26:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24998 2025-11-26T06:44:53Z ddc:004 open_access

Flipping Odd Matchings in Geometric and Combinatorial Settings Aichholzer, Oswin Brenner, Sofia Dorfer, Joseph Hoang, Hung P. Perz, Daniel Rieck, Christian Verciani, Francesco Odd matchings reconfiguration flip graph geometric combinatorial connectivity NP-hardness FPT We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched vertex of the first matching gets matched, while consequently another vertex becomes unmatched. We consider two distinct settings: the geometric setting, in which the vertices are points embedded in the plane and all occurring odd matchings are crossing-free, and a combinatorial setting, in which we consider odd matchings in general graphs. For the latter setting, we provide a complete polynomial time checkable characterization of graphs in which any two odd matchings can be reconfigured into each another. This complements the previously known result that the flip graph is always connected in the geometric setting [Oswin Aichholzer et al., 2025]. In the combinatorial setting, we prove that the diameter of the flip graph, if connected, is linear in the number of vertices. Furthermore, we establish that deciding whether there exists a flip sequence of length k transforming one given matching into another is NP-complete in both the combinatorial and the geometric settings. To prove the latter, we introduce a framework that allows us to transform partial order types into general position with only polynomial overhead. Finally, we demonstrate that when parameterized by the flip distance k, the problem is fixed-parameter tractable (FPT) in the geometric setting when restricted to convex point sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oswin Aichholzer and Sofia Brenner and Joseph Dorfer and Hung P. Hoang and Daniel Perz and Christian Rieck and Francesco Verciani 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.12 urn:nbn:de:0030-drops-249983 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode