Computing and Informatics

Given a graph G=(V, E) and k source-sink pairs (s_1, t_1), dots, (s_k, t_k) with each s_i, t_i in V, the Min-Sum Disjoint Paths problem asks to find k disjoint paths connecting all the source-sink pairs with minimized total length, while the Min-Max Disjoint Paths problem asks for k disjoint paths connecting all the source-sink pairs with minimized length of the longest path. We show that the weighted Min-Sum Disjoint Paths problem is rm FP rm NP-complete in general graphs, and the unweighted Min-Sum Disjoint Paths problem and the unweighted Min-Max Disjoint Paths problem cannot be approximated within Omega(m1- epsilon) for any constant epsilon > 0 even in planar graphs, assuming rm P neq rm NP, where m is the number of edges in G. We give for the first time a simple bicriteria approximation algorithm for the unweighted Min-Max Edge-Disjoint Paths problem and the weighted Min-Sum Edge-Disjoint Paths problem, with guaranteed approximation ratio O(łog k / łog łog k) and O(1), respectively.