Approximation and complexity of k-splittable flows

Ronald Koch, Martin Skutella, and Ines Spenke

not available

not available

Given a graph with a source and a sink node, the maximum k-splittable flow (MkSF) problem is to find a flow of maximum value with a flow decomposition using at most k paths. In the more general context of multicommodity flows, this NP-hard problem has been introduced by Baier, Koehler, and Skutella. It generalizes disjoint paths problems and unsplittable flows. A particularly interesting aspect of this problem is that its solution requires both packing and routing strategies. The total flow has to be divided into k packets which then have to be routed along certain paths of the given graph. The main contributions of this paper are as follows:

(i) We show that for constant~k an optimum packing can be found in polynomial time by trying polynomially many alternatives. If k is part of the input, the packing problem can be solved approximately within arbitrary precision in polynomial time. This result is based on the observation that approximate flows only require constantly many different flow values. The latter observation is of interest in its own right.

(ii) Based on (i), we prove that, for constant k, the MkSF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it. To the best of our knowledge, NP-hard flow problem have not been studied on graphs of bounded treewidth before.

(iii) Last but not least, we provide a comprehensive overview of the complexity and approximability landscape of k-splittable flows for varying values of k.

Download as [PDF] [ps.gz] [ps]