The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable
Cygan, Marek · Marx, Dániel · Pilipczuk, Marcin · Pilipczuk, Michał
Original · EN
Given a graph G and k pairs of vertices (s₁,t₁),..., (sₖ,tₖ), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P₁,..., Pₖ such that Pᵢ goes from sᵢ to tᵢ. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time nᵒ⁽ᵏ⁾. We give an algorithm with running time 2²ᵒ⁽ᵏ²⁾ nᵒ⁽¹⁾ for the problem, that is, we show the fixed-parameter tractability of the problem.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.