Disjoint paths and the Grid Theorem in Digraphs

Abstract

In parameterized complexity, it is often the case that FPT problems in undirected graphs become W[1]-hard when translated to the directed setting. The DIRECTED DISJOINT PATHS problem, a notoriously hard problem in digraphs, is a classical example of this: Robertson and Seymour [1] showed that undirected version is FPT when parameterized by the number k of requests but, on the other hand, Fortune et al. [2], showed that the directed version is NP-complete for fixed k = 2 and Slivkins [3] showed that it is W[1]-hard with parameter k even when restricted to acyclic digraphs. In this thesis, we provide two new results regarding parameterized complexityin digraphs. First, we show how to adapt the Directed Grid Theorem by Kawarabayashi and Kreutzer [4], a result analogous to the celebrated Grid Theorem by Robertson and Seymour [5], into an FPT algorithm. Then, we introduce a novel relaxation for DIRECTED DISJOINT PATHS in which we only require the paths to behave properly not in the whole digraph, but in an unspecified part of size prescribed by a parameter. Namely, in the DISJOINT ENOUGH DIRECTED PATHS problem, given a digraph D together with a set of k pairs of vertices (the requests) and two non-negative integers k and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. Amongst other algorithmic and hardness we show that this problem has a kernel in general digraphs. This result has consequences for the STEINER NETWORK problem: we show that it is FPT parameterized by the number k of terminals and p, where p = n − q and q is the size of the solution.