18.997 Topics in Combinatorial Optimization: Lecture 10 Notes

18.997 Topics in Combinatorial Optimization March 11, 2004 Lecture 10 Matroid theory was first formalized in 1935 by Whitney [5] who introduced the notion as an attempt to study the properties of vector spaces in an abstract manner. Since then, matroids have proven to have numerous applications in a wide variety of fields including combinatorics and graph theory. Today we will briefly survey matroid representation and then discuss some problems in matroid optimization and the corresponding applications. The tools we develop will help us answer the following puzzle: Puzzle: A game is played on a graph G(V, E) and has two players, George and Ari. Ari’s moves consist of “fixing” edges e ∈ E. George’s moves consist of deleting any unfixed edge. The game ends when every edge has been either fixed or deleted. Ari wins if the graph at the end of the game is connected (i.e. if the fixed edges form a spanning tree). Otherwise George wins. Supposing George moves first, characterize the graphs in which George has a winning strategy. 1 Graphic Matroids Let us begin with some comments regarding graphic matroids that arose during a discussion after class last time. Recall the graphic matroid of graph G is M (G) = (E, I = {F ⊆ E : F is acyclic}). For which graphs G and H does M (G) = M (H)? It is easy to see that the matroid representations of two different graphs might be the same. For example, for the graphs G and H in Figure 1(a) and Figure 1(b) respectively, M (G) = M (H). c a c f d e a g d e b h b h (a) G g f (b) H Figure 1: Switching operation preserves matroid representation. We can think of H as being obtained from G by taking a vertex cut of size two and switching the roles of each vertex in one of the subgraphs. In fact, for 2-connected graphs, this operation always preserves the matroid representation. Theorem 1 If G and H are 2-connected, then M (G) = M (H) if and only if H can be obtained from G via a sequence of switching operations. For higher connectivity, no opertaions exist that lead to the same matroid. 10-1 Theorem 2 If G and H are 3-connected, then M (G) = M (H) if and only if G = H. In general, graph (vertex) connectivity can be equated to a corresponding notion of matroid connectivity. In particular, it can be shown that a graphic matroid corresponding to a k-connected graph is k-connected and vice versa. However, we will not define matroid connectivity here. Let us make one final observation concerning graphic matroids. Recall that last time we saw if a graph G is planar (we assumed sufficiently connected, so that it is uniquely embeddable, but this is not necessary), then M ∗ (G) = M (G∗ ) where the ∗ operation indicates taking the dual of the corresponding object. It can be shown that planar graphs are unique in this sense. Theorem 3 (Tutte) The dual matroid of a graphic matroid M (G) corresponding to graph G is itself a graphic matroid if and only if G is planar. 2 Matroid Representation We would like to characterize matroids representable over a finite field. As a first step, note a matroid and its dual are representable over the same fields. Theorem 4 If M is representable over F , then so is M ∗ . Proof: Suppose the bases of M have size m. Then, by assumption, M can be represented by an m×n matrix A = [I m×m |B m×(n−m) ]. The columns of this matrix are indexed by the elements of the ground set. Let Z be a basis of M and rearrange the rows and columns of A such that Z = X2 ∪ Y1 where X2 and Y1 are as pictured (Figure 2(a)). X(1) X(1) X(2) Y(1) Y(2) X(1) I 0 B(1,1) B(1,2) X(2) 0 I B(2,1) B(2,2) X(2) Y(1) Y(2) Y(1) B(1,1)’ 0 Y(2) B(1,2)’ I (b) A∗ (a) A Figure 2: Representation of M and M ∗ . Consider the matrix A∗ = [B T |I (n−m)×(n−m) ] (Figure 2(b)). Since Z was a basis, B restricted to the X1 rows and Y1 columns has full rank. Thus the X1 columns in A∗ also have full rank, and so Z ∗ = X1 ∪ Y2 is an independent set of vectors. By a similar argument, it is a maximal independent set and so is a basis. As Z ∗ = S\Z, Z ∗ is a basis of M ∗ . Since this is true for every basis Z of M , A∗ is a representation of the dual matroid M ∗ of M . � In 1971, after characterizations of GF (2)- and GF (3)-representable matroids, Gian-Carlo Rota conjectured that the matroids representable over any finite field can be characterized by a finite list of excluded minors (just as, for example, planar graphs can be characterized as those graphs excluding K3,3 and K5 as minors). A minor of a matroid M is a matroid which can be obtained from M by contractions (defined last time) and deletions of elements of the ground set. Binary matroids, or matroids representable over GF (2), were characterized by their excluded minors by Tutte in 1958 [4]. They are precisely the matroids which exclude U42 as a minor. (Observe 10-2 that the list of excluded minors should be closed under taking the dual, and indeed U42 ’s dual is U42 itself.) Theorem 5 A matroid is binary if and only if it excludes U42 as a minor. Tutte further characterized regular matroids, or matroids representable over any field. Definition 1 The Fano matroid is the matroid with ground set S = {A, B, C, D, E, F, G} whose bases are all subsets of S of size 3 except {A, D, B}, {B, E, C}, {A, F, C}, {A, G, E}, {D, G, C}, {B, G, F }, and {D, E, F }. B D E G A C F Figure 3: Fano matroids Note Fano matroids (and hence their duals, see Theorem 4), are representable over GF (2) by, for example, A = (0, 1, 0)T , B = (1, 0, 0)T , C = (0, 0, 1)T , D = (1, 1, 0)T , E = (1, 0, 1)T , F = (0, 1, 1)T , and G = (1, 1, 1)T . In fact, these two matroids are the minimal binary non-regular matroids. Theorem 6 A binary matroid is regular if and only if it excludes the Fano matroid F7 and its dual F7∗ as minors. The ternary matroids, or matroids representable over GF (3) were characterized in the early 1970s in an unpublished work of Reid, later published by Bixby [1] and Seymour [3]. ∗ Theorem 7 The ternary matroids are the matroids which exclude U52 , U52 = U53 , F7 , and F7∗ as minors. In 2000, Geelen, Gerards and Kapoor characterized matroids representable over GF (4) [2] by specifying seven excluded minors, a work for which they won the 2003 Fulkerson Prize. The current state-of-the-art is represented in Figure 4. Remark: Linear matroids are matroids that are representable over some field. Not all linear matroids are representable over the rationals. The Fano matroid is an example of a binary matroid that is not representable over the rationals: If F7 is representable over the rationals, then it is representable over the reals. Since the basis has cardinality 3, it is representable over 3 . Assume such a representation. Since D, E, and F are dependent, they must define a plane that passes through the origin, say the xy-plane. Consider, say, D and E. Each of A, B, C, and G together with D and E form an independent set. Therefore, A, B, C, and G do not lie on the xy-plane. Thus we can project them onto the z = 1 plane (i.e. 10-3 Matroids Linear, representable over some field U(2,5) and U(3,5) Binary, GF(2) graphic regular Fano matroid and its dual U(2,4) planar co−graphic Ternary, GF(3) Figure 4: Classes of matroids. scale them so that they lie in the z = 1 plane). This new representation, say A , B  , C  , and G , preserves the independence relations and thus is also a representation of F7 . Now notice that span(A, G) ∩ span(C, B) = span(E). As E lies in the xy-plane, span(A, G) ∩ (z = 1) = A G and span(C, B) ∩ (z = 1) = B  C  form two parallel lines. Similarly, span(A, B) ∩ (z = 1) = A B  and span(C, G) ∩ (z = 1) = C  G form two parallel lines. Thus A B  C  G is a parallelogram, and so its diagonals, B  G and A C  must intersect. However, this contradicts the fact that span(A, C) ∩ span(B, G) = span(F ). 3 Matroid Optimization To show the power of matroids and just as a sample of things to come, we begin with a definition of the union of matroids. This definition will prove useful in answering questions like does G contain k disjoint spanning trees? Definition 2 The matroid union ∨ki=1 Mi of matroids M1 = (S1 , I1 ), . . . , Mk = (Sk , Ik ) is the k Ii : Ii ∈ Ii }. matroid M = (∪ki=1 Si , I) where I = {∪i=1 We will show that M is a matroid; this is not completely obvious. Furthermore, one can characterize the size of a maximal independent subset in the union of matroids as follows. Lemma 8 Let M = ∨ki=1 Mi for matroids Mi = (Si , Ii ). Then for any U ⊆ S, rM (U ) = minT ⊆U (|U − � T | + ki=1 rMi (T ∩ Si ) where rM (U ) is the rank of set U in matroid M . We will see applications of this next time. Today we will discuss a simpler optimization problem, that of finding a maximum weight independent set in a matroid. Specifically, let M = (S, I) be a 10-4 matroid with an integral weight function w(s) for each s ∈ S. We would like to find an I ∈ I of maximum weight. Consider the greedy algorithm. First order the elements of S so that w(si ) ≥ w(si+1 ). Initialize I to the empty set. At step i, if {si } ∪ I ∈ I, set I ← {si } ∪ I. We will prove that this algorithm is optimal with the aid of the following polytope due to Edmonds: Matroid Polytope xs ≥ 0 x(U ) ≤ r(U ) ∀s ∈ S ∀U ⊆ S Note that the second inequality implies xs ≤ 1 as the rank of a single vertex is at most one. We will show that this polytope is integral and that the vertices are the indicator vectors of independent sets of the matroid. Certainly all independent sets of the matroid satisfy that x(U ) ≤ r(U ). Theorem 9 The greedy algorithm finds a maximum weight independent set. Theorem 10 The matroid polytope of Edmonds is integral. Proof: (of Theorems 9 and 10) Consider the linear program � max w(s)xs �s∈S s.t. xs ≤ r(U ) s∈U xs ≥ 0 ∀U ⊆ S ∀s ∈ S and its dual min � r(U )yU U⊆S s.t. � yU ≥ w(s) Us yU ≥ 0 ∀s ∈ S ∀U ⊆ S. Consider adding the constraint that the yU are integral to the dual. Let the optimal value of this  , the optimal value of the primal be OP , the optimal value of the dual be extended dual be OD OD , and the weight of the maximum independent set be WI . We will construct feasible yU for the  extended dual such that the value of the program OD will equal the weight w(I) of the set I returned  , this by the greedy algorithm. This will prove several facts. As w(I) ≤ WI ≤ OP = OD ≤ OD shows that the greedy algorithm is optimal, thus proving Theorem 9. Furthermore, this shows that the dual is integral for an arbitrary integral weight function, and thus the system is TDI. Together with the fact that the rank function is integral, this proves that the matroid polytope is integral, thus proving Theorem 10.  = w(I). Label the elements of S in order of decreasing weight as the greedy Let’s prove that OD algorithm does. Let Ui = {s1 , . . . , si } and set yUn = w(sn ), yUi = w(si ) − w(si+1 ) for 1 ≤ i ≤ n. For all other sets U , set yU = 0. Note yU�≥ 0 and yU � are integral by construction. �n−1 The first constraint of the dual is also satisfied as, for all i, Usi yU = j≥i yUj = w(sn )+ j=i w(sj )−w(sj+1 ) = w(si ). Now consider the objective. Notice r(U1 ) = 1 if s1 ∈ I and 0 otherwise. Similarly, r(Ui )−r(Ui−1 ) = 1 if si ∈ I and 0 otherwise. Therefore,  OD = � r(U )yU U 10-5 = n−1 � r(Ui )(w(si ) − w(si+1 )) + r(Un )w(sn ) i=1 = = w(s1 )r(U1 ) + w(I). n � w(si )(r(Ui ) − r(Ui−1 )) i=2 � References [1] R. Bixby. On reid’s characterization of ternary matroids. J. Combin. Theory Ser. B, 26:174–204, 1979. [2] J. F. Geelen, A. M. H. Gerards, and A. Kapoor. The excluded minors for gf (4)-representable matroids. Journal of Combinatorial Theory Series B, 79, 2000. [3] P. Seymour. Matroid representation over gf (3). J. Coubin. Theory Ser. B, 26:159–173, 1979. [4] W. T. Tutte. A homotopy theorem for matroids, i, ii. Trans. Amer. Math Soc., 88:144–174, 1958. [5] H. Whitney. On the abstract properties of linear dependence. Amer. J. Math., 57:509–533, 1935. 10-6