License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.81
URN: urn:nbn:de:0030-drops-181339
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18133/
Go to the corresponding LIPIcs Volume Portal

Ito, Takehiro ; Iwamasa, Yuni ; Kakimura, Naonori ; Kobayashi, Yusuke ; Maezawa, Shun-ichi ; Nozaki, Yuta ; Okamoto, Yoshio ; Ozeki, Kenta

Rerouting Planar Curves and Disjoint Paths

pdf-format:
LIPIcs-ICALP-2023-81.pdf (1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ito_et_al:LIPIcs.ICALP.2023.81,
  author =	{Ito, Takehiro and Iwamasa, Yuni and Kakimura, Naonori and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta},
  title =	{{Rerouting Planar Curves and Disjoint Paths}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{81:1--81:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18133},
  URN =		{urn:nbn:de:0030-drops-181339},
  doi =		{10.4230/LIPIcs.ICALP.2023.81},
  annote =	{Keywords: Disjoint paths, combinatorial reconfiguration, planar graphs}
}

Keywords: Disjoint paths, combinatorial reconfiguration, planar graphs
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI