Collection of Maths Problems

Vertex cover in bipartite graph

Task number: 3995

• Hint

  Use duality between flows and cuts in an appropriate network.

• Solution

  We convert the bipartite graph with classes of bipartition \( A, B \) to the network with unit capacities by connecting a source \( s \) with edges to all vertices from the set \( A \), similarly \( B \) to the target \( t \), and all edges go from \( A \) to \( B \).

  We find the maximum flow, and because the edge capacities are integers, you can choose an integer maximum flow. The flow edges used between parts \( A \) and \( B \) form the matching, because no vertex of \( A \) can saturate two edges: There are unit capacities on edges towards \( A \). Similarly for the vertices of \( B \). This is the maximum matching because each matching can be converted to a flow.

  If we have an edge cut \( F \), it can be assumed without loss of generality that each edge of the cut is incident with \( s \) or with \( t \): Otherwise we replace the edge of the cut between \( A \) and \( B \) with its successor leading to \( t \). For \( U \) we choose those vertices from the set \( A \cup B \), which belong to the edges of the cut \( F \). Evidently \(|U|=|F|\). In addition, the set \( U \) is a vertex cover of the original bipartite graph. An uncovered edge would correspond to a saturating path between \( s \) and \( t \), and thus \( F \) would not be a cut.

  Similarly, a cut of the same capacity can be created from each vertex cover \( U \).

  Hence, the size of the minimum vertex cover is equal to the capacity of the minimum cut, and this is equal to the sizes of the maximum flow and the maximum matching.