Jump to content

Kőnig's theorem (graph theory)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 07:15, 9 December 2014 (an early source that explicitly mentions the implication from König to perfection of complements of line graphs of bipartite graphs — not o.r.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For other uses, see König's theorem (disambiguation).
An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six.

In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Setting

A graph is bipartite if its vertices can be partitioned into two sets such that each edge has one endpoint in each set.[1] A vertex cover in a graph is a set of vertices that includes at least one endpoint of each edge, and a vertex cover is minimum if no other vertex cover has fewer vertices.[2] A matching in a graph is a set of edges no two of which share an endpoint, and a matching is maximum if no other matching has more edges.[3] König's theorem states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover.[4]

For graphs that are not bipartite, the maximum matching and minimum vertex cover problems are very different in complexity: maximum matchings can be found in polynomial time for any graph, while minimum vertex cover is NP-complete. The complement of a vertex cover in any graph is an independent set, so a minimum vertex cover is complementary to a maximum independent set; finding maximum independent sets is another NP-complete problem. The equivalence between matching and covering articulated in König's theorem allows minimum vertex covers and maximum independent sets to be computed in polynomial time for bipartite graphs, despite the NP-completeness of these problems for more general graph families.[citation needed]

König's theorem is equivalent to numerous other min-max theorems in graph theory and combinatorics, such as Hall's marriage theorem and Dilworth's theorem. Since bipartite matching is a special case of maximum flow, the theorem also results from the max-flow min-cut theorem.[citation needed]

History

König's theorem is named after the Hungarian mathematician Dénes Kőnig. Kőnig had announced in 1914 and published in 1916 the results that every regular bipartite graph has a perfect matching,[5] and more generally that the chromatic index of any bipartite graph (that is, the minimum number of matchings into which it can be partitioned) equals its maximum degree[6] – the latter statement is known as König's Line Coloring Theorem.[7] However, Bondy & Murty (1976) attribute König's theorem itself to a later paper of Kőnig (1931). According to Biggs, Lloyd & Wilson (1976), Kőnig attributed the idea of studying matchings in bipartite graphs to his father, mathematician Gyula Kőnig. In Hungarian, Kőnig's name has a double acute accent, but his theorem is usually spelled in German characters, with an umlaut.

Statement of the theorem

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.[4]

Example

The bipartite graph shown in the above illustration has 14 vertices; a matching with six edges is shown in blue, and a vertex cover with six vertices is shown in red. There can be no smaller vertex cover, because any vertex cover has to include at least one endpoint of each matched edge, so this is a minimum vertex cover. Similarly, there can be no larger matching, because any matched edge has to include at least one endpoint in the vertex cover, so this is a maximum matching. König's theorem states that the equality between the sizes of the matching and the cover (in this example, both numbers are six) applies more generally to any bipartite graph.[4]

Proof

Partition of the vertices of a matched bipartite graph into even and odd levels, for the proof of König's theorem.

Let G=(V,E) be a bipartite graph, and let V be partitioned into left set L and right set R. Suppose that M is a maximum matching for G.

By definition of "matching", no vertex can cover more than one edge of M. Therefore if a vertex cover with |M| vertices can be constructed, it is minimum.

If M is a perfect matching (which implies that M is maximum) then |L| = |R| = |M|. Since every edge of G is incident on exactly one vertex of L and on exactly one vertex of R, either L or R is a vertex cover of size |M| and we are done.

Otherwise, use an alternating path argument to construct a minimum vertex cover. Given M, An alternating path is a path whose edges alternate between M and E \ M. Partition the vertex set V of G into subsets Si as described below. We show that the union of the odd-indexed subsets is a vertex cover with |M| vertices.

  • Let S0 consist of all vertices unmatched by M.
  • For integer j ≥ 0, let S2j+1 be the set of all vertices v such that
  1. v is adjacent via some edge in E \ M to a vertex in S2j and
  2. v has not been included in any previously-defined set Sk, where k < 2j+1.
If there is no such vertex, but there remain vertices not included in any previously-defined set Sk, arbitrarily choose one of these and let S2j+1 consist of that single vertex.
  • For integer j ≥ 1, let S2j be the set of all vertices u such that u is adjacent via some edge in M to a vertex in S2j−1. Note that for each v in S2j−1 there is a vertex u to which it is matched since otherwise v would have been in S0. Therefore M sets up a one-to-one correspondence between the vertices of S2j−1 and the vertices of S2j.

With regard to the final item on this list, one might worry that a vertex u adjacent via some edge in M to a vertex v in S2j−1 might already be contained in a set Si of index less than 2j and therefore that the sets Si might not form a partition. We show that this is not the case.

  • Vertex v, which by construction appears for the first time in S2j−1, cannot be matched to a vertex in S2k with k < j since vertices in S2k are either unmatched (when k = 0) or matched to a vertex in S2k−1 (when k ≥ 1).
  • Vertex v cannot be matched to a vertex u in S2k-1 with k ≤ j. For observe first that vertices in S2k−1 with k < j are matched to vertices in S2k with 2k < 2j−1 and therefore cannot be matched to v. Second, suppose that v were matched to u in S2j−1. Form an alternating path starting at v by selecting an edge of E \ M joining v to a vertex in S2j−2, an edge of M joining that vertex to a vertex in S2j-3 and so on, joining a vertex in Si to a vertex in Si−1 via an edge of E \ M if i is odd and via an edge of M if i is even, until the process cannot be continued, which happens either when one reaches S0 or when one reaches a set S2h+1 containing a single vertex with no edge joining it to any vertex in the next lower level, S2h. Form a similar path starting at u. Joining these two paths by the edge vu of M produces a longer alternating path P. The path P is simple, since if the alternating paths starting from v and u had a common vertex w at level i, there would be an odd cycle containing w, which is impossible in a bipartite graph. Since v and u are connected, by construction their paths can only both end in S0 or both end in S2h+1. The latter is impossible as that would form a cycle, so as a consequence, the endpoints of P can only be distinct vertices in S0. Hence the first and last edges of P are in E \ M and therefore P contains one more edge of E \ M than of M. So by removing the edges of P ∩ M from M and adding the edges of P ∩ (E \ M) to M we obtain a matching with one more edge than M, contradicting that M is maximum.

We have shown that every vertex of V is in exactly one of the sets Si. It follows that the edges of M always join vertices in adjacent levels S2j−1 and S2j. We further show that no edge of E \ M joins a pair of vertices both of which lie in an even level. For suppose an edge of E \ M joins a vertex in S2j to a vertex in S2k with k ≤ j. If v is a vertex in S2k with k < j, then any vertex joined to v by an edge of E \ M lies in a level Si with i ≤ 2k+1 < 2j, and therefore v cannot be joined by an edge of E \ M to a vertex in S2j. On the other hand, by the same alternating path argument used above, two vertices in S2j cannot be joined to each other by an edge of E \ M . Consequently, every edge of M has exactly one vertex in an odd set, and every edge of E \ M has at least one vertex in an odd set. The union of all of the odd sets is therefore a vertex cover of G containing |M| vertices.[citation needed]

Algorithm

The construction described in the proof above provides an algorithm for producing a minimum vertex cover given a maximum matching. Thus, the Hopcroft–Karp algorithm for finding maximum matchings in bipartite graphs may also be used to solve the vertex cover problem efficiently in these graphs.[citation needed]

Despite the equivalence of the two problems from the point of view of exact solutions, they are not equivalent for approximation algorithms. Bipartite maximum matchings can be approximated arbitrarily accurately in constant time by distributed algorithms; in contrast, approximating the minimum vertex cover of a bipartite graph requires at least logarithmic time.[8]

Connections with perfect graphs

A graph is said to be perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique. Any bipartite graph is perfect, because each of its subgraphs is either bipartite or independent; in a bipartite graph that is not independent the chromatic number and the size of the largest clique are both two while in an independent set the chromatic number and clique number are both one.[citation needed]

A graph is perfect if and only if its complement is perfect,[9] and König's theorem can be seen as equivalent to the statement that the complement of a bipartite graph is perfect. For, each color class in a coloring of the complement of a bipartite graph is of size at most 2 and the classes of size 2 form a matching, a clique in the complement of a graph G is an independent set in G, and as we have already described an independent set in a bipartite graph G is a complement of a vertex cover in G. Thus, any matching M in a bipartite graph G with n vertices corresponds to a coloring of the complement of G with n-|M| colors, which by the perfection of complements of bipartite graphs corresponds to an independent set in G with n-|M| vertices, which corresponds to a vertex cover of G with M vertices. Conversely, König's theorem proves the perfection of the complements of bipartite graphs, a result proven in a more explicit form by Gallai (1958).

One can also connect König's Line Coloring Theorem to a different class of perfect graphs, the line graphs of bipartite graphs. If G is a graph, the line graph L(G) has a vertex for each edge of G, and an edge for each pair of adjacent edges in G. Thus, the chromatic number of L(G) equals the chromatic index of G. If G is bipartite, the cliques in L(G) are exactly the sets of edges in G sharing a common endpoint. Now König's Line Coloring Theorem, stating that the chromatic index equals the maximum vertex degree in any bipartite graph, can be interpreted as stating that the line graph of a bipartite graph is perfect.[10]

Since line graphs of bipartite graphs are perfect, the complements of line graphs of bipartite graphs are also perfect. A clique in the complement of the line graph of G is just a matching in G. And a coloring in the complement of the line graph of G, when G is bipartite, is a partition of the edges of G into subsets of edges sharing a common endpoint; the endpoints shared by each of these subsets form a vertex cover for G. Therefore, König's theorem itself can also be interpreted as stating that the complements of line graphs of bipartite graphs are perfect.[10]

Notes

  1. ^ Bondy & Murty (1976), pp. 4–5.
  2. ^ Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
  3. ^ Bondy & Murty (1976), p. 70.
  4. ^ a b c Bondy & Murty (1976), Theorem 5.3, p. 74.
  5. ^ In a poster displayed at the 1998 International Congress of Mathematicians in Berlin and again at the Bled'07 International Conference on Graph Theory, Harald Gropp has pointed out that the same result already appears in the language of configurations in the 1894 thesis of Ernst Steinitz.
  6. ^ Biggs, Lloyd & Wilson (1976).
  7. ^ Lovász & Plummer (1986), Theorem 1.4.17, pp. 37ff.
  8. ^ Göös & Suomela (2012).
  9. ^ This is the perfect graph theorem of Lovász (1972)
  10. ^ a b Lovász (1974).

References

  • Biggs, E. K.; Lloyd; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press, pp. 203–207, ISBN 0-19-853916-9.
  • Bondy, J. A.; Murty, U. S. R. (1976), Graph Theory with Applications, North Holland, ISBN 0-444-19451-7.
  • Gallai, Tibor (1958), "Maximum-minimum Sätze über Graphen", Acta Math. Acad. Sci. Hungar., 9 (3–4): 395–434, doi:10.1007/BF02020271, MR 0124238.
  • Göös, Mika; Suomela, Jukka (2012), "No sublogarithmic-time approximation scheme for bipartite vertex cover", 26th International Symposium on Distributed Computing (DISC), Salvador, Brazil, October 2012, arXiv:1205.4605.
  • Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő, 34: 104–119.
  • Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok, 38: 116–119.
  • Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4, MR 0302480.
  • Lovász, László (1974), "Minimax theorems for hypergraphs", Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Berlin: Springer, pp. 111–126. Lecture Notes in Math., Vol. 411, doi:10.1007/BFb0066186, MR 0406862.
  • Lovász, László; Plummer, M. D. (1986), Matching Theory, North-Holland, ISBN 0-444-87916-1.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Kőnig%27s_theorem_(graph_theory)&oldid=637288786"