Half-integral linkages in highly connected directed graphs

Katherine Edwards, Irene Muzi, Paul Wollan

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 in…