2022/10/21 by Ito, Takehiro, Iwamasa, Yuni, Kakimura, Naonori +5
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2210.11778
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.