Rerouting Planar Curves and Disjoint Paths

MaRDI QIDQ6414640zbMATH OpenFDO

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

Publication date 21 October 2022

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 $mathcalP$ and $mathcalQ$ connecting the same set of terminal pairs, we aim to determine whether $mathcalP$ can be transformed to $mathcalQ$ 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 $mathcalP$ and $mathcalQ$ 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.

This page was built for publication: Rerouting Planar Curves and Disjoint Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414640)