Kőnig's and Hall's theorems through minimum cut in bipartite graphs

Revision en13, by adamant, 2022-08-07 02:03:52

Hi everyone!

There is a well-known result about bipartite graphs which is formulated as follows:

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

Knowing it you can easily find the size of a minimum vertex cover in a given bipartite graph. But what about actually recovering such cover? Well... There is an algorithm to it, but it's lengthy and not very motivated, so I constantly forget its details. However, there is a simple alternative, which is easily reproduced from scratch, even if you forget specific details.

Besides, there is another well-known result which is formulated as follows:

A bipartite graph has a perfect matching if and only if every subset $$$\alpha$$$ of one part has a neighborhood $$$\beta$$$ in the other part such that $$$|\beta| \geq |\alpha|$$$.

It is most likely well known to those familiar with the topic, but still might be of interest to someone.

Kőnig's theorem

Recall that given a flow network $$$G=(V, E)$$$, finding minimum cut between $$$s$$$ and $$$t$$$ is done as follows:

  • Find a maximum flow $$$f$$$ from $$$s$$$ to $$$t$$$ in the network;
  • Find $$$X$$$, the set of all vertices reachable from $$$s$$$ in the residual network;
  • Minimum cut is formed by $$$S=X$$$ and $$$T=V \setminus X$$$, that is the minimum cut is formed by the edges going from $$$S$$$ to $$$T$$$.

Now, recall that bipartite matching between sets of vertices $$$A$$$ and $$$B$$$ may be found as maximum flow in the following network:

  • There is an edge of capacity $$$1$$$ going from $$$s$$$ to every vertex of $$$A$$$;
  • There is an edge of capacity $$$1$$$ going from every vertex of $$$B$$$ to $$$t$$$;
  • There is an edge of capacity $$$+\infty$$$ going between some vertices of $$$A$$$ and $$$B$$$, as defined by the bipartite graph.

Now... Is there anything special about minimum cut in such network?


Minimum cut $$$(S, T)$$$ in a flow network induced by a bipartite graph

Generally, some vertices from $$$A$$$ and some vertices from $$$B$$$ will be with the source $$$s$$$ in the cut, while other will be with the sink $$$t$$$.

Let $$$A = A_S \cup A_T$$$ and $$$B = B_S \cup B_T$$$, such that $$$A_S, B_S \subset S$$$ and $$$A_T, B_T \subset T$$$. Then the following is evidently true:

  • There are no edges from $$$A_S$$$ to $$$B_T$$$ (otherwise the cut would be infinite);
  • Thus, every edge in the bipartite graph is incident to some vertex from $$$A_T$$$ or $$$B_S$$$ (or both);
  • Minimum cut is formed only by edges going from $$$S$$$ to $$$A_T$$$ and from $$$B_S$$$ to $$$T$$$ and thus its size is $$$|A_T|+|B_S|$$$.

Putting it all together, the minimum vertex cover is $$$A_T \cup B_S$$$, and it can be easily found from the minimum cut:

  1. Find a minimum cut $$$(S, T)$$$ in the flow network of the maximum matching on bipartite graph with parts $$$A$$$ and $$$B$$$;
  2. A minimum vertex cover is comprised of the sets $$$A_T = (A \cap T)$$$ and $$$B_S = (B \cap S)$$$.

(Generalized) Hall's theorem

The approach above is useful in some other cases as well. Consider the following problem:

A bipartite graph on parts $$$A$$$ and $$$B$$$ is a $$$k$$$-expander if the neighborhood (set of adjacent vertices) $$$\beta \subset B$$$ of any $$$\alpha \subset A$$$ is such that

$$$ |\beta| \geq k |\alpha|. $$$

Given a bipartite graph, you need to check whether it is a $$$k$$$-expander.

Note that for $$$k=1$$$ and $$$|A|=|B|$$$, the condition above is, by Hall's theorem, equivalent to graph having a perfect matching.

Let's construct a similar flow network, but the edges from $$$s$$$ to $$$A$$$ will have capacity $$$k$$$, while the edges from $$$B$$$ to $$$t$$$ have capacity $$$1$$$, and the edges between $$$A$$$ and $$$B$$$ still have capacity $$$+\infty$$$. One has to check whether such graph has a maximum flow of size $$$k|A|$$$.

If the graph is not a $$$k$$$-expander, there can't be such flow, as there is a subset $$$\alpha \subset A$$$ through which you can't push flow of size $$$k|\alpha|$$$ no matter what. But how to prove that the graph is a $$$k$$$-expander when there is such flow?

Well, we rather prove that if the minimum cut in the graph has a capacity less than $$$k|A|$$$, the graph is not a $$$k$$$-expander.

Let's split the minimum cut into $$$A_S \cup B_S$$$ and $$$A_T \cup B_T$$$, as above. There still must be no edges from $$$A_S$$$ to $$$B_T$$$, as they have infinite capacities. So, there is a cut of size $$$k|A_T|+|B_S|<k|A|$$$, which translates into $$$|B_S| < k(|A|-|A_T|) = k|A_S|$$$.

On the other hand, edges from $$$A_S$$$ are only directed in $$$|B_S|$$$, thus $$$\alpha=A_S$$$ is a subset of $$$A$$$ for which $$$\beta \geq k|\alpha|$$$ does not hold.

That being said, the algorithm to check whether the graph is a $$$k$$$-expander is as follows:

  1. Construct a network, in which edges $$$s \to A$$$ have capacity $$$k$$$, edges $$$B \to t$$$ have capacity $$$1$$$ and edges $$$A \to B$$$ have capacity $$$+\infty$$$;
  2. Check that the maximum flow (minimum cut) in the network is $$$k|A|$$$. If it is, the graph is a $$$k$$$-expander, otherwise it's not.
Tags tutorial, konigs theorem, bipartite matching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English adamant 2022-08-07 14:51:32 57 Tiny change: 'first one.\n\nIt is like' -> 'first one. It is like'
en14 English adamant 2022-08-07 03:35:16 4
en13 English adamant 2022-08-07 02:03:52 383 Tiny change: 'nstruct a flow network, ' -> 'nstruct a network, '
en12 English adamant 2022-08-07 02:00:57 9
en11 English adamant 2022-08-07 02:00:31 2167 + Hall lemma
en10 English adamant 2022-08-06 23:35:52 10 Tiny change: '$ or $B_S$;\n- Minim' -> '$ or $B_S$ (or both);\n- Minim'
en9 English adamant 2022-08-06 23:07:05 16 Tiny change: ' no edges between $A_S$ and $B_T$ (ot' -> ' no edges from $A_S$ to $B_T$ (ot'
en8 English adamant 2022-08-06 23:05:45 19 Tiny change: 'and $B_T$ or $A_T$ and $B_S$ (otherwi' -> 'and $B_T$ (otherwi'
en7 English adamant 2022-08-06 22:35:31 36 Tiny change: 'ver**.\n\nNow, the result is well-known and knowing it ' -> 'ver**.\n\nKnowing it '
en6 English adamant 2022-08-06 22:32:30 16
en5 English adamant 2022-08-06 22:31:16 10
en4 English adamant 2022-08-06 22:29:00 216
en3 English adamant 2022-08-06 22:24:33 8
en2 English adamant 2022-08-06 22:16:36 828 Tiny change: 'g" width="600px">\n<b' -> 'g" width="700px">\n<b' (published)
en1 English adamant 2022-08-06 21:57:14 1972 Initial revision (saved to drafts)