direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 19-2004

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Approximation and complexity of k-splittable flows
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe