18.997 Topics in Combinatorial Optimization: Lecture 20 Notes

18.997 Topics in Combinatorial Optimization April 27, 2004 Lecture 20 1 k-arc-connected orientations We continue the discussion of how a 2k-edge-connected graph can be oriented so that the resulting digraph is k-arc-connected. Last time we have seen that this can be achieved using submodular flows. Today we present a different approach, which relates the problem to matroid intersection. Let G = (V, E) be a 2k-edge-connected graph and let D = (V, A) denote the bidirected version of G, with two arcs (u, v) and (v, u) for each edge {u, v}. (All graphs in this lecture can be multigraphs.) We define two matroids on the ground set of arcs A. The first one is a partition matroid: M1 = (A, {B ⊆ A : ∀edge (u, v); B contains at most one of the arcs (u, v), (v, u)}). The bases of M1 are exactly the orientations of G. The second matroid, which will force the orientation to be k-arc-connected, is more involved. Define • H(U ) = {(v, u) ∈ A : u ∈ U } • C = {H(U ) : ∅ ⊂ U ⊂ V } • f (H(U )) = |E(U )| + |δ(U )| − k = |E| − |E(V \ U )| − k In other words, H(U ) is the set of arcs with their “head” in U (either crossing the cut into U or contained inside U ), and f (H(U )) is the maximum number of edges oriented like this, so that k arcs leaving U are still available. Note that C forms a crossing family: ∀H1 , H2 ∈ C; H1 ∩ H2 = ∅, H1 ∪H2 = A ⇒ H1 ∩H2 ∈ C, H1 ∪H2 ∈ C. This is simply because H(U1 )∩H(U2 ) = H(U1 ∩U2 ) and H(U1 )∪H(U2 ) = H(U1 ∪U2 ). Also, f (H(U )) = |E|−|E(V \U )|−k is a crossing submodular function on C: since |E(V \U1 )|+|E(V \U2 )| ≤ |E(V \(U1 ∩U2 ))|+E(V \(U1 ∪U2 ))|, f (H1 ∩H2 )+f (H1 ∪H2 ) ≤ f (H1 ) + f (H2 ). Given these properties, we shall prove that M2 = (A, {B ⊆ A : |B| ≤ |E| & ∀H ∈ C; |B ∩ H| ≤ f (H)}) is a matroid. Then, k-arc-connected orientations correspond exactly to common bases of M1 ∩ M2 : bases of M1 are orientations of G, and an orientation is a base of M2 if and only if it has at most δ(U ) − k arcs across any directed cut δ in (U ), i.e. it must have at least k arcs across δ out (U ). Therefore a k-arc-connected orientation can be found using matroid intersection. 1 It remains to prove that M2 is a matroid. This is implied by the following lemma. Lemma 1 Let C ⊆ 2A be a crossing family and f : C → Z a crossing submodular function. Then for any k ∈ Z+ , B = {B ⊆ A : |B| = k & ∀H ∈ C; |B ∩ H| ≤ f (H)} are the bases of a matroid. Proof: We have to prove the exchange property for B. Let B1 , B2 ∈ B, i ∈ B1 \B2 and j ∈ B2 \B1 . If B1 − i + j ∈ / B, it means that for some H ∈ C, |B1 ∩ H| = f (H), i ∈ / H and j ∈ H, so that we violate the condition by exchanging j for i. Assume that this holds for every j ∈ B2 \ B1 . 1 provided that membership in M2 can be tested efficiently, which is not explained here. 20-1 For each j ∈ B2 \ B1 , let Hj ∈ C be the maximal set such that i ∈ / Hj , j ∈ Hj and |B1 ∩ Hj | = f (Hj ). These sets are disjoint; if Hj ∩ Hj � = ∅ and |B1 ∩ Hj | = f (Hj ), |B1 ∩ Hj � | = f (Hj � ), then by crossing submodularity |B1 ∩ (Hj ∪ Hj � )| = f (Hj ∪ Hj � ) which contradicts the maximality ofHj and Hj � . Let P = {Hj : j ∈ B2 \ B1 } denote the collection of these disjoint sets, and W = A \ P the set of remaining uncovered elements. For each Hj ∈ P, we have |B2 ∩ Hj | ≤ f (Hj ) = |B1 ∩ Hj |. All the elements of B2 \ B1 are covered by P, so B2 ∩ W ⊆ B1 ∩ W , and there is an element i ∈ W which belongs to B1 but not B2 . Therefore |B2 ∩ W | < |B1 ∩ W | and |B2 | < |B1 | which is a contradiction. � 2 Splitting off Now we turn to a technique developed by L´ aszl´o Lov´ asz, which is very useful for connectivity aug­ mentation and other questions concerning edge connectivity. Theorem 2 Let G = (V + s, E) be a graph, such that the degree of s is even, and ∀U ; ∅ ⊂ U ⊂ V ⇒ |δ(U )| ≥ k (1) Then there are edges (s, u), (s, t) such that G
= (V + s, E \ {(s, u), (s, t)} ∪ {(t, u)}) satisfies Condition 1. In other words, we can “split off” a vertex s of even degree, by replacing pairs of edges incident with s by other edges in the graph, and we preserve k-edge-connectivity between all vertices different than s in the remaining graph. We prove the theorem later. Now let’s demonstrate its application to the construction of all 2k-edge-connected graphs. We first need a lemma. Lemma 3 Every edge-minimal k-edge connected graph has a vertex of degree k. Proof: In a k-edge-connected graph, every cut contains at least k edges. If it’s edge-minimal, every edge is contained in a cut of size exactly k (otherwise we can remove the edge without decresing connectivity). Let S ⊂ V be minimal such that |δ(S)| = k. If |S| = 1, we get a vertex of degree k. We prove that |S| > 1 leads to a contradiction. G[S] is connected (otherwise S is not minimal), and  V, so G[S] contains an edge e. Let δ(T ) be a cut of size k, cutting e (therefore S ∩ T = ∅). If S ∪ T = by submodularity, δ(S ∩ T ) and δ(S ∪ T ) are also cuts of size k. If S ∪ T = V , then δ(S \ T ) = δ(T ) would be a cut of size k. In any case, we get a contradiction with the minimality of S. � Theorem 4 Let M2k denote a multigraph of 2k parallel edges between two vertices. Any 2k-edgeconnected graph can be built from M2k by • adding edges • pinching k edges: taking k edges (u1 , v1 ), . . . (uk , vk ), adding a new vertex s, and replacing each (ui , vi ) by (s, ui ) and (s, vi ). Proof: Start with a 2k-edge-connected graph. Remove edges, until there is a vertex s of degree 2k (whose existence follows from the previous lemma). Apply the splitting-off lemma k times, and remove vertex s while preserving k-edge-connectivity. Then continue, until G shrinks to a 2-vertex graph, which must be a multigraph of at least 2k parallel edges. We remove some edge to obtain M2k . The reverse procedure consists of repeatedly adding edges and pinching collections of k edges. � Note: This gives another proof that any 2k-edge-connected graph G has a k-arc-connected orientation. We start from M2k , where k edges are oriented each way. We build G by adding edges (with arbitraty orientation) and pinching edges, replacing an arc by two arcs oriented the same way. This procedure preserves k-arc-connectivity. 20-2 3 Connectivity augmentation In this section, we use splitting-off to solve the problem of augmenting a graph by adding some edges, so that the graph becomes � k-edge-connected. Let U ⊂ V and x : V → Z. We denote dE (U ) = |δ(U ) ∩ E| and x(U ) = v∈U x(v). Lemma 5 Given G = (V, E), there exists of set of edges F such that (V, E ∪ F ) is k-edge-connected and F has prescribed degrees dF (v) = x(v), if and only if • x(V ) is even, and • ∀U ; ∅ ⊂ U ⊂ V ⇒ dE (U ) + x(U ) ≥ k. Proof: These conditions are clearly necessary; we’ll now show their sufficiency. For G = (V, E) and x : V → Z, add a new vertex s, connecting it to each v ∈ V by x(v) parallel edges. If x(V ) is even, the degree of s is even. Due to the second condition, we have augmented all cuts δ(U ), ∅ ⊂ U ⊂ V , to size at least k, so we can apply splitting off. It follows that edges incident with s can be replaced by a set of edges F with prescribed degrees x(v), while preserving k-edge-connectivity. � This yields an approach to finding the smallest augmenting set F . Find x(v) such that ∀U, ∅ ⊂ U ⊂ V ; dE (U ) + x(U ) ≥ k and x(V ) is minimal. If x(V ) turns out odd, we increase some x(v) by 1 (arbitrarily). In any case, we can augment G to a k-edge-connected subgraph by adding x(V )/2 edges, which is optimal. Theorem 6 G can be augmented to a k-edge-connected graph by adding γ edges, if and only if for any collection of disjoint subsets of vertices P: � (k − dE (U )) ≤ 2γ. U∈P Proof: Again the condition is clearly necessary; we now show sufficiency. Assume that γ satisfies the condition of the lemma. Start with x(v) = k. Decrease the x(v) values arbitrarily, maintaining ∀U ; ∅ ⊂ U ⊂ V ⇒ x(U ) ≥ k − dE (U ). If we cannot decrease any x(v) anymore, each v with x(v) ≥ 1 must be contained in a subset U for which equality x(U ) = k − dE (U ) holds. Let P denote the collection of maximal subsets U ⊂ V such that x(U ) = k − dE (U ). Consider any S, T ∈ P; if S ∪ T = V , then x(V ) ≤ x(S) + x(T ) = (k − dE (V \ S)) + (k − dE (V \ T )) ≤ 2γ. If S∪T = V for any S, T ∈ P, then P must be a collection of disjoint sets. Assume S∩T =  ∅: then x(S)+ x(T ) = (k − dE (S)) + (k − dE (T )) ≤ (k − dE (S ∩T )) + (k − dE (S ∪T )) ≤ x(S ∩T )+ x(S ∪T ) = x(S) + x(T ), i.e. all inequalities are equalities and x(S ∪ T ) = k − dE (S ∪ T ) which contradicts the maximality of S, T . Therefore, P is a partition of {v ∈ V : x(v) ≥ 1} and � � x(U ) = (k − dE (U )) ≤ 2γ. x(V ) = U∈P U∈P Finally, we increment some x(v) to make x(V ) even, if necessary. Consequently, x satisfies the conditions of Lemma 5, x(V ) ≤ 2γ, and therefore we can augment G to a k-edge-connected subgraph by adding at most γ edges. � The condition on x(v) in the proof can be checked efficiently (by min-cut computations). Therefore we can find the minimum set of γ edges which augment edge connectivity to k, in polynomial time. In contrast, the connectivity augmentation problem with edge weights is NP-hard. 20-3