An approximate max-Steiner-tree-packing min-Steiner-cut theorem (Q925137): Difference between revisions

Given an undirected multigraph \(G\) and a subset of vertices \(S\leq V(G)\), the Steiner tree packing problem is to find a largest collection of edge-disjoint tree that each connect \(S\). \(S\)-cut is a subset of edges whose removal disconnects some vertices in \(S\). We say a graph is \((k-S)\)-connected if every \(S\)-cut has at least \(k\)-edges. Author proves that if \(G\) is \((2k-S)\)-connected, then \(G\) has \(k\)-edge-disjoint trees. The proof is constructive, so if \(G\) is \((26k-S)\)-connected, then a collection of \(k\)-edge-disjoint \(S\)-tree can be constructed in polynomial time. It is a first polynomial time constant factor approximation algorithm for the Steiner tree packing problem.