Vertex Cover in bipartite graph

Vertex cover reduces to matching and flow when the input is a bipartite graph.

First the unweighted case, that is, we want the minimum cardinality vertex cover.

Konig's theorem says size(VC) = size(M) where VC is a minimum vertex cover and M is a maximum matching.

Quick proof: The direction M >= VC is easy since at least one of the two endpoints in M has to appear in VC. The other direction, M <= VC is proved by providing an algorithm that constructs VC from M.

Suppose we have a matching M now. We have a simple observation, if v in L is matched to w in R, then at most one of v and w can have an unmatched neighbor, otherwise we can augment. A stronger version is that an alternating path start with an unmatched vertex must end at a matched vertex.

The algorithm: start from every unmatched vertex on the left L, do dfs/bfs to reach other vertices in L and R. Let L1 and R1 be set of matched vertices. From L to R we use E-M, from R to L we use M. Let the hit vertices in L be L0 and those in R be R0, the answer is L1-L0 + R0. Intuitively we need all v in R0 to cover all unmatched vertices in L, as well as v in L0. Given the observation we had before, no vertex in L0 can have an edge with an unmatched vertex in R. So edges involving all unmatched vertices in R is covered by L1-L0. Edges involving R1-R0 are covered by L1-L0 because none of them is reachable from L0 when we do dfs. Edges involving R0 are covered by R0 of course. That way we have covered all edges with endpoints in R, namely unmatched vertices, R0 and R1-R0.

The weighted version involves a reduction to min-cut. The graph is constructed by adding s and t, s has edge w(e) = w(v) for each v in L, and each v in R has an edge to t with w(e) = w(v). Each edge from v1 in L to v2 in R has inf capacity. Now a mincut is a min VC.

First observe that a trivial cut is to have s by itself and the weight is finite. So a mincut cannot have an inf edge. Suppose we have a VC = L1 + R1, then our cut is s + L - L1 + R1. The cost of VC is w(L1) + w(R1) and the cost of cut is also w(L1) + w(R1). Conversely, if we have a cut with finite capacity, let the cut assign L1 to s, where L1 is a subset of L, then all vertices in R, call it R1, with an inf edge with L1 must also belong to s. Hence we have L-L1 + R1 being a vertex cover with the same weight.

The algorithm is thus solving the mincut problem with max-flow-min-cut algorithm, then those reachable from s in R and those not reachable from s in L form VC.