SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES∗

I. T.O. Takehiro; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

doi:10.1137/20M1364370

SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES^∗

I. T.O. Takehiro, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1102-1123
Number of pages	22
Journal	SIAM Journal on Discrete Mathematics
Volume	36
Issue number	2
DOIs	https://doi.org/10.1137/20M1364370
Publication status	Published - 2022

Keywords

combinatorial reconfiguration
combinatorial shortest paths
graph algorithms
matching

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1137/20M1364370

Cite this

@article{0301369184894483a85d40a0efc01baf,

title = "SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES∗",

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.",

keywords = "combinatorial reconfiguration, combinatorial shortest paths, graph algorithms, matching",

author = "Takehiro, {I. T.O.} and Naonori Kakimura and Naoyuki Kamiyama and Yusuke Kobayashi and Yoshio Okamoto",

note = "Funding Information: ∗Received by the editors September 3, 2020; accepted for publication (in revised form) November 2, 2021; published electronically April 28, 2022. A preliminary version has appeared in the Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). https://doi.org/10.1137/20M1364370 Funding: The first author was partially supported by JST CREST grant JPMJCR1402 and JSPS KAKENHI grants JP18H04091, JP19K11814, and JP20H05793, Japan. The second author was partially supported by JSPS KAKENHI grants JP17K00028, JP18H05291, and JP20H05795, Japan. The third author was partially supported by JST PRESTO grant JPMJPR1753, Japan. The fourth author was partially supported by JSPS KAKENHI grants JP16K16010, JP17K19960, JP18H05291, and JP20H05795, Japan. The fifth author was partially supported by JSPS KAKENHI grants JP15K00009, JP20K11679, and JP20H05795; JST CREST grant JPMJCR1402; and the Kayamori Foundation of Informational Science Advancement, Japan. Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics",

year = "2022",

doi = "10.1137/20M1364370",

language = "English",

volume = "36",

pages = "1102--1123",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES∗

AU - Takehiro, I. T.O.

AU - Kakimura, Naonori

AU - Kamiyama, Naoyuki

AU - Kobayashi, Yusuke

AU - Okamoto, Yoshio

N1 - Funding Information: ∗Received by the editors September 3, 2020; accepted for publication (in revised form) November 2, 2021; published electronically April 28, 2022. A preliminary version has appeared in the Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). https://doi.org/10.1137/20M1364370 Funding: The first author was partially supported by JST CREST grant JPMJCR1402 and JSPS KAKENHI grants JP18H04091, JP19K11814, and JP20H05793, Japan. The second author was partially supported by JSPS KAKENHI grants JP17K00028, JP18H05291, and JP20H05795, Japan. The third author was partially supported by JST PRESTO grant JPMJPR1753, Japan. The fourth author was partially supported by JSPS KAKENHI grants JP16K16010, JP17K19960, JP18H05291, and JP20H05795, Japan. The fifth author was partially supported by JSPS KAKENHI grants JP15K00009, JP20K11679, and JP20H05795; JST CREST grant JPMJCR1402; and the Kayamori Foundation of Informational Science Advancement, Japan. Publisher Copyright: © 2022 Society for Industrial and Applied Mathematics

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - combinatorial reconfiguration

KW - combinatorial shortest paths

KW - graph algorithms

KW - matching

UR - http://www.scopus.com/inward/record.url?scp=85130585783&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85130585783&partnerID=8YFLogxK

U2 - 10.1137/20M1364370

DO - 10.1137/20M1364370

M3 - Article

AN - SCOPUS:85130585783

SN - 0895-4801

VL - 36

SP - 1102

EP - 1123

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -