An exponential time parameterized algorithm for planar disjoint paths

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, { s i , t i } i =1 k , and the task is to find k pairwise vertex-disjoint paths such that the i ’th path connects s i to t i . In this paper, we give a parameterized algorithm with running time 2 O ( k 2 ) n O (1) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

Authors

• Daniel Lokshtanov
• Pranabendu Misra
• Michal Pilipczuk
• Saket Saurabh 0001
• Meirav Zehavi

Keywords

• disjoint paths
• homology
• network flow
• parameterized complexity
• planar graphs