TY - GEN
T1 - Rerouting Planar Curves and Disjoint Paths
AU - Ito, Takehiro
AU - Kakimura, Naonori
AU - Maezawa, Shun Ichi
AU - Okamoto, Yoshio
AU - Iwamasa, Yuni
AU - Kobayashi, Yusuke
AU - Nozaki, Yuta
AU - Ozeki, Kenta
N1 - Funding Information:
Funding Takehiro Ito: JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814, JP20H05793. Yuni Iwamasa: JSPS KAKENHI Grant Numbers JP20K23323, JP20H05795, JP22K17854. Naonori Kakimura: JSPS KAKENHI Grant Numbers JP20H05795, JP21H03397, JP22H05001. Yusuke Kobayashi: JSPS KAKENHI Grant Numbers JP20K11692, JP20H05795, JP22H05001. Shun-ichi Maezawa: JSPS KAKENHI Grant Numbers JP20H05795, JP22K13956. Yuta Nozaki: JSPS KAKENHI Grant Numbers JP20H05795, JP20K14317, JP23K12974. Yoshio Okamoto: JSPS KAKENHI Grant Numbers JP20H05795, JP20K11670, JP23K10982. Kenta Ozeki: JSPS KAKENHI Grant Numbers JP18K03391, JP19H01803, JP20H05795, 23K03195.
Publisher Copyright:
© Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki.
PY - 2023/7
Y1 - 2023/7
N2 - In this paper, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths P and Q connecting the same set of terminal pairs, we aim to determine whether P can be transformed to Q by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when k = 2. On the other hand, we prove that, when the graph is embedded on a plane and all paths in P and Q connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s-t paths as a variant. We show that the disjoint s-t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.
AB - In this paper, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths P and Q connecting the same set of terminal pairs, we aim to determine whether P can be transformed to Q by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when k = 2. On the other hand, we prove that, when the graph is embedded on a plane and all paths in P and Q connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s-t paths as a variant. We show that the disjoint s-t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.
KW - combinatorial reconfiguration
KW - Disjoint paths
KW - planar graphs
UR - http://www.scopus.com/inward/record.url?scp=85167350932&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85167350932&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2023.81
DO - 10.4230/LIPIcs.ICALP.2023.81
M3 - Conference contribution
AN - SCOPUS:85167350932
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
A2 - Etessami, Kousha
A2 - Feige, Uriel
A2 - Puppis, Gabriele
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Y2 - 10 July 2023 through 14 July 2023
ER -