The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable

摘要

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 time nO(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.