An approximate max-Steiner-tree-packing min-Steiner-cut theorem

摘要

Given an undirected multigraph G and a subset of vertices S /spl sube/ 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.