The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable
Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk · 2013
Given a graph G and k pairs of vertices (s1, t1), ..., (sk, tk), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P1, ..., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in timenO(k). We give an algorithm with running time 22O(k2)* nO(1)for the problem, that is, we show the fixed-parameter tractability of the problem.