On packing connectors (Q1272488)

Let \(G=(V,E)\) be an undirected graph and \(\{S,T\}\) a partition of \(V\). Then a set of edges \(F\subseteq E\) such that every component of the subgraph \((V,F)\) intersects both \(S\) and \(T\), is called an \(S\)--\(T\) connector. In general a subpartition \(W\) of a set \(X\) is a collection of pairwise disjoint nonempty subsets of \(X\); and if---like in the present case---\(W=\{U_1, \dots, U_t\}\) is a subpartition of \(S\) or \(T\), then \(\delta(W)\) denotes the set of edges with one end in \(U_i\) and one end in \(V\setminus U_i\) for some index \(i\). The main result of this paper is Theorem 1: \(G\) contains \(k\) edge-disjoint \(S\)--\(T\) connectors iff \(|\delta (W)|\geq k\cdot | W|\) for every subpartition \(W\) of \(S\) or \(T\), where \(k\) is a natural number. This result is a generalization of a theorem on (i) disjoint edge covers in a bipartite graph (König/Gupta), and (ii) disjoint spanning trees in an undirected graph (Tutte/Nash-Williams), stated here as Lemma 1. According to the concept of \(S\)--\(T\) connector in undirected graphs the \(S\)--\(T\) bibranching is defined in directed graphs and a result of Schrijver with respect to packing bibranches is given as Lemma 2. The proof of Theorem 1 follows essentially by combining both these lemmas. Simultaneously this proof yields the basis for a polynomial algorithm for packing \(S\)--\(T\) connectors not described in the present paper. Finally, in Section 3, it is shown that Theorem 1 implies the integer rounding property for a set of linear inequalities associated with packing \(S\)--\(T\) connectors. The polyhedral formulation of this fact is given in Theorem 2.