pith. sign in

arxiv: 1907.01700 · v1 · pith:6TIT7PX6new · submitted 2019-07-03 · 💻 cs.DS · cs.DM

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

Takehiro Ito , Naonori Kakimura , Naoyuki Kamiyama , Yusuke Kobayashi , Yoshio Okamoto This is my paper

Pith reviewed 2026-05-25 10:20 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords perfect matchingsreconfigurationalternating cyclesNP-hardnessouterplanar graphsperfect matching polytopeplanar graphsbipartite graphs
0
0 comments X

The pith

The shortest reconfiguration of perfect matchings via alternating cycles is NP-hard on planar and bipartite graphs but polynomial-time solvable on outerplanar graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies transforming one perfect matching to another through a shortest sequence of steps, each flipping the edges along a single alternating cycle. This task is equivalent to finding the combinatorial shortest path in the perfect matching polytope. The authors establish that computing this shortest sequence is NP-hard even when the graph is planar or bipartite. They also give a polynomial-time algorithm for the special case when the graph is outerplanar. A reader would care because the results delineate the computational complexity of a natural reconfiguration problem arising from polytope adjacency.

Core claim

The problem of finding a shortest sequence of perfect matchings transforming one given perfect matching to another, where each consecutive pair differs by the edges of exactly one alternating cycle, is NP-hard on planar graphs and on bipartite graphs, but can be solved in polynomial time on outerplanar graphs.

What carries the argument

The equivalence of the alternating-cycle reconfiguration distance to the combinatorial shortest-path distance in the perfect matching polytope, which transfers both the hardness proofs and the polynomial-time algorithm between the two problems.

Load-bearing premise

The input graphs contain two perfect matchings whose symmetric difference consists of alternating cycles, and the reconfiguration distance equals the shortest path distance in the perfect matching polytope under the given adjacency.

What would settle it

A concrete planar graph together with two perfect matchings for which the length of the shortest alternating-cycle sequence differs from the shortest path distance between the corresponding vertices in the perfect matching polytope.

Figures

Figures reproduced from arXiv: 1907.01700 by Naonori Kakimura, Naoyuki Kamiyama, Takehiro Ito, Yoshio Okamoto, Yusuke Kobayashi.

Figure 1
Figure 1. Figure 1: Two sequences of perfect matchings between [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The construction of G∗ and the length function `. In (c), the edge lengths are depicted by different styles: thick solid lines represent edges of length two, thin solid lines represent edges of length one, and dotted lines represent edges of length zero. along the chords in F. Notice that each edge in F appears on the outer face boundaries in two of these subgraphs. Furthermore, each chord e in these subgr… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the proof of Claim 2. (a) The perfect matchings M and N are shown by red and blue, respectively. (b) The graph G∗ . (c) The center r and the chosen set X∗ . Proof of Claim 1. By the duality, the cycle C in G corresponds to a cut C ∗ in G∗ such that the inside is connected. Such a cut intersects with any path in G∗ at most twice as G∗ is a tree, and only the intersected edges can change the … view at source ↗
Figure 4
Figure 4. Figure 4: The construction of a partition for the outerplanar graph in Figure [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) Subtree Tv in the whole tree T, (b) subtree T j v in Tv, and (c) an (x, y, z)-separator of T j v . We now define partial solutions for subtrees. For a subtree T j v and an edge subset F 0 ⊆ E0 ∩ E(T j v ), the frontier for F 0 is the component (subtree) in T j v − F 0 that contains the root v of T j v . We sometimes call it the v-frontier for F 0 to emphasize the root v. For three integers x, y, z ∈ {0… view at source ↗
Figure 6
Figure 6. Figure 6: (x, y, z)-separators of a subtree T j v , and their restrictions to subtrees T j−1 v and Twj . (a) The vertices v and wj are contained in the same component. (See also [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Reduction for planar graphs of maximum degree three. Top left: a yes instance [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Reduction for bipartite graphs of maximum degree three. Top left: a yes instance [PITH_FULL_IMAGE:figures/full_fig_p017_8.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the shortest reconfiguration problem between two perfect matchings in an undirected graph, where each step replaces one matching with another whose symmetric difference is a single alternating cycle. This is equivalent to the combinatorial shortest-path problem in the 1-skeleton of the perfect-matching polytope. The central claims are that the problem is NP-hard even when the input graph is planar or bipartite, yet solvable in polynomial time when the graph is outerplanar.

Significance. If the proofs and algorithm are correct, the work supplies a complexity dichotomy for matching reconfiguration across natural graph classes and directly informs the structure of the perfect-matching polytope. The outerplanar polynomial-time result is a concrete algorithmic contribution that contrasts with the hardness results.

minor comments (3)
  1. The abstract asserts the existence of NP-hardness reductions and a polynomial-time algorithm for outerplanar graphs but does not indicate the running time or the key structural property (e.g., treewidth or cycle decomposition) exploited by the algorithm; a brief statement of these facts in the abstract would improve readability.
  2. Section 1 (Introduction) should explicitly recall that any two perfect matchings on the same vertex set have symmetric difference consisting solely of even alternating cycles; this fact is used throughout but is not stated until later.
  3. The NP-hardness proofs for planar and bipartite graphs are stated to exist, but the manuscript would benefit from a short high-level overview of the reduction source (e.g., from Hamiltonian cycle or 3-SAT) before the formal construction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents direct complexity results: NP-hardness even for planar or bipartite graphs, and polynomial-time solvability for outerplanar graphs. These are established via explicit reductions and algorithms, not via any fitted parameters, self-definitional equations, or load-bearing self-citations. The noted equivalence between reconfiguration distance and shortest-path distance in the perfect-matching polytope follows from the standard definition of the 1-skeleton (edges exist precisely when the symmetric difference is one alternating cycle), which is an external fact from polyhedral combinatorics and holds independently of the paper. The input condition (symmetric difference decomposable into alternating cycles) is always satisfied for any pair of perfect matchings and introduces no circularity. No patterns from the enumerated list apply; the derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and polyhedral combinatorics without introducing new free parameters or invented entities.

axioms (1)
  • standard math Undirected graphs admit perfect matchings whose symmetric differences decompose into alternating cycles.
    Invoked in the problem definition and equivalence to polytope shortest paths.

pith-pipeline@v0.9.0 · 5633 in / 1165 out tokens · 47343 ms · 2026-05-25T10:20:28.833627+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 3 internal anchors

  1. [1]

    Flip distances between graph orientations

    Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip distances between graph orientations. CoRR, abs/1902.06103, 2019. To appear in WG 2019.arXiv:1902.06103

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  2. [2]

    Flip distance between triangula- tions of a simple polygon is NP-complete.Discrete & Computational Geometry, 54(2):368– 389, 2015

    Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip distance between triangula- tions of a simple polygon is NP-complete.Discrete & Computational Geometry, 54(2):368– 389, 2015. doi:10.1007/s00454-015-9709-7

    work page doi:10.1007/s00454-015-9709-7 2015

  3. [3]

    Alfakih and Katta G

    Abdo Y. Alfakih and Katta G. Murty. Adjacency on the constrained assignment prob- lem. Discrete Applied Mathematics, 87(1-3):269–274, 1998. doi:10.1016/S0166-218X(98) 00063-8

    work page doi:10.1016/s0166-218x(98 1998

  4. [4]

    The Perfect Matching Reconfiguration Problem

    Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The perfect matching reconfiguration problem. CoRR, abs/1904.06184, 2019. To appear in MFCS 2019.arXiv:1904.06184

    work page internal anchor Pith review Pith/arXiv arXiv 1904

  5. [5]

    Complexity of token swapping and its variants.Algorithmica, 80(9):2656–2682, 2018

    Édouard Bonnet, Tillmann Miltzow, and Paweł Rzążewski. Complexity of token swapping and its variants.Algorithmica, 80(9):2656–2682, 2018. doi:10.1007/s00453-017-0387-0

    work page doi:10.1007/s00453-017-0387-0 2018

  6. [6]

    Shortest Reconfiguration of Matchings

    Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest reconfiguration of matchings.CoRR, abs/1812.05419, 2018. To appear in WG 2019.arXiv: 1812.05419

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  7. [7]

    Finding short paths on polytopes by the shadow vertex algorithm

    Tobias Brunsch and Heiko Röglin. Finding short paths on polytopes by the shadow vertex algorithm. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 ofLecture Notes in Computer ...

    work page doi:10.1007/978-3-642-39206-1_24 2013

  8. [8]

    Pancake flipping is hard.J

    Laurent Bulteau, Guillaume Fertin, and Irena Rusu. Pancake flipping is hard.J. Comput. Syst. Sci., 81(8):1556–1574, 2015. doi:10.1016/j.jcss.2015.02.003

    work page doi:10.1016/j.jcss.2015.02.003 2015

  9. [9]

    On certain polytopes associated with graphs

    Vašek Chvátal. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B, 18(2):138–154, 1975. doi:10.1016/0095-8956(75)90041-6

    work page doi:10.1016/0095-8956(75)90041-6 1975

  10. [10]

    A combinatorial study of partial order polytopes.Eur

    Samuel Fiorini. A combinatorial study of partial order polytopes.Eur. J. Comb., 24(2):149– 159, 2003. doi:10.1016/S0195-6698(03)00009-X

    work page doi:10.1016/s0195-6698(03)00009-x 2003

  11. [11]

    Frieze and Shang-Hua Teng

    Alan M. Frieze and Shang-Hua Teng. On the complexity of computing the diameter of a polytope. Computational Complexity, 4:207–219, 1994. doi:10.1007/BF01206636

    work page doi:10.1007/bf01206636 1994

  12. [12]

    M. R. Garey, David S. Johnson, and Robert Endre Tarjan. The planar Hamiltonian circuit problem is NP-complete.SIAM J. Comput., 5(4):704–714, 1976. doi:10.1137/0205049

    work page doi:10.1137/0205049 1976

  13. [13]

    Daniel Geist and Ervin Y. Rodin. Adjacency of the 0-1 knapsack problem.Computers & OR, 19(8):797–800, 1992. doi:10.1016/0305-0548(92)90019-2. 19

    work page doi:10.1016/0305-0548(92)90019-2 1992

  14. [14]

    On the complexity of optimal matching reconfiguration

    Manoj Gupta, Hitesh Kumar, and Neeldhara Misra. On the complexity of optimal matching reconfiguration. In Barbara Catania, Rastislav Královic, Jerzy R. Nawrocki, and Giovanni Pighizzini, editors,SOFSEM 2019: Theory and Practice of Computer Science — 45th Inter- national Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec,...

    work page doi:10.1007/978-3-030-10801-4_18 2019

  15. [15]

    The complexity of change

    Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors,Surveys in Combinatorics 2013, volume 409 ofLondon Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press, 2013. doi:10. 1017/CBO9781139506748.005

    work page 2013

  16. [16]

    Demaine, Nicholas J

    Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054–1065, 2011. doi:10.1016/j.tcs.2010.12.005

    work page doi:10.1016/j.tcs.2010.12.005 2011

  17. [17]

    Reconfiguration of maximum-weightb-matchings in a graph.J

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Reconfiguration of maximum-weightb-matchings in a graph.J. Comb. Optim., 37(2):454–464, 2019. doi:10.1007/s10878-018-0289-3

    work page doi:10.1007/s10878-018-0289-3 2019

  18. [18]

    Finding shortest paths between graph colourings.Algorithmica, 75(2):295–321, 2016

    Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, and Daniël Paulusma. Finding shortest paths between graph colourings.Algorithmica, 75(2):295–321, 2016. doi: 10.1007/s00453-015-0009-7

    work page doi:10.1007/s00453-015-0009-7 2016

  19. [20]

    The time complexity of permutation routing via matching, token swapping and a variant.J

    Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka. The time complexity of permutation routing via matching, token swapping and a variant.J. Graph Algorithms Appl., 23(1):29– 70, 2019. doi:10.7155/jgaa.00483

    work page doi:10.7155/jgaa.00483 2019

  20. [21]

    Flip distance between two triangulations of a point set is NP-complete

    Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Comput. Geom., 49:17–23, 2015. doi:10.1016/j.comgeo.2014.11.001

    work page doi:10.1016/j.comgeo.2014.11.001 2015

  21. [22]

    NP-completeness of non-adjacency relations on some 0-1 polytopes

    Tomomi Matsui. NP-completeness of non-adjacency relations on some 0-1 polytopes. Math- ematical Engineering Technical Reports METR-94-12, The University of Tokyo, 1994

    work page 1994

  22. [23]

    Approximation and hardness of token swapping

    Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In Piotr Sankowski and Christos D. Zaroliagis, editors,24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 66:1–66:15. Schloss Dagstuhl - Leibniz-Ze...

    work page doi:10.4230/lipics.esa.2016.66 2016

  23. [24]

    Mouawad, Naomi Nishimura, Vinayak Pathak, and Venkatesh Raman

    Amer E. Mouawad, Naomi Nishimura, Vinayak Pathak, and Venkatesh Raman. Shortest reconfiguration paths in the solution space of boolean formulas.SIAM J. Discrete Math., 31(3):2185–2200, 2017. doi:10.1137/16M1065288

    work page doi:10.1137/16m1065288 2017

  24. [25]

    Degree-constrained subgraph reconfiguration is in P

    Moritz Mühlenthaler. Degree-constrained subgraph reconfiguration is in P. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors,Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 ofLecture Notes in Computer Science, pages 505–5...

    work page doi:10.1007/978-3-662-48054-0_42 2015

  25. [26]

    TheHirschconjectureistruefor (0, 1)-polytopes

    DenisNaddef. TheHirschconjectureistruefor (0, 1)-polytopes. Mathematical Programming, 45(1-3):109–110, 1989. doi:10.1007/BF01589099. 20

    work page doi:10.1007/bf01589099 1989

  26. [27]

    Introduction to reconfiguration

    Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. doi:10. 3390/a11040052

    work page 2018

  27. [28]

    Papadimitriou

    Christos H. Papadimitriou. The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program., 14(1):312–324, 1978. doi:10.1007/BF01588973

    work page doi:10.1007/bf01588973 1978

  28. [29]

    Flip distance between triangulations of a planar point set is APX-hard

    Alexander Pilz. Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom., 47(5):589–604, 2014. doi:10.1016/j.comgeo.2014.01.001

    work page doi:10.1016/j.comgeo.2014.01.001 2014

  29. [30]

    The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two

    Ján Plesník. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett., 8(4):199–201, 1979. doi:10.1016/0020-0190(79) 90023-1

    work page doi:10.1016/0020-0190(79 1979

  30. [31]

    Findingashortestsolutionforthe N×N extension of the 15-PUZZLE is intractable

    DanielRatnerandManfredK.Warmuth. Findingashortestsolutionforthe N×N extension of the 15-PUZZLE is intractable. In Tom Kehler, editor,Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA, August 11-15, 1986. Volume 1: Science., pages 168–172. Morgan Kaufmann, 1986

    work page 1986

  31. [32]

    The diameter of the fractional matching polytope and its hardness implica- tions

    Laura Sanità. The diameter of the fractional matching polytope and its hardness implica- tions. In Mikkel Thorup, editor,59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 910–921. IEEE Computer So- ciety, 2018. doi:10.1109/FOCS.2018.00090

    work page doi:10.1109/focs.2018.00090 2018

  32. [33]

    A counterexample to the Hirsch Conjecture

    Francisco Santos. A counterexample to the Hirsch Conjecture. Annals of Mathematics, 176(1):383–412, 2012. doi:10.4007/annals.2012.176.1.7

    work page doi:10.4007/annals.2012.176.1.7 2012

  33. [34]

    An asymptotically improved upper bound on the diameter of polyhe- dra

    Noriyoshi Sukegawa. An asymptotically improved upper bound on the diameter of polyhe- dra. Discrete & Computational Geometry. To appear. doi:10.1007/s00454-018-0016-y

    work page doi:10.1007/s00454-018-0016-y

  34. [35]

    Shortest reconfiguration of sliding tokens on a cater- pillar

    Takeshi Yamada and Ryuhei Uehara. Shortest reconfiguration of sliding tokens on a cater- pillar. In Mohammad Kaykobad and Rossella Petreschi, editors,WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings, volume 9627 ofLecture Notes in Computer Science, pages 236–248. Springer, 2016....

    work page doi:10.1007/978-3-319-30139-6_19 2016

  35. [36]

    Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno

    Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno. Sequentially swapping colored tokens on graphs. J. Graph Algorithms Appl., 23(1):3–27,

    work page

  36. [37]

    doi:10.7155/jgaa.00482

    work page doi:10.7155/jgaa.00482

  37. [38]

    Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

    Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theor. Comput. Sci., 586:81–94, 2015. doi:10.1016/j.tcs. 2015.01.052

    work page doi:10.1016/j.tcs 2015

  38. [39]

    Mark Keil, David G

    Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David G. Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, and Yushi Uno. Swapping colored tokens on graphs.Theor. Comput. Sci., 729:1–10, 2018. doi:10.1016/j.tcs.2018.03.016. 21

    work page doi:10.1016/j.tcs.2018.03.016 2018