SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES

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

Research output: Contribution to journalArticlepeer-review

7 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 languageEnglish
Pages (from-to)1102-1123
Number of pages22
JournalSIAM Journal on Discrete Mathematics
Volume36
Issue number2
DOIs
Publication statusPublished - 2022

Keywords

  • combinatorial reconfiguration
  • combinatorial shortest paths
  • graph algorithms
  • matching

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES'. Together they form a unique fingerprint.

Cite this