Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

[1] O. Aichholzer, J. Cardinal, T. Huynh, K. Knauer, T. Mütze, R. Steiner, and

B. Vogtenhuber, Flip distances between graph orientations, Algorithmica, 83 (2021),

pp. 116–143, https://doi.org/10.1007/s00453-020-00751-1.

[2] O. Aichholzer, W. Mulzer, and A. Pilz, Flip distance between triangulations of a simple

polygon is NP-complete, Discrete Comput. Geom., 54 (2015), pp. 368–389, https://doi.

org/10.1007/s00454-015-9709-7.

[3] A. Y. Alfakih and K. G. Murty, Adjacency on the constrained assignment problem, Discrete

Appl. Math., 87 (1998), pp. 269–274, https://doi.org/10.1016/S0166-218X(98)00063-8.

[4] M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Mühlenthaler, and K. Wasa, The perfect matching reconfiguration problem, in 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019,

Aachen, Germany, P. Rossmanith, P. Heggernes, and J.-P. Katoen, eds., LIPIcs 138,

Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2019, pp. 80:1–

80:14, https://doi.org/10.4230/LIPIcs.MFCS.2019.80, http://www.dagstuhl.de/dagpub/

978-3-95977-117-7.

[5] É. Bonnet, T. Miltzow, and P. Rzążewski, Complexity of token swapping and its variants,

Algorithmica, 80 (2018), pp. 2656–2682, https://doi.org/10.1007/s00453-017-0387-0.

[6] N. Bousquet, T. Hatanaka, T. Ito, and M. Mühlenthaler, Shortest reconfiguration of

matchings, in Graph-Theoretic Concepts in Computer Science—45th International Workshop, WG 2019, Vall de Núria, Spain, Revised Papers, I. Sau and D. M. Thilikos, eds.,

Lecture Notes in Computer Science 11789, Springer-Verlag, Berlin, 2019, pp. 162–174,

https://doi.org/10.1007/978-3-030-30786-8_13.

[7] T. Brunsch and H. Röglin, Finding short paths on polytopes by the shadow vertex algorithm,

in Automata, Languages, and Programming—40th International Colloquium, ICALP 2013,

Riga, Latvia, Proceedings, Part I, F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, and

D. Peleg, eds., Lecture Notes in Computer Science 7965, Springer-Verlag, Berlin, 2013,

pp. 279–290, https://doi.org/10.1007/978-3-642-39206-1_24.

[8] L. Bulteau, G. Fertin, and I. Rusu, Pancake flipping is hard, J. Comput. Syst. Sci., 81

(2015), pp. 1556–1574, https://doi.org/10.1016/j.jcss.2015.02.003.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Downloaded 02/07/23 to 130.54.130.253 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

1122

ITO, KAKIMURA, KAMIYAMA, KOBAYASHI, AND OKAMOTO

[9] V. Chvátal, On certain polytopes associated with graphs, J. Comb. Theory Ser. B, 18 (1975),

pp. 138–154, https://doi.org/10.1016/0095-8956(75)90041-6.

[10] S. Fiorini, A combinatorial study of partial order polytopes, Eur. J. Comb., 24 (2003), pp. 149–

159, https://doi.org/10.1016/S0195-6698(03)00009-X.

[11] A. M. Frieze and S.-H. Teng, On the complexity of computing the diameter of a polytope,

Comput. Complexity, 4 (1994), pp. 207–219, https://doi.org/10.1007/BF01206636.

[12] M. R. Garey, D. S. Johnson, and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5 (1976), pp. 704–714, https://doi.org/10.1137/

0205049.

[13] D. Geist and E. Y. Rodin, Adjacency of the 0-1 knapsack problem, Comput. Oper. Res., 19

(1992), pp. 797–800, https://doi.org/10.1016/0305-0548(92)90019-2.

[14] M. Gupta, H. Kumar, and N. Misra, On the complexity of optimal matching reconfiguration, in SOFSEM 2019: Theory and Practice of Computer Science—45th International Conference on Current Trends in Theory and Practice of Computer Science,

Nový Smokovec, Slovakia, Proceedings, B. Catania, R. Královic, J. R. Nawrocki, and

G. Pighizzini, eds., Lecture Notes in Computer Science 11376, Springer-Verlag, Berlin,

2019, pp. 221–233, https://doi.org/10.1007/978-3-030-10801-4_18.

[15] J. van den Heuvel, The complexity of change, in Surveys in Combinatorics 2013, S. R.

Blackburn, S. Gerke, and M. Wildon, eds., London Mathematical Society Lecture Note

Series 409, Cambridge University Press, Cambridge, 2013, pp. 127–160, https://doi.org/

10.1017/CBO9781139506748.005.

[16] T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara,

and Y. Uno, On the complexity of reconfiguration problems, Theoret. Comput. Sci., 412

(2011), pp. 1054–1065, https://doi.org/10.1016/j.tcs.2010.12.005.

[17] T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto, Reconfiguration

of maximum-weight b-matchings in a graph, J. Comb. Optim., 37 (2019), pp. 454–464,

https://doi.org/10.1007/s10878-018-0289-3.

[18] T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto, Shortest reconfiguration of perfect matchings via alternating cycles, in 27th Annual European Symposium on Algorithms, ESA 2019, Munich/Garching, Germany, M. A. Bender, O. Svensson, and G. Herman, eds., LIPIcs 144, Schloss Dagstuhl—Leibniz-Zentrum für Informatik,

Dagstuhl, Germany, 2019, pp. 61:1–61:15, https://doi.org/10.4230/LIPIcs.ESA.2019.61,

http://www.dagstuhl.de/dagpub/978-3-95977-124-5.

[19] M. Johnson, D. Kratsch, S. Kratsch, V. Patel, and D. Paulusma, Finding shortest

paths between graph colourings, Algorithmica, 75 (2016), pp. 295–321, https://doi.org/10.

1007/s00453-015-0009-7.

[20] M. Kamiński, P. Medvedev, and M. Milanič, Complexity of independent set reconfigurability problems, Theoret. Comput. Sci., 439 (2012), pp. 9–15, https://doi.org/10.1016/j.

tcs.2012.03.004.

[21] J. Kawahara, T. Saitoh, and R. Yoshinaka, The time complexity of permutation routing

via matching, token swapping and a variant, J. Graph Algorithms Appl., 23 (2019), pp. 29–

70, https://doi.org/10.7155/jgaa.00483.

[22] A. Lubiw and V. Pathak, Flip distance between two triangulations of a point set is NPcomplete, Comput. Geom., 49 (2015), pp. 17–23, https://doi.org/10.1016/j.comgeo.2014.

11.001.

[23] T. Matsui, NP-completeness of non-adjacency relations on some 0-1 polytopes, Mathematical

Engineering Technical Reports METR-94-12, University of Tokyo, 1994.

[24] T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, and T. Uno, Approximation and hardness of token swapping, in 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, P. Sankowski and C. D. Zaroliagis, eds., LIPIcs 57,

Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2016, pp. 66:1–

66:15, https://doi.org/10.4230/LIPIcs.ESA.2016.66.

[25] A. E. Mouawad, N. Nishimura, V. Pathak, and V. Raman, Shortest reconfiguration paths

in the solution space of Boolean formulas, SIAM J. Discrete Math., 31 (2017), pp. 2185–

2200, https://doi.org/10.1137/16M1065288.

[26] M. Mühlenthaler, Degree-constrained subgraph reconfiguration is in P, in Mathematical

Foundations of Computer Science 2015—40th International Symposium, MFCS 2015, Milan, Italy, Proceedings, Part II, G. F. Italiano, G. Pighizzini, and D. Sannella, eds.,

Lecture Notes in Computer Science 9235, Springer-Verlag, Berlin, 2015, pp. 505–516,

https://doi.org/10.1007/978-3-662-48054-0_42.

[27] D. Naddef, The Hirsch conjecture is true for (0, 1)-polytopes, Math. Program., 45 (1989),

pp. 109–110, https://doi.org/10.1007/BF01589099.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Downloaded 02/07/23 to 130.54.130.253 . Redistribution subject to SIAM license or copyright; see https://epubs.siam.org/terms-privacy

SHORTEST RECONFIGURATION OF PERFECT MATCHINGS

1123

[28] N. Nishimura, Introduction to reconfiguration, Algorithms, 11 (2018), 52, https://doi.org/

10.3390/a11040052.

[29] C. H. Papadimitriou, The adjacency relation on the traveling salesman polytope is NPcomplete, Math. Program., 14 (1978), pp. 312–324, https://doi.org/10.1007/BF01588973.

[30] A. Pilz, Flip distance between triangulations of a planar point set is APX-hard, Comput.

Geom., 47 (2014), pp. 589–604, https://doi.org/10.1016/j.comgeo.2014.01.001.

[31] J. Plesník, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with

degree bound two, Inform. Process. Lett., 8 (1979), pp. 199–201, https://doi.org/10.1016/

0020-0190(79)90023-1.

[32] D. Ratner and M. K. Warmuth, Finding a shortest solution for the N ×N extension of

the 15-PUZZLE is intractable, in Proceedings of the 5th National Conference on Artificial

Intelligence, Philadelphia, 1986, Volume 1: Science, T. Kehler, ed., Morgan Kaufmann,

Burlington, MA, 1986, pp. 168–172.

[33] L. Sanità, The diameter of the fractional matching polytope and its hardness implications, in

59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris,

M. Thorup, ed., IEEE Computer Society, Washington, DC, 2018, pp. 910–921, https:

//doi.org/10.1109/FOCS.2018.00090.

[34] F. Santos, A counterexample to the Hirsch conjecture, Ann. Math., 176 (2012), pp. 383–412,

https://doi.org/10.4007/annals.2012.176.1.7.

[35] N. Sukegawa, An asymptotically improved upper bound on the diameter of polyhedra, Discrete

Comput. Geom., 62 (2019), pp. 690–699, https://doi.org/10.1007/s00454-018-0016-y.

[36] T. Yamada and R. Uehara, Shortest reconfiguration of sliding tokens on subclasses of interval graphs, Theoret. Comput. Sci., 863 (2021), pp. 53–68, https://doi.org/10.1016/j.tcs.

2021.02.019.

[37] K. Yamanaka, E. D. Demaine, T. Horiyama, A. Kawamura, S.-I. Nakano,

Y. Okamoto, T. Saitoh, A. Suzuki, R. Uehara, and T. Uno, Sequentially swapping colored tokens on graphs, J. Graph Algorithms Appl., 23 (2019), pp. 3–27, https:

//doi.org/10.7155/jgaa.00482.

[38] K. Yamanaka, E. D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto,

T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno, Swapping labeled tokens on graphs,

Theoret. Comput. Sci., 586 (2015), pp. 81–94, https://doi.org/10.1016/j.tcs.2015.01.052.

[39] K. Yamanaka, T. Horiyama, J. M. Keil, D. G. Kirkpatrick, Y. Otachi, T. Saitoh,

R. Uehara, and Y. Uno, Swapping colored tokens on graphs, Theoret. Comput. Sci.,

729 (2018), pp. 1–10, https://doi.org/10.1016/j.tcs.2018.03.016.

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

...