Complexity and Approximability of k-Splittable Flows
dc.contributor.author | Koch, Ronald | |
dc.contributor.author | Spenke, Ines | |
dc.date.accessioned | 2021-12-17T10:06:20Z | |
dc.date.available | 2021-12-17T10:06:20Z | |
dc.date.issued | 2005 | |
dc.description.abstract | Let G=(V,E) be a graph with a source node s and a sink node t, |V| = n, |E|= m. For a given number k, the Maximum k-Splittable Flow Problem (MkSF) is to find an s,t-flow of maximum value with a flow decomposition using at most k paths. In the multicommodity case this problem generalizes disjoint paths problems and unsplittable flow problems. We provide a comprehensive overview of the complexity and approximability landscape of MkSF on directed and undirected graphs. We consider constant values of k and k depending on graph parameters. For arbitrary constant values of k, we prove that the problem is strongly NP-hard on directed and undirected graphs already for k=2. This extends a known NP-hardness result for directed graphs that could not be applied to undirected graphs. Furthermore, we show that MkSF cannot be approximated with a performance ratio better than 5/6. This is the first constant bound given for this value. For non constant values of k, the polynomially solvability was known before for all k >= m, but open for smaller k. We prove that MkSF is NP-hard for all k fulfilling 2 <= k <= m-n+1 (for n >= 3). For all other values of k the problem is shown to be polynomially solvable. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15553 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14326 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | network flows | en |
dc.subject.other | k-splittable flows | en |
dc.subject.other | complexity | en |
dc.subject.other | approximability | en |
dc.subject.other | s, t-flow | en |
dc.title | Complexity and Approximability of k-Splittable Flows | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 2005, 29 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
tub.subject.msc2000 | 90C60 Abstract computational complexity for mathematical programming problems | en |