2026-07-26T00:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18133 2024-03-06T11:01:06Z ddc:004 open_access

Rerouting Planar Curves and Disjoint Paths Ito, Takehiro Iwamasa, Yuni Kakimura, Naonori Kobayashi, Yusuke Maezawa, Shun-ichi Nozaki, Yuta Okamoto, Yoshio Ozeki, Kenta Disjoint paths combinatorial reconfiguration planar graphs In this paper, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths 𝒫 and 𝒬 connecting the same set of terminal pairs, we aim to determine whether 𝒫 can be transformed to 𝒬 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 𝒫 and 𝒬 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takehiro Ito and Yuni Iwamasa and Naonori Kakimura and Yusuke Kobayashi and Shun-ichi Maezawa and Yuta Nozaki and Yoshio Okamoto and Kenta Ozeki 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.81 urn:nbn:de:0030-drops-181339 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.81 eng https://creativecommons.org/licenses/by/4.0/legalcode