Kőnig's theorem through min-cut/max-flow duality

Правка en4, от adamant, 2022-08-06 22:29:00

Hi everyone!

There is a somewhat 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.

Now, the result is well-known and 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.

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

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 between $$$A_S$$$ and $$$B_T$$$ or $$$A_T$$$ and $$$B_S$$$ (otherwise the cut would be infinite);
  • Thus, every edge in the bipartite graph is incident to some vertex from $$$A_T$$$ or $$$B_S$$$;
  • 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_S = (S \cap A)$$$ and $$$B_T = (B \cap T)$$$.
Теги tutorial, konigs theorem, bipartite matching

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский adamant 2022-08-07 14:51:32 57 Tiny change: 'first one.\n\nIt is like' -> 'first one. It is like'
en14 Английский adamant 2022-08-07 03:35:16 4
en13 Английский adamant 2022-08-07 02:03:52 383 Tiny change: 'nstruct a flow network, ' -> 'nstruct a network, '
en12 Английский adamant 2022-08-07 02:00:57 9
en11 Английский adamant 2022-08-07 02:00:31 2167 + Hall lemma
en10 Английский adamant 2022-08-06 23:35:52 10 Tiny change: '$ or $B_S$;\n- Minim' -> '$ or $B_S$ (or both);\n- Minim'
en9 Английский 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 Английский 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 Английский 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 Английский adamant 2022-08-06 22:32:30 16
en5 Английский adamant 2022-08-06 22:31:16 10
en4 Английский adamant 2022-08-06 22:29:00 216
en3 Английский adamant 2022-08-06 22:24:33 8
en2 Английский adamant 2022-08-06 22:16:36 828 Tiny change: 'g" width="600px">\n<b' -> 'g" width="700px">\n<b' (published)
en1 Английский adamant 2022-08-06 21:57:14 1972 Initial revision (saved to drafts)