Half-integral linkages in highly connected directed graphs

Abstract

We study the half-integral $k$-Directed Disjoint Paths Problem ($\frac{1}{2}$kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$, and the input graph is $L$-strongly connected, for any $L\ge 1$. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\ge 2$ there exists $L(k)$ such that $\frac{1}{2}$kDDPP is solvable in time $O(|V(G){|}^c)$ for a $L(k)$-strongly connected directed graph $G$. As the function $L(k)$ grows rather quickly, we also show that $\frac{1}{2}$kDDPP is solvable in time $O(|V(G){|}^{f(k)})$ in $(36k^3+2k)$-strongly connected directed graphs. We also show that for each $\epsilon <1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $\epsilon k$.

20 pages