2015/12/06 by Ene, Alina, Mnich, Matthias, Pilipczuk, Marcin +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1512.01829
We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M = \(s1, t1), …, (sk, tk)\. The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (si, ti) ∈ M', there is a path in P connecting si to ti. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP. In this paper we obtain an O(r3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r ⋅ 3r) approximation for MaxEDP.