|
Published Articles >> Table of Contents >> Abstract
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
pp. 61-70
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem
Lap Chi Lau, University of Toronto
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.10
Send link to a friend
| Abstract |
|
Given an undirected multigraph G and a subset of vertices S ⊆ V (G), the STEINER TREE PACKING problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme unless P=NP). In fact, prior to this paper, not even an approximation algorithm with asymptotic ratio o(n) was known despite several attempts. In this work, we close this huge gap by presenting the first polynomial time constant factor approximation algorithm for the STEINER TREE PACKING problem. The main theorem is an approximate min-max relation between the maximum number of edge-disjoint trees that each connects S (i.e. S-trees) and the minimum size of an edge-cut that disconnects some pair of vertices in S (i.e. S-cut). Specifically, we prove that if the minimum S-cut in G has 26k edges, then G has at least k edge-disjoint S-trees; this answers Kriesell's conjecture affirmatively up to a constant multiple. The techniques that we use are purely combinatorial, where matroid theory is the underlying ground work.
|
 Additional Information
|
Citation:
Lap Chi Lau,
"An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem,"
focs,
pp. 61-70,
45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04),
2004
|
|
