5 Matching, Covers, and Packing From previous "more applied" areas of Graph theory we now shift closer towards the traditional theory, and survey the classical topics which belong to every GT curriculum. We start with matchings in graphs, and related topics of covering and packing. Interestingly, graph matchings play a role, e.g., in statistical physics. □ Brief outline of this lecture • Matching in graphs and in bipartite graphs, stable marriage. • Perfect matchings, Hall's theorem, factors in graphs, factorizations. • Vertex cover. Packings in graphs, related coverings. • Counting objects in graphs, e.g. spanning trees. Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing 5.1 Matching in Graphs and Bipartite Graphs Imagine the task to "match suitable couples" such that nobody is in more than one relationship: Definition 5.1. A matching in an undirected graph G is a subset of edges M C E(G) such that no two edges from M share a vertex. (The vertices incident to the edges in M are called matched. \M\ is the size.) c Fact: We illustrate the definition with several simple claims: • No matching in G can have more than L|^(G)|/2J edges. • If G is a star, then no matching in G has more than one edge. □ • In any G, one can find a matching with (at least) \6(G)/2] edges. (Simply pick the edges greedily from any un-matched vertex...) Solving the Bipartite Matching Problem The prime example and application of graph matching is in bipartite graphs. □ Algorithm 5.2. Finding maximum cardinality matching in a bipartite graph. Given a bipartite graph G with the vertex parts A,B, A(jB — V(G), construct the following flow network G+: A B l • Run Algorithm 4.14 on G+. • Since all the capacities are integral (1), the resulting max. flow will be integral as well (0 or 1). nForm M C E(G) from the edges of flow value 1. * naCezení největšUw párování v úipartittiímgrafu * Petr Hlinený, Fl MU Brno, 2014 3/33 Fl: MA010: Matching and Packing Flows to bipartite matching Proof of Algorithm 5.2: 1 - A matching M C E(G) gives a flow sized |M|; val. 1 through each edge of M.n - Conversely, assume a flow / computed by Algorithm 4.14 on G+. Proposition 4.16 implies that /(e) e {0,1} (only possible int. vals.) for all e e E{G+). - Then every vertex of G has total flow 0 or 1 (by the capacity from z or to s). □ - Select M — {e e E(G) : /(e) = 1} and so M is a matching and \M\ = ||/||. 5 Closer relation to network flows • Residual (augmenting) paths in G+ = free alternating paths in G; free - both ends of the path in G are currently not matched, alternating - every second edge of the path is in the current matching. • Flow network cuts in G+ = so called vertex covers in G; i.e., the subsets of V(G) hitting all the edges in E(G) - see later. free aCtemavinjj path = voíná střídavá cesta Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Better runtime bound Theorem 5.3. (Hopcroft-Karp algorithm) For a bipartite graph G — (V,E), one can find a maximum matching in time 0(\E\ ■ y/\V\). □ 1 Proof (sketch): Run Dinitz's algorithm (4.5) on the network G+ (see above): - In one round, all the shortest free alternating paths are found in 0(|_B|) time, and the same time takes the augmenting step. □ - After y/\V\ rounds, no free alternating path is thus shorter than and hence there are at most 0(i/|V|) such paths left! □ - All the leftover free alt. paths are finished in next 0(i/|V|) rounds. Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Matching and Optimization Consider the following problems: • Maximum weighted matching in a weighted bipartite graph (G, w) asks for a matching M C E(G) maximizing ^2eeM w(e). —>• A solution can again be obtained similarly to free alternating paths. □ • What about maximum cardinality matching in general graphs! • Maximum weighted matching in general graphs can be solved efficiently as well [Edmonds]—this is a crucial result in combinatorial optimization. The idea of augmenting free alternating paths can be used, too. However;n how can one find such an augmenting path efficiently in this general case?n Edmonds' Blossom algorithm: rec. contract odd cycles forming alternating "blossoms" (until eventually reaching the easy bipart. case). the "blossom" □ Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing The Stable Marriage Theorem Consider also the following problem related to matchings: • Given is a graph G together with matching preferences: for every vertex v € V(G), its matching prefence is a linear order \J\, i.e., the union of any subfamily has at least as many elements as the number of sets in it. □ Where is Thm. 5.5 in this one? A = the sets Mi,..., Mfe, B = their elements, E{G) ~ e. perfect matching = perfektní párování Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Hall's theorem revisited Theorem 5.5. (repeated) Let G be a bipartite graph with the parts A, B, i.e. A(jB — V(G). Then G contains a matching of size \ A\ (in other words, with whole A matched) if, and only if, for every U C A the number of neighbours ofU in B is at least \U\. Proof (a sketch, see Theorem 5.13 for a related full proof): • We apply the flow-cut duality (Theorem 4.14 and Algorithm 5.2) onto the associated network G+ (with capacities 1). Schematically: • So, there is no matching of size \A\ iff G+ has a cut of size < \A\. Let D C V(G) by vertices incid. with this cut, one with each cut edge; \D\ < \A\. • Consider now U — A \ D —all the neighbours of U must belong to B n D, and \BC\D\ = \D\ -\Ar\D\< \A\ -\Ar\D\ = \A\D\ = \U\: a contradiction to the assumptions. Z Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Theorem 5.5. (repeated) Let G be a bipartite graph with the parts A, B, i.e. AiJB — V(G). Then G contains a matching of size \ A\ (in other words, with whole A matched) if, and only if, for every U C A the number of neighbours ofU in B is at least \U\. Corollary 5.6. For every k > 0, a k-regular bipartite graph contains a perf. matching. Proof:Take U C A. The number of edges incident with U is k ■ \U\ (by ^-regularity), and each neighbour in B meets < k of these edges. Hence there are at least k ■ \U\/k — \U\ neighbours of U in B. C Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Perfect matchings in regular graphs Consider a /j-regular (undirected) graph G. • Recall (Cor. 5.6); if G is bipartite, then a perfect matching exists. □ • For non-bipartite G, a perfect matching may not exist. Take, e.g., any odd cycle (k — 2)... , What if the number of vertices is even? No, take two odd cycles.. • An old result of Petersen claims (k — 3): If G is 3-regular and 2-connected (enough to say "G has no bridges"), then G has a perfect matching. • Is there some nice general characterization of the graphs with a perfect matching? Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing ^Tutte's Condition Theorem 5.7. (Tutte) A graph G has a perfect matching if, and only if, for all S C V(G); - the graph G — S has at most \S\ odd components (those of odd number of vert.). Note that the stated condition is clearly necessary: Though, we skip the rather involved proof of this beautiful characterization... Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing 5.3 Factors as Generalization of Matching A perfect matching has the significant property that every graph vertex is incident with exactly one matching edge. What if this number "one" is raised up? Definition 5.8. An r-factor in an undirected graph G is a spanning r-regular (i.e., on all vert, of G and with all degrees r) subgraph of G. Fact: A perfect matching in a graph is the same as a l-factor. □ A solution is short, but tricky... Let G be 4-regular, and assume that G is connected (if not, find 2-factors in each of its components). Since 4 is an even degree, Euler's theorem 2.17 applies to G. □ Hence G consists of one closed trail W — (t>o, ei, vi, e2, t>2, ■ ■ ■, em, t>o); a walk covering every edge of G exactly once. Note that the length m — 2|V(G)| is even in this case. We select every second edge of W, i.e., e±, e^, e$,..., em-i- So, for every vertex of G we select precisely two of the four incident edges, giving a 2-factor. C Example 5.9. Any 4-regular graph contains a 2-factor. ■factor = r faktor Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Factorization into perfect matchings We speak about a factorization of a graph (cf. more general packing in Section 5.4) if the edge set of a graph is to be decomposed into edge-disjoint subgraphs of a certain kind... A r-factorization is a factorization into r-factors. □ Proposition 5.10. For every k > 0, a k-regular bipartite graph has a \-factorization.u Proof: Find the first 1-factor M C E(G) by Corollary 5.6, and continue by induction with factorization of the (k — l)-regular subgraph G — M. □ C Proposition 5.11. For every n, the complete graph K^n has a I-factorization. □ Proof, a brief sketch: Take the perfect matching of n edges from the picture, and rotate it 2n — 1 times around the central vertex. Why is this a factorization? □ Very briefly, every edge of K^n not incident with the centre in this picture has its "diagonal length", and the chosen perfect matching covers each such "length" once. Z 5.4 Packing and Covers Consider now kind of "two-sided" graph problems in which the task is to disjointly pack (a large number of) certain objects into a graph—the packing side. □ Seeing the problem from the opposite side, one could ask about finding (a few of) obstacles which prevent packing any more objects in the graph—the covering side.□ • For example, the network flow-cut duality is of this kind; we would like to "pack" as much flow as possible, while the obstacles are the edges of a z-s cut in the network. □ • In the setting of matchings, the following related notion pops up: Definition: A vertex cover in a graph G is such a set C C V(G) that every edge of G is incident with a vertex of C, i.e. G — C has no edges. □ Proposition 5.12. If C is a vertex cover in a graph G, then no matching in G may contain more than \C\ edges. packing = pakgvani, covering = po^ryvani, vertex cover = vrchoiove pokjijti Petr Hliněný, Fl MU Brno, 2014 16/33 Fl: MA010: Matching and Packing Matching—cover duality in bipartite graphs Theorem 5.13. (König) For an undirected bipartite graph G, the maximum cardinality of a matching in G equals the minimum cardinality of a vertex cover in G. Proof: Recall (Prop. 5.12) that no matching may be larger than the minimum cardinality vertex cover in G. □ 1 Construct the same flow network G+ as in Algorithm 5.2. The maximum flow (01-valued) in G+, corresponding to the maximum cardinality matching M C E(G), is by Theorem 4.10 equal to the minimum edge-cut X C E(G+) in G+. □ Selecting one vertex from each edge of X, and not z,s, one gets C C V(G) hitting all of X, such that clearly \C\ < \X\ — \M\. We claim that C is a vertex cover in G: Suppose not, and let e — uv be a ("leftover") edge in G — C. Then z-u-v-s is a residual path in G+ avoiding X, a contradiction to X being a cut in G+. □ Hence, together with Prop. 5.12, \M\ < \C\ < \X\ = |M|, and the equality holds. C Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing More on packing—covering dualities • For general graphs, Kbnig's Thm. 5.13 fails; e.g., the complete graph Kn has a minimum vertex cover of n — 1 vertices while a maximum matching of only [n/2\ edges.□ Though: Proposition 5.14. In any graph G, the maximum cardinality of a matching and the minimum vertex cover size are within a multiplicative factor of 2 away from each other.a Proof: Let C C V(G) be a smallest vertex cover in G. Then no matching in G is larger than \C\ (Proposition 5.12); \M\ < \C\. Conversely, take a maximum matching M C E(G), and set D — V(M) the vertices incident with M. Since M is maximum, no edge of G may avoid D, and so D is a vertex cover of size \D\ < 2 ■ \M\. □ C • In other words, G cont. a matching of m edges or a v. cover of < 2m vertices. A prime and famous result (a difficult one) in this direction is the following: Theorem 5.15. (Erdos—Posa) There ex. a function f such that, for any k e N, every graph contains k pairwise disjoint cycles or < f(k) vertices hitting every cycle of G. (Vertices hitting every cycle in a graph are called feedback vertex set FVS.) Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Packing edge-disjoint trees In this example, note that we deal with edge-disjoint objects (spanning trees), i.e., we allow them to share vertices but not edges of the underlying graph G. • If V is a partition of the vertex set V(G), then l^l denotes the number of parts. An edge e G E(G) is crossing V if its two ends are in distinct parts. • If T C G is a spanning tree then, clearly, at least \V\ — 1 of its edges cross V. □ Theorem 5.16. (Nash-Williams, Tutte) A (multi)graph contains k pairwise edge-disjoint spanning trees if, and only if, every partition V ofV(G) is crossed by at least k ■ (\V\ — 1) edges of G. □ The proof of this statement (in the "if" direction) is not easy... Theorem 5.17. (Nash-Williams) A (multi)graph can be partitioned into < k forests if, and only if, every vertex subset U C V(G) induces a subgraph with < k ■ (\U\ — 1) edges of G. The proof here is similar to the previous one, and not easy either (see [Diestel]). Petr Hliněný, Fl MU Brno, 2014 * pálkování hranoví éisjunfynícfi stromů * Fl: MA010: Matching and Packing Path Covers In the last example of covering-packing duality, we aim to cover all the vertices of a digraph by pairwise disjoint directed paths, and relate these paths to pairwise nonadjacent vertices (of the paths). The full result reads: Theorem 5.18. (Gallai-Milgram) Every digraph G contains a collection of pairw. disjoint paths Pi,..., Pp such that a) Pi,..., Pp cover all the vertices, i.e. Pi U • • • U Pp — V(G), and □ b) these paths have independent representatives, that is, a collection of pairwise nonadjacent vertices R—{riE V(Pi) : i — 1,... ,p}. Clearly, some paths satisfying a) do exist, just take singleton vertices as the paths. □ The core idea is to take any such a covering collection of paths that the set of path ends L — {£i E V(Pi) the end : i — 1,... ,p} is minimal by inclusion... :F Claim : In a digraph G, let Pi,..., Pp be a collection of pairw. disjoint paths covering all the vertices of G, such that the set of path ends L — {£i e V(Pi) the end : i — 1,... ,p} is minimal by inclusion - meaning that no other covering coll. of paths has the ends in a proper subset of L. Then the paths Pi,..., Pp have independent representatives. □ Proof: We would like to say that the set of ends L are the desired representatives. By means of contradiction, assume there is an edge e — £2(1 C L. Then, using induction on I V(G)|, consider the subgraph G—i\ covered by the paths P\—l\,Pi,... ,Pv\u • there exist such independent representatives by induction in G — i\, or • the new set of ends L\ — {mi, £2, ■ ■ ■, £p} is not minimal—some coll. of paths covering G — i\ ends in a proper subset of L\. □ The latter, though, contradicts original minimality of the ends L in G. C Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing 5.5 Counting Objects in Graphs How many distinct (this time not disjoint) one can find in a given graph? • (Trivial) Count the number of vertices, |V(G)|, and of edges, |_B(G)|. c • (Rather routine) How many triangles / 4-cycles are there in a graph G? □ • (???) Now, how many perfect matchings are there in a (say bipartite) graph G! Is this again a routine question (with a routine algorithmic answer)? c Surprisingly not! Even though we can easily decide the existence of a perfect matching, and to find one, we cannot find or count all of them. —>• This problem is "#P-hard". □ • Is there something else (nontrivial) which can be counted easily in graphs? Yes. Petr Hliněný, Fl MU Brno, 2014 ■J^tůvgrafu * Fl: MAO 10: Matching and Packing Counting spanning trees Recall a definition from Section 2.3: • A spanning tree of G is a subgraph T of G such that T is a tree and V(T) = V(G). Example 5.19. How many distinct spanning trees are contained in the following graph? □ We argue as follows; which edges have to be removed from our graph to obtain a tree? Easily, one from each of the two cycles. Hence, by the principle of independent choices, we have got 5 ■ 6 = 30 spanning trees. □ □ Example 5.20. How many distinct spanning trees are contained in the following graph? □ Similarly as in 5.19, we may remove the "diagonal" edge and one more, giving 9 spanning trees. Or, we keep the "diagonal" and remove one edge from the left and one from the right cycles, giving additional 4 ■ 5 = 20 choices. Altogether 9 + 20 = 29 spanning trees. □ Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing Cayley formula and beyond The following claim is considered a "beautiful gem" of graph theory. Theorem 5.21. (Cayley) The complete graph Kn for n > 0 contains exactly nn~2 distinct spanning trees. Several nice and short proofs of this gem exist, see the textbook [Matousek-Nesetril]... □ Even more generally: Definition. The Laplace matrix Q — (qij)™j=1 of an n-vertex graph G is defined: - qu — dc(i) (vertex degree), _ qij — 0 for non-adjacent vertices i ^ j, - — — 1 for adjacent vertices i ^ j. □ Theorem 5.22. Let Q be the Laplace matrix of a graph G, and let a matrix Q' result from Q by erasing the first row and the first column. Then the number of distinct spanning trees in G equals the determinant \Q'\. □ Corollary 5.23. One can count the spanning trees in any graph in polynomial time. A proof of Thm. 5.22 is, however, quite difficult and using advanced linear algebra. Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Matching and Packing