18.997 Topics in Combinatorial Optimization: Lecture 18 Notes

18.997 Topics in Combinatorial Optimization Lecture 18 18 Orientations, Directed Cuts and Submodular Flows In this lecture, we will introduce three related topics: graph orientations, directed cuts, and submodular flows. In fact, we will use submodular flows to prove results from the other topics. 18.1 Graph Orientations We first introduce some notation and definitions. Let G = (V, E) be an undirected graph. Recall that for a non-empty subset U ⊂ V , the notation δG (U ) denotes the set of edges with one endpoint in U and the other endpoint in V \ U . Definition 1 Let λG (u, v) denote the maximum number of edge-disjoint u-v paths in G. We say that G is k-edge-connected if λG (u, v) ≥ k for all u, v ∈ V . An equivalent statement is that each cut contains at least k edges, i.e., |δG (U )| ≥ k for all non-empty U ⊂ V . out (U ) is the set of arcs Let D = (V, A) be a directed graph. For a non-empty subset U ⊂ V , δD in with their tail in U and head in V \ U , and δD (U ) is the set of arcs in the reverse direction. Definition 2 Let λD (u, v) denote the maximum number of edge-disjoint directed paths in D from u to v. We say that D is k-arc-connected if λD (u, v) ≥ k for each u, v ∈ V . An equivalent out statement is that |δD (U )| ≥ k for all non-empty U ⊂ V . A digraph that is 1-arc-connected is also called strongly connected. An orientation of a graph G is a digraph obtained by choosing a direction for each edge of G. We now give some results relating edge-connectivity of G to arc-connectivity of orientations of G. Theorem 3 (Robbins, 1939) G is 2-edge-connected ⇐⇒ there exists an orientation D of G that is strongly connected. Proof: ⇐: Fix a strongly-connected orientation D. For any non-empty U ⊂ V , we may choose u ∈ U and v ∈ V \ U . Since D is strongly connected, there is a directed u-v path and a directed v-u out in (U )| ≥ 1 and |δD (U )| ≥ 1, implying |δG (U )| ≥ 2. path. Thus |δD ⇒: Since G is 2-edge-connected, it has an ear decomposition. We proceed by induction on the number of ears. If G is a cycle then we may orient the edges to form a directed cycle D, which is obviously strongly connected. Otherwise, G consists of an ear P and subgraph G
with a strongly connected orientation D
. The ear is an undirected path with endpoints x, y ∈ V (G
) (possibly x = y). We orient P so that it is a directed path from x to y and add this to D
, thereby obtaining an orientation D of G. To show that D is strongly connected, consider any u, v ∈ V (G). If u, v ∈ V (G
) then by induction there is a u-v dipath. If u ∈ P and v ∈ V (G
) then there is a u-y dipath and by induction there is a y-v dipath. Concatenating these gives a u-v dipath. The case u ∈ V (G
) and v ∈ P is symmetric. If both u, v ∈ P then either a subpath of P is a u-v path, or there exist a u-y path, a y-x path, and a x-v path. (The y-x path exists by induction). Concatenating these three paths gives a u-v path. � The natural generalization of this theorem also holds. 18-1 Theorem 4 (Nash-Williams, 1960) G is 2k-edge-connected ⇐⇒ there exists an orientation D of G that is k-arc-connected. Before proving Nash-Williams’ theorem, we need a result about how to construct 2k-edgeconnected graphs. This theorem 5 is proved in a subsequent lecture. Theorem 5 Every 2k-edge-connected graph can be constructed as follows. Start from the multigraph G1 consisting of two vertices u and v, with 2k parallel edges joining u and v. Repeatedly perform one of the following operations: 1. Add a new edge. 2. “Pinch” a set S of k edges. This means to add a new vertex z and to replace each edge xy ∈ S with the two edges xz and zy. Proof of Theorem 4: ⇐: Identical to the corresponding direction in the proof of Theorem 3. ⇒: By induction on the number of operations used to construct G in Theorem 5. The starting graph G1 is clearly 2k-edge-connected. Orienting k of the edges from u to v and the other k from v to u gives an orientation that is k-arc-connected. So suppose that G is 2k-edge-connected and has a k-arc-connected orientation D. If we add an edge to G then this edge may be added to D and oriented arbitrarily without violating k-arcconnectivity. Now suppose we pinch a edge-set S, obtaining a graph G
. The directions of the pinched edges induce directions on the new edges of G
in the natural way. That is, if xy ∈ S and xy is oriented from x to y then we orient the new edges xz, zy from x to z and from y to z. If xy ∈ S then xy is oriented as in D. This yields an orientation D
of G
. in out To show that D
is k-arc-connected, we can for example show that δD � (U ) ≥ k and δD � (U ) ≥ k

for every ∅ =  U ⊆ V , where V is the vertex set of G; the vertex set of G being V = V ∪ {z}. This is clear for U = V as we pinched k edges (and we get k incoming to z and k outgoing arcs from z in in out out in D
). For U ⊂ V , we have that δD � (U ) ≥ δD (U ) ≥ k and δD � (U ) ≥ δD (U ) ≥ k as we replaced the arc xy with xz and zy and D is a k-arc-connected orientation. � As mentioned earlier, Theorem 5 will be proved in a susbsequent lecture. We will also give another proof of Nash-Williams orientation theorem based on submodular flows. Nash-Williams also proved the following, much stronger theorem. Theorem 6 (Nash-Williams, 1960) For any graph G, there exists an orientation D such that λD (u, v) ≥ λG (u, v)/2 . The proof of this theorem is quite involved; see Theorem 61.6 in Schrijver. We now prove it for special case that all vertices of G have even degree. in out Proof: Since G is Eulerian, there exists an orientation D such that dD (v) = dD (v) ∀v ∈ V . Thus for any non-empty U ⊂ V , the total in-degree of the vertices in U must equal the total out-degree. Any arcs with both endpoints in U contribute 1 to both the total in-degree and outdegree. Thus the number of arcs leaving U must equal the number of arcs entering U . That is, in out (U )| = |δD (U )| = |δG (U )|/2. The theorem follows by observing that λD (u, v) and λG (u, v) |δD out respectively equal the minimum of |δD (U )| and |δG (U )| over all cuts U separating u and v. � 18.2 Directed Cuts One might expect a directed cut to be a set of edges whose removal destroys strong connectivity of a digraph. Our definition of directed cuts is quite the opposite: it is clear from the following definition that a digraph has a directed cut if and only if it is not strongly connected. 18-2 Definition 7 Let D = (V, A) be a directed graph. A directed cut in D is a set of arcs of the form in out δD (U ) where U is a non-empty proper subset of V and δD (U ) = ∅. Definition 8 A dijoin is a minimal set of arcs that intersect every directed cut. A dijoin is also known as a directed cut cover. Theorem 9 (Lucchesi-Younger, 1978) For every weakly-connected digraph, the minimum size of a dijoin equals the maximum number of disjoint directed cuts. The Lucchesi-Younger theorem is yet another example of a min-max theorem in combinatorial optimization involving objects that “block” each other. A more well-known example is the max-flow min-cut theorem: the minimum size of an s-t cut equals the maximum number of disjoint s-t paths. The min-cut max-flow theorem remains true after swapping the terms cut and path: the minimum length of an s-t path equals the maximum number of disjoint s-t cuts. To see that the max does not exceed the min, fix a shortest s-t path P and let d be the length of P . Each s-t cut must contain at least one edge of P , so there can be at most d disjoint cuts. We now give an intuitive argument that in fact d disjoint cuts exist. Imagine the edges of the graph as being strings of one inch in length, tied together at the vertices. Hold the graph at vertex s, letting gravity pull the other vertices downwards. It is easy to see that the vertices at distance i from s (in the graph-theoretic sense) will be suspended i inches below s. The edges connecting the vertices at distance i to the vertices at distance i + 1 form an s-t cut, and there are d such cuts. Woodall conjectured that the Lucchesi-Younger theorem remains true after swapping the terms directed cut and dijoin. Conjecture 10 (Woodall, 1978) For every digraph, the minimum size of a directed cut equals the maximum number of disjoint dijoins. Woodall’s conjecture remains open, although it has been proven in several special cases; see Chapter 56 of Schrijver. Proposition 11 Let D = (V, A) be a weakly-connected digraph, let B be a subset of A, and let B
= { (v, u) : (u, v) ∈ B }. Then B is a dijoin ⇐⇒ the digraph D
= (V, A ∪ B
) is strongly connected. in in Proof: ⇒: Let U be a non-empty proper subset of V . If δD (U ) is not a directed cut then δD � (U )
in is not either since D is a subgraph of D . So suppose that δD (U ) is a directed cut. Then there exists in an arc (x, y) ∈ δD (U ) ∩ B, since B is a dijoin. The reverse arc (y, x) is an arc of D
, by definition
out in
 ∅, implying that δD of B . Thus δD� (U ) = � (U ) is not a directed cut. Since D has no directed cuts, it is strongly connected. in in (U ) with δD (U ) ∩ B = ∅. ⇐: Suppose that B is not a dijoin. Then there exists a directed cut δD out in
out Then we have δD (U ) = ∅ and for every (x, y) ∈ δD (U ), (y, x) ∈  B . This shows that δD � (U ) = ∅, in
so δD� (U ) is a directed cut. We conclude that D is not strongly connected. � Since checking that a graph is strongly connected can be done in linear time, Proposition 11 implies a polynomial time algorithm to check that a set is a dijoin. It is also easy to check that a collection of sets are disjoint directed cuts, so the Lucchesi-Younger theorem gives a “good charac­ terization” for the problem of finding a minimum size dijoin or a maximum collection of directed cuts. We will see in a later lecture that a minimum size dijoin and a maximum packing of directed cuts can be found in polynomial time, via a reduction to matroid intersection. If D is a planar digraph, we can construct its planar dual D ∗ as follows. Let GD be the underlying undirected graph of D, and let G∗D be its planar dual. For each arc wx of D, let yz be the corresponding dual edge in G∗D . We choose a direction for the edge yz such that it crosses teh arc 18-3 e1 a e2 e3 e4 A C b e5 e7 B E c D F e6 Figure 1: A digraph D in black and its planar dual D ∗ in gray. Note that the arcs {BA, DC, F E} are a directed cut for D, and the corresponding dual arcs {e4 , e7 , e1 } are a directed cycle in D∗ . wx from left to right. Intuitively, the direction for yz is obtained by rotating the arc wx clockwise. The resulting directed graph is the planar dual D ∗ . As we can see from Figure 1, the dicycles of D∗ correspond to the directed cuts of D. A dijoin B in D is a set that intersects every directed cut, and hence B corresponds to a set F of arcs in D∗ that intersects every dicycle. Such a set F is called a feedback arc set. Thus we obtain the following corollary of the Lucchesi-Younger theorem. Corollary 12 For planar digraphs, the minimum size of a feedback arc set equals the maximum number of disjoint directed cuts. 18.3 Submodular Flows We now introduce submodular flows, and use this framework to prove results about graph orientation and directed cuts. Definition 13 Let D = (V, A) be a directed graph and let C ⊆ 2V be a family of subsets of V . C is called a crossing family if: X, Y ∈ C , X ∩ Y = ∅, X ∪ Y =  V =⇒ X ∩ Y ∈ C and X ∪ Y ∈ C . Example 14 The family C = 2V \ {∅, V } is a crossing family. Example 15 Fix s, t ∈ V . The family C = { S : s ∈ S, t ∈  S } is a crossing family. Example 16 . Let C be the family of vertex sets that induce directed cuts in D. More formally, let out (U ) = ∅ }. We claim that C is a crossing family. C ={U : ∅=  U ⊂ V and δD out Proof: Suppose that X, Y ∈ C , X ∩ Y = ∅, and X ∪ Y =  V . By definition of C , δD (X) = ∅, implying that D contains no arc (x, z) with x ∈ X and z ∈ V \ X. Similarly, D contains no arc (x, z) with x ∈ Y and z ∈ V \ Y . First we show that X ∩ Y ∈ C . By our previous remarks, for any x ∈ X ∩ Y , if (x, z) is an arc then we cannot have z ∈ V \ X or z ∈ V \ Y . That is, z ∈ (V \ X) ∪ (V \ Y ) = V \ (X ∩ Y ). This out (X ∩ Y ) = ∅, so X ∩ Y ∈ C . shows that δD 18-4 Next we show that X ∪ Y ∈ C . Suppose z is neither in X nor in Y . If x ∈ X then (x, z) cannot be an arc. Similarly, if x ∈ Y then (x, z) cannot be an arc. This shows that there is no arc (x, z) out (X ∪ Y ) = ∅, so X ∪ Y ∈ C . � with x ∈ X ∪ Y and z ∈ (V \ X) ∩ (V \ Y ) = V \ (X ∪ Y ). Thus δD Definition 17 Let C be a crossing family. A function f : C → R is called crossing submodular (relative to C ) if it satisfies: f (X) + f (Y ) ≥ f (X ∩ Y ) + f (X ∪ Y ) ∀ X, Y ∈ C with X ∩ Y = ∅ and X ∪ Y =  V. Definition 18 Let D = (V, A) be a digraph, let C be a crossing family, and let f be a crossing submodular function on C . We associate with each arc a ∈ A a variable xa and an interval [da , ca ]. The vector x ∈ RA is called a submodular flow if it is contained in the polyhedron: x(δ in (U )) − x(δ out (U )) ≤ f (U ) da ≤ xa ≤ ca ∀U ∈C ∀a∈A (1) Theorem 19 (Edmonds-Giles, 1977) The polyhedron (1) is Box-TDI. That is, for any vectors c, d ∈ RA and any crossing submodular function f , all vertices of (1) are integral. We will prove the Edmonds-Giles theorem in a later lecture. In the remainder of this lecture, we will show some of its applications. First we show that Theorem 4 follows from the Edmond-Giles theorem. Corollary 20 G is 2k-edge-connected ⇐⇒ there exists an orientation of G that is k-arc-connected. Proof: This proof is due to Frank (1980). Choose an orientation D = (V, A) of G arbitrarily. If D is k-arc-connected then there is nothing to prove, so assume otherwise. We will try to find a subset of the arcs such that reversing those arcs’ directions yields a k-arc-connected orientation. For each arc a ∈ A we define a variable xa , where xa = 1 means that we switch the direction of arc a, and xa = 0 means that we do not. Let ∅ = U ⊂ V be arbitrary. After switching the arcs, we want at least k arcs inbound to set in U . Before switching, we have |δD (U )| such arcs. The number of inbound arcs gained by switching out in in in out (U )| − x(δD (U )) + x(δD (U )) ≥ k. That is, is x(δD (U )) − x(δD (U )). Thus we want to have |δD A we want to find an integral vector x ∈ R satisfying: in out out x(δD (U )) − x(δD (U )) ≤ |δD (U )| − k 0 ≤ xa ≤ 1 ∀∅=  U ⊂V ∀a∈ A (2) We have shown that C = { U : ∅ =  U ⊂ V } = 2V \ {∅, V } is a crossing family (Example 14). In out order to use the Edmonds-Giles theorem, we need to show that the function f (U ) = |δD (U )| − k is crossing submodular. So suppose that X, Y ∈ C , X ∩ Y = ∅, and X ∪ Y =  V . It is easy to see that out out out out (X)| + |δD (Y )| ≥ |δD (X ∩ Y )| + |δD (X ∪ Y )|. |δD (To see that the left can be greater than the right, note that arcs connecting X \ Y and Y \ X contribute 1 to the left but 0 to the right.) This implies that f (X) + f (Y ) ≥ f (X ∩ Y ) + f (X ∪ Y ), since the k’s cancel. Thus the Edmonds-Giles theorem shows that every vertex of the polyhedron (2) is integral. However, we have yet to show that the polyhedron is non-empty. To show this, set each xa = 1/2, in in out out so that that x(δD (U )) = |δD (U )|/2 and x(δD (U )) = |δD (U )|/2. Then in in out in out (U )| − x(δD (U )) + x(δD (U )) = |δD (U )|/2 + |δD (U )|/2 = |δG (U )|/2 ≥ k. |δD 18-5 This shows that all constraints are satisfied, so the polyhedron (2) is non-empty; in particular, it has at least one integral vertex x∗ . Swapping the direction of the edges indicated by the 1-coordinates � of x∗ yields a k-arc-connected orientation of G. Next, we show that the Lucchesi-Younger theorem also follows from the Edmond-Giles theorem. Corollary 21 Let D = (V, A) be a weakly-connected digraph. The minimum size of a dijoin equals the maximum number of disjoint directed cuts in D. out Proof: Take C = { U : ∅ =  U ⊂ V and δD (U ) = ∅ }. Example 16 shows that C is a crossing family. Take f : C → R to be the function f (U ) = −1 for all U ∈ C . Clearly f is crossing submodular. So the Edmonds-Giles theorem shows that the following polyhedron is Box-TDI: x(δ in (U )) − x(δ out (U )) ≤ f (U ) da ≤ xa ≤ ca ∀U ∈C ∀a∈A (3) Next, for each a ∈ A, we define da = −∞ and ca = 0. By the definition of C and f , we may out (U )) with 0 and f (U ) with −1. Adding the following objective function yields the LP: replace x(δD max � xa a∈A s.t. x(δ in (U )) xa ≤ 0 ≤ −1 ∀U ∈C ∀a∈A (4) It is easier to interpret the meaning of this LP after replacing xa with −xa : � min xa a∈A s.t. x(δ in (U )) xa ≥ 0 ≥ 1 ∀U ∈C ∀a∈ A (5) Note that setting xa > 1 is never necessary to satisfy any constraints and furthermore penalizes the objective function. Thus we may assume that xa ≤ 1. The feasible integral solutions are therefore {0, 1} solutions, corresponding to dijoins of D. Since (3) is Box-TDI, the LP (5) has an integral optimal solution x∗ , corresponding to a minimum size dijoin. The dual of (5) is: max � yU U ∈C s.t. � yU ≤ 1 ∀a∈ A (6) U : a∈δ in (U ) yU ≥ 0 ∀U ∈ C The constraints ensure that yU ≤ 1 for each U ∈ C . The feasible integral solutions are therefore {0, 1} solutions, each corresponding to a packing of directed cuts of D. Since (3) is Box-TDI, (6) has an integral optimal solution, corresponding to a maximum packing of directed cuts. Strong duality implies that the minimum size of a dijoin equals the maximum number of disjoint directed cuts. � 18-6