Planar Disjoint Paths, Treewidth, and Kernels

In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a set of k vertex pairs $\left(s_{i}, t_{i}\right)$ and the task is to find k pairwise vertex-disjoint paths such that the i-th path connects $s_{i}$ to $t_{i}$. We study the problem through the lens of kernelization, aiming at efficiently reducing the input size in terms of a parameter. We show that PLANAR DISJOINT PATHS does not admit a polynomial kernel when parameterized by k unless coNP $\subseteq \mathrm{NP} /$ poly, resolving an open problem by [Bodlaender, Thomassé, Yeo, ESA’09]. Moreover, we rule out the existence of a polynomial Turing kernel unless the WKhierarchy collapses. Our reduction carries over to the setting of edge-disjoint paths, where the kernelization status remained open even in general graphs. On the positive side, we present a polynomial kernel for PLANAR DISJOINT PATHS parameterized by $k+\mathrm{tw}$, where tw denotes the treewidth of the input graph. As a consequence of both our results, we rule out the possibility of a polynomialtime (Turing) treewidth reduction to $t w=k^{\mathcal{O}(1)}$ under the same assumptions. To the best of our knowledge, this is the first hardness result of this kind. Finally, combining our kernel with the known techniques [Adler, Kolliopoulos, Krause, Lokshtanov, Saurabh, Thilikos, JCTB’17; Schrijver, SICOMP’94] yields an alternative (and arguably simpler) proof that PLANAR DISJOINT PATHS can be solved in time $2^{\mathcal{O}\left(k^{2}\right)} \cdot n^{\mathcal{O}(1)}$, matching the result of [Lokshtanov, Misra, Pilipczuk, Saurabh, Zehavi, STOC’20].

Authors

• Michal Wlodarczyk 0001
• Meirav Zehavi

Keywords

• Steiner trees
• Computer science
• Directed graphs
• Approximation algorithms
• Kernel
• Task analysis
• Optimization
• Hardness
• Undirected
• Polynomial Kernel
• Planar Graphs
• Estimation Algorithm
• Ring Structure
• Complex Parameters
• Problem Parameters
• Polynomial-time Algorithm
• Multiple Edges
• Winding Number
• Flow Units
• Class Of Graphs
• Distinct Vertices
• Multigraph
• Pair Of Edges
• Internal Face
• Terminal Pair
• Minimum Cut
• Radial Diameter
• Dual Graph
• Areas Of Computer Science
• parameterized complexity
• disjoint paths
• treewidth
• kernelization