.Petr Hliněný, FI MU Brno, 2015 1 / 24 FI: MA010: Matching and Packing 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. s s s s s s s s ✷ 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. matching = párování, δ(G) = min. degree = minimální stupeˇn .Petr Hliněný, FI MU Brno, 2015 2 / 24 FI: 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: s ss s sss s Definition 5.1. A matching in an undirected graph G is a subset of edges M ⊆ 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.) ✷ Fact: We illustrate the definition with several simple claims: • No matching in G can have more than ⌊|V (G)|/2⌋ 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) ⌈δ(G)/2⌉ edges. (Simply pick the edges greedily from any un-matched vertex. . . ) * Nalezení nejvˇetšího párování v bipartitním grafu * .Petr Hliněný, FI MU Brno, 2015 3 / 24 FI: MA010: Matching and Packing 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 ˙∪B = V (G), construct the following flow network ¯G+ : s s s s s s s s s s 1 1 1 1 1 1 1 1 1 1 1 1 A B z s ✷ • 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). ✷Form M ⊆ E(G) from the edges of flow value 1. free alternating path = volná stˇrídavá cesta .Petr Hliněný, FI MU Brno, 2015 4 / 24 FI: MA010: Matching and Packing Flows to bipartite matchings s s s s s s s s s s 1 1 1 1 1 1 1 1 1 1 1 1 z s Proof of Algorithm 5.2: – A matching M ⊆ E(G) gives a flow sized |M|; val. 1 through each edge of M.✷ – Conversely, assume a flow f computed by Algorithm 4.14 on ¯G+ . Proposition 4.16 implies that f(e) ∈ {0, 1} (only possible int. vals.) for all 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(G) : f(e) = 1} and so M is a matching and |M| = f . ✷✷ 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. .Petr Hliněný, FI MU Brno, 2015 5 / 24 FI: 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 O(|E| · |V |). ✷ s s s s s s s s s s 1 1 1 1 1 1 1 1 1 1 1 1 z s 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 O(|E|) time, and the same time is taken by the augmenting step. ✷ – After |V | rounds, no free alternating path is thus shorter than |V |, and hence there are at most O( |V |) such paths left! ✷ – All the leftover free alt paths are finished in next O( |V |) rounds. ✷ .Petr Hliněný, FI MU Brno, 2015 6 / 24 FI: 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 ⊆ E(G) maximizing e∈M w(e). → A solution can again be obtained similarly to free alternating paths. ✷ • What about maximum cardinality matching in general graphs? → The idea of augmenting free alternating paths can be used, too. However;✷ how can one find such an augmenting path efficiently in this general case?✷ → Edmonds’ Blossom algorithm: recursively contract odd cycles forming alternating “blossoms” (until eventually reaching the easy bipart. case). s s s s s s s s s s s the “blossom” ✷ • Maximum weighted matching in general graphs can be solved efficiently as well [Edmonds] —this is a crucial uneasy result in combinatorial optimization. stable matching = stabilní párování .Petr Hliněný, FI MU Brno, 2015 7 / 24 FI: MA010: Matching and Packing 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 0, a k-regular bipartite graph contains a perf. matching. Proof: Note that |A| = |B| where A, B are the parts of the bip. graph. Take any U ⊆ A. The number of edges incident with U is k · |U| (by k-regularity), and each neighbour in B meets ≤ k of these edges. s s s s s s s s ✷ Hence there are at least k · |U|/k = |U| neighbours of U in B. ✷ .Petr Hliněný, FI MU Brno, 2015 12 / 24 FI: MA010: Matching and Packing Perfect matchings in regular graphs Consider a k-regular 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). . . s s s ✷ 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. s s s s s s s s s s ✷ • Is there some nice general characterization of the graphs with a perfect matching? * Tutteho podmínka * .Petr Hliněný, FI MU Brno, 2015 13 / 24 FI: 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 ⊆ 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: s s s s s ss s s s S Though, we skip the rather involved proof of this beautiful characterization. . . r-factor = r-faktor .Petr Hliněný, FI MU Brno, 2015 14 / 24 FI: MA010: Matching and Packing 5.3 Factors as a 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 1-factor. ✷ Example 5.9. Any 4-regular graph contains a 2-factor. s s s s s s 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 = (v0, e1, v1, e2, v2, . . . , em, v0); 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., e1, e3, e5, . . . , em−1. So, for every vertex of G we select precisely two of the four incident edges, giving a 2-factor. ✷ factorization = rozklad .Petr Hliněný, FI MU Brno, 2015 15 / 24 FI: 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 1-factorization.✷ Proof: Find the first 1-factor M ⊆ E(G) by Corollary 5.6, and continue by induction with factorization of the (k − 1)-regular subgraph G \ M. ✷ ✷ Proposition 5.11. For every n, the complete graph K2n has a 1-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. s s s s s s s s s s Why is this a factorization? ✷ Very briefly, every edge of K2n not incident with the centre in this picture has its “diagonal length”, and the chosen perfect matching covers each such “length” once. ✷ packing = pakování, covering = pokrývání, vertex cover = vrcholové pokrytí .Petr Hliněný, FI MU Brno, 2015 16 / 24 FI: MA010: Matching and Packing 5.4 Packing and Covers Consider now the following 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: s ss s s ss s❢ ❢ ❢ Definition: A vertex cover in a graph G is such a set 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. .Petr Hliněný, FI MU Brno, 2015 17 / 24 FI: 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. ✷ s s s s s s s s s s 1 1 1 1 1 1 1 1 1 1 1 1 z s Construct the same flow network ¯G+ as in Algorithm 5.2. The maximum flow (01valued) in ¯G+ , corresponding to the maximum cardinality matching M ⊆ E(G), is by Theorem 4.10 equal to the minimum edge-cut X ⊆ E(G+ ) in ¯G+ . ✷ Selecting one vertex from each edge of X, and not z, s, one gets 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. ✷ .Petr Hliněný, FI MU Brno, 2015 18 / 24 FI: MA010: Matching and Packing More on packing–covering dualities • For general graphs, König’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.✷ Proof: Let 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 ⊆ 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|. ✷ ✷ • 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. (Erdős–Pósa) There ex. a function f such that, for any k ∈ 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.) * Pakování hranovˇe disjunktních strom˚u * .Petr Hliněný, FI MU Brno, 2015 19 / 24 FI: 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 P is a partition of the vertex set V (G), then |P| denotes the number of parts. An edge e ∈ E(G) is crossing P if its two ends are in distinct parts. • If T ⊆ G is a spanning tree then, clearly, at least |P| − 1 of its edges cross P. ✷ Theorem 5.16. (Nash–Williams, Tutte) A (multi)graph contains k pairwise edge-disjoint spanning trees if, and only if, every partition P of V (G) is crossed by at least k · (|P| − 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 ⊆ 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]). * pokrytí or. grafu cestami * .Petr Hliněný, FI MU Brno, 2015 20 / 24 FI: 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 P1, . . . , Pp such that a) P1, . . . , Pp cover all the vertices, i.e. P1 ∪ · · · ∪ Pp = V (G), and ✷ b) these paths have independent representatives, that is, a collection of pairwise nonadjacent vertices R = {ri ∈ V (Pi) : i = 1, . . . , p}. Sketch. Clearly, some paths satisfying a) exist – 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 ∈ V (Pi) the end : i = 1, . . . , p} is minimal by inclusion. . . s s s s ℓpPp s s s s . . .. . . s s s s s s s s ℓ2 ℓ1 P2 P1 .Petr Hliněný, FI MU Brno, 2015 21 / 24 FI: MA010: Matching and Packing Claim : In a digraph G, let P1, . . . , Pp be a collection of pairw. disjoint paths covering all the vertices of G, such that the set of path ends L = {ℓi ∈ 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 P1, . . . , Pp have independent representatives. ✷ Proof: We would like to say that the set of ends L are the desired representatives. s s s s ℓpPp s s s s . . .. . . s s s s s s s s ℓ2 ℓ1 P2 P1 m1 x By means of contradiction, assume there is an edge e = ℓ2ℓ1 ⊆ L. Then, using induction on |V (G)|, consider the subgraph G\ℓ1 covered by the paths P1 −ℓ1, P2, . . . , Pp:✷ • there exist such independent representatives by induction in G \ ℓ1, or ✷ • the new set of ends L1 = {m1, ℓ2, . . . , ℓp} is not minimal—some collection of paths covering G \ ℓ1 ends in a proper subset of L1. ✷ The latter, though, contradicts original minimality of the ends L in G. ✷ * poˇcítání objekt˚u v grafu * .Petr Hliněný, FI MU Brno, 2015 22 / 24 FI: MA010: Matching and Packing 5.5 Appendix: Counting objects in graphs How many distinct objects (this time not disjoint) one can find in a given graph? • (Trivial) Count the number of vertices, |V (G)|, and of edges, |E(G)|. ✷ • (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)? ✷ 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ý, FI MU Brno, 2015 23 / 24 FI: MA010: 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? s s s s s s s ssss ✷ 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? s s s s s ssss ✷ 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ý, FI MU Brno, 2015 24 / 24 FI: 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 [Matoušek–Nešetřil]. . . ✷ Even more generally: Definition. The Laplace matrix Q = (qij)n i,j=1 of an n-vertex graph G is defined: – qii = dG(i) (vertex degree), – qij = 0 for non-adjacent vertices i = j, – qij = −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.