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

Given a graph G and k pairs of vertices (s₁, t₁), ..., (s_k, t_k), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P₁, ..., 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 2^2O(k2) * n^O(1) for the problem, that is, we show the fixed-parameter tractability of the problem.