KAIST Discrete Math Seminar

The k disjoint paths problem, which was shown to be efficiently solvable for fixed k in undirected graphs in a breakthrough result by Robertson and Seymour, is notoriously difficult in directed graphs. In directed graphs, he problem is NP-complete even in the case when k=2. In an attempt to make the problem more tractable, Thomassen conjectured that if a digraph G were sufficiently strongly connected, then every k disjoint paths problem in G would be feasible. He later answered his conjecture in the negative, showing that the problem remains NP-complete when k=2, even when we assume that the graph is arbitrarily highly connected.

We consider the following further relaxation of the problem: a half-integral solution to a k disjoint paths problem is a set of paths linking the desired vertices such that each vertex of the graph is in at most two of the paths. We will present the new result that the half-integral k disjoint paths problem can be efficiently solved (even when the parameter k is included as part of the input!) if we assume the graph is highly connected.

This is joint work with Irene Muzi and Katherine Edwards.