2016/11/03 by Edwards, Katherine, Muzi, Irene, Wollan, Paul · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1611.01004
We study the half-integral k-Directed Disjoint Paths Problem (\tfrac12kDDPP) 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≥ 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≥ 2 there exists L(k) such that \tfrac12kDDPP 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 \tfrac12kDDPP is solvable in time O(|V(G)|f(k)) in (36k3+2k)-strongly connected directed graphs. We also show that for each ε<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 εk.