A graph reduction step preserving element-connectivity and packing steiner trees and forests

Given an undirected graph G = (V,E) and a subset of vertices called terminals T ⊆ V , the element-connectivity k_G(u, v) of two terminals u, v ∈ T is the maximum number of u-v paths that are pairwise element-disjoint, that is, disjoint in both edges and nonterminals V \ T. (Elementconnectivity was first (implicitly) defined by Frank, Ibaraki, and Nagamochi in [J. Graph Theory, 17 (1993), pp. 275.281].) (Element-disjoint paths need not be disjoint in terminals.) Hind and Oellermann [Congr. Numer., 113 (1996), pp. 179.204] gave a graph reduction step that preserves the global element-connectivity of the terminals. We show that one can also apply such a reduction step while preserving local connectivity, that is, all the pairwise element-connectivities of the terminals. We illustrate the usefulness of this more general reduction step by giving applications to packing element-disjoint Steiner trees and forests: Given a graph G and disjoint terminal sets T1, T2, . . . , Th, we seek a maximum number of element-disjoint Steiner forests where each forest connects each Ti. We prove that if each Ti is k-element-connected, then there exist ω( k/log |T| log h ) element-disjoint Steiner forests, where T = U_i T_i. If G is planar (or has fixed genus), we show that there exist ω(k) Steiner forests. Our proofs are constructive, giving poly-time algorithms to find these forests; these are the first nontrivial algorithms for packing element-disjoint Steiner forests.