An approximate max-Steiner-tree-packing min-Steiner-cut theorem
Lap Chi Lau
University of Toronto

Date: Friday December 10, 2004
Time 11-12
Venue: Room TBA, HKUST


Abstract
Given an undirected multigraph G and a subset of vertices S, the
Steiner Tree Packing problem is to find a largest collection of
edge-disjoint trees that each connects S.  This problem and its
generalization 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 work, 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.

(A preliminary version appears in Proceedings of FOCS 2004)