direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2006

Length-Bounded Cuts and Flows
Zitatschlüssel Report-005-2006
Autor Georg Baier and Thomas Erlebach and Alexander Hall and Ekkehard Köhler and Heiko Schilling and Martin Skutella
Jahr 2006
Adresse Strasse des 17. Juni 136, 10623 Berlin
Nummer 005
Monat February
Notiz ICALP 2006
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung An $L$-length-bounded cut in a graph $G$ with source $s$, and sink $t$ is a cut that destroys all $s$-$t$-paths of length at most $L$. An $L$-length-bounded flow is a flow in which only flow paths of length at most $L$ are used. The first research on path related constraints we are aware of was done in 1978 by Lovász, Neumann Lara, and Plummer. Among others they show that the minimum length-bounded node-cut problem is polynomial for $Lłe 4$. We show that the minimum length-bounded cut problem turns out to be $\mathcalNP$-hard to approximate within a factor of at least $1.1377$ for $L\ge 5$ in the case of node-cuts and for $L\ge 4$ in the case of edge-cuts (both in graphs with unit edge lengths). We also give approximation algorithms of ratio $\minŁ,n/L\$ in the node case and $\minŁ,n^2/L^2,\sqrtm\$ in the edge case, where $n$ denotes the number of nodes and $m$ denotes the number of edges. For classes of graphs such as constant degree expanders, hypercubes, and butterflies, we obtain $\mathcalO\!(łog n)$-approximations by using the Shortening Lemma for flow numbers [Kolman and Scheideler, SODA'02]. We discuss the integrality gaps of the LP relaxations of length-bounded flow and cut problems, which can be of size $Ømega(\sqrtn)$. We show that edge- and path-flows are not polynomially equivalent for length-bounded flows, analyze the structure of optimal solutions and give instances where each maximum flow ships a large percentage of the flow along paths with an arbitrarily small flow value.
Link zur Publikation Download Bibtex Eintrag