Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Length-Bounded Cuts and Flows
Author(s): Baier, Georg
Erlebach, Thomas
Hall, Alexander
Köhler, Ekkehard
Schilling, Heiko
Skutella, Martin
Type: Research Paper
Abstract: 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≤4. We show that the minimum length-bounded cut problem turns out to be NP-hard to approximate within a factor of 1.1377 for L≥5 in the case of node-cuts and for L≥4 in the case of edge-cuts (both in graphs with unit edge lengths). We also give approximation algorithms of ratio min{L,n/L} in the node case and min{L,n2/L2,√m} 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 O(log 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 Ω(√n). 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.
Subject(s): approximation algorithms
hardness of approximation
length-bounded cuts
length-bounded edge-disjoint paths
multi-commodity flows
Issue Date: 2006
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 68R10 Graph theory
90C27 Combinatorial optimization
68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2006, 05
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 250.07 kB
DownloadShow Preview
Format: Unknown | Size: 174.62 kB
Format: Unknown | Size: 204.31 kB
Format: Postscript | Size: 517.79 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.