Vertex Cover in Bipartite Graphs, in Depth

The problem and the easy half of the theorem

Let G have vertex sets L and R, with every edge joining a vertex of L to a vertex of R. A matching M is a set of edges with no shared endpoint. A vertex cover C is a set of vertices such that every edge has at least one endpoint in C.

One direction holds in every graph. Each matching edge must be covered, and no vertex covers two of them. So any cover has at least as many vertices as any matching has edges: |M| <= |C| for all M and C. This is weak duality. So a matching and a cover of equal size are both optimal.

Kőnig's theorem says that in bipartite graphs the gap always closes: the maximum matching size equals the minimum cover size. A triangle shows why bipartiteness matters: its maximum matching has one edge, but its minimum cover needs two vertices.

The problem and the easy half of the theorem

Let G have vertex sets L and R, with every edge joining a vertex of L to a vertex of R. A matching M is a set of edges with no shared endpoint. A vertex cover C is a set of vertices such that every edge has at least one endpoint in C.

One direction holds in every graph. Each matching edge must be covered, and no vertex covers two of them. So any cover has at least as many vertices as any matching has edges: |M| <= |C| for all M and C. This is weak duality. So a matching and a cover of equal size are both optimal.

Kőnig's theorem says that in bipartite graphs the gap always closes: the maximum matching size equals the minimum cover size. A triangle shows why bipartiteness matters: its maximum matching has one edge, but its minimum cover needs two vertices.

From a maximum matching to a minimum cover

Start from a maximum matching M. Call a vertex free if no matching edge touches it. Now define Z as the set of vertices reachable from the free vertices of L by alternating paths: paths that leave L along non-matching edges and return to L along matching edges. Then the cover is:

C = (L - Z) | (R & Z)      # left vertices NOT reached, right vertices reached

Two facts about Z do all the work. First, no free right vertex is in Z: the path reaching it would be an augmenting path, contradicting maximality. Second, a matched left vertex enters Z only through its own matching edge, so a matched left vertex is in Z exactly when its partner is.

C covers every edge. Take an edge (u, v) with u in L. If u is not in Z, u is in C. If u is in Z and the edge is not in the matching, the search follows it, so v is in Z and in C. If u is in Z and the edge is the matching edge, then u is matched and by the second fact v is in Z, so v is in C.

C has exactly |M| vertices. Every free left vertex is a starting point, so it is in Z and not in C. No free right vertex is in Z, so none is in C. Therefore C contains only matched vertices. For each matching edge (u, v), the second fact says u and v are either both in Z or both outside it. If both are in Z, v is in C and u is not. If both are outside, u is in C and v is not. Exactly one endpoint per matching edge, so |C| = |M|, and weak duality makes both optimal.

Implementation with a certificate check

The implementation has three parts: find a maximum matching, run the alternating search, and verify the certificate. The matching below augments one free left vertex at a time with breadth-first search, which is O(V E) and has no recursion, so it cannot overflow the stack on long augmenting paths. For large graphs use Hopcroft-Karp, which is O(E sqrt(V)); the cover extraction does not care how the matching was found, only that it is maximum.

from collections import deque

def max_matching(n_left, n_right, adj):
    """adj[u] lists right vertices adjacent to left vertex u."""
    match_l = [-1] * n_left
    match_r = [-1] * n_right
    for s in range(n_left):
        parent, seen = {}, [False] * n_right
        q, end = deque([s]), -1
        while q and end < 0:
            u = q.popleft()
            for v in adj[u]:
                if seen[v]:
                    continue
                seen[v], parent[v] = True, u
                if match_r[v] < 0:
                    end = v
                    break
                q.append(match_r[v])
        v = end                       # flip the augmenting path, if any
        while v >= 0:
            u = parent[v]
            nxt = match_l[u]
            match_l[u], match_r[v] = v, u
            v = nxt
    return match_l, match_r


def konig_cover(n_left, n_right, adj, match_l, match_r):
    in_zl, in_zr = [False] * n_left, [False] * n_right
    q = deque(u for u in range(n_left) if match_l[u] < 0)
    for u in q:
        in_zl[u] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v == match_l[u] or in_zr[v]:
                continue                  # only non-matching edges L -> R
            in_zr[v] = True
            w = match_r[v]                # matching edge R -> L
            assert w >= 0, "free right vertex reached: matching not maximum"
            if not in_zl[w]:
                in_zl[w] = True
                q.append(w)
    return ([u for u in range(n_left) if not in_zl[u]],
            [v for v in range(n_right) if in_zr[v]])


def verify(adj, match_l, cover_l, cover_r):
    size = sum(v >= 0 for v in match_l)
    cl, cr = set(cover_l), set(cover_r)
    for u, nbrs in enumerate(adj):
        for v in nbrs:
            assert u in cl or v in cr, f"edge ({u}, {v}) is not covered"
    assert len(cl) + len(cr) == size, "cover and matching sizes differ"
    return size

The verifier checks the two conditions weak duality needs, so a passing verify proves both outputs optimal regardless of bugs elsewhere. The assertion in konig_cover is a cheaper alarm: reaching a free right vertex means the matching was not maximum. The search is O(V + E), cheaper than the matching itself.

Worked example

Take L = {a, b, c, d}, R = {1, 2, 3, 4} and edges a-1, a-2, b-1, c-2, c-3, c-4 and d-2, the graph in the diagram above. Vertices b and d each have a single neighbour, so a matching might take b-1, d-2 and c-3. Can it reach four? Vertices a, b and d together see only {1, 2}: three left vertices with two neighbours between them, a Hall violation, so at most two of them can ever be matched and the maximum is 3.

Run the cover search from the only free left vertex, a. Its non-matching edges reach 1 and 2, so both join Z. Their matching edges lead back to b and d, which join Z. Vertex b has no edge except its matching edge to 1, and d has none except its matching edge to 2, so the search stops with Z = {a, b, d, 1, 2}.

The cover is {c, 1, 2}. Every edge is touched: a-1 and b-1 by 1, a-2 and d-2 by 2, and c-2, c-3 and c-4 by c. Three vertices, three matching edges, so both are optimal. The left part of Z, {a, b, d}, is exactly the Hall violator: the search finds the obstruction to a larger matching and the cover at once. Run the code above and it finds a-2, b-1 and c-3 instead, leaving d free; the search reaches the same Z and the same cover.

The complement: maximum independent sets

The complement of any vertex cover is an independent set, a set of vertices with no edge between them, because an edge inside the complement would be uncovered. The converse also holds, so in every graph the minimum cover size plus the maximum independent set size equals the number of vertices (Gallai's identity). With Kőnig, a bipartite maximum independent set has |V| - |M| vertices: the complement of the cover. In the example, the independent set is {a, b, d, 3, 4}: five vertices, eight minus three.

This is the form the theorem takes most often in practice: keep as many items as possible with no conflicts, where every conflict runs between two groups, such as frontend and backend feature flags. That is a maximum independent set in a bipartite conflict graph, one matching away.

Weighted covers and the LP view

With vertex costs, the counting argument fails, but the cheapest bipartite cover is still a minimum cut. Build a flow network: a source with an edge of capacity w(u) to each left vertex u, an edge of capacity w(v) from each right vertex v to a sink, and an edge of infinite capacity from u to v for each original edge.

def weighted_cover(L, R, edges, w, max_flow):
    # max_flow(graph, s, t) -> (value, set of vertices reachable from s in the residual graph)
    g = {}
    for u in L: g[("s", u)] = w[u]
    for v in R: g[(v, "t")] = w[v]
    for u, v in edges: g[(u, v)] = float("inf")
    value, reach = max_flow(g, "s", "t")
    cover = [u for u in L if u not in reach] + [v for v in R if v in reach]
    return value, cover          # value equals the total weight of cover

A finite cut can never sever an infinite middle edge, so for every original edge either u is on the sink side (its source edge is cut, putting u in the cover) or v is on the source side (its sink edge is cut, putting v in the cover). The capacity of the minimum cut is therefore the weight of the cheapest cover. With all weights equal to one, this reduces to the unweighted theorem, which is one way to see Kőnig as a special case of max-flow min-cut.

The LP view explains why bipartite graphs are special. As an integer program, vertex cover minimises the sum of x_v subject to x_u + x_v at least 1 per edge. A bipartite constraint matrix is totally unimodular, so the LP relaxation has an integral optimum, and its dual is the matching LP: duality plus integrality is Kőnig's theorem.

Modelling real problems

Kőnig's original statement was about matrices: in a 0-1 matrix, the minimum number of rows and columns that together contain every 1 equals the maximum number of 1s with no two in the same row or column. Make rows the left side, columns the right side, and each 1 an edge. The Hungarian algorithm uses this when it covers all zeros of the reduced cost matrix with the fewest lines, and the most non-attacking rooks on a grid of open cells is a maximum matching whose cover names the saturated rows and columns.

Bipartite cover also models placement. Where calls run from clients to backends, the fewest services to instrument so every call has a traced endpoint is a minimum vertex cover; so is the fewest accounts or resources to audit so every access grant is touched.

Failure modes

The construction is short, and the bugs in it are predictable.

• Non-maximum matching. A greedy or interrupted matching produces a set that is not a cover. The assertion above catches this when a free right vertex is reached; the verifier catches the rest.
• Mixing sides. Starting from free right vertices also works with L and R swapped in the formula; mixing the two orientations does not.
• Following the wrong edges. Leave L only on non-matching edges and R only on matching edges; otherwise Z swallows the whole component.
• Input that is not bipartite. If your two sides were inferred from data, an edge inside one side silently breaks every guarantee. Check bipartiteness with a two-colouring BFS first.
• Recursion depth. Recursive DFS versions of Kuhn's algorithm can overflow the stack on long augmenting paths in large graphs. Use the BFS version above or an explicit stack.

When the graph is not bipartite

Outside bipartite graphs the matching bound still holds but the gap can be large, and no polynomial algorithm is known. Taking both endpoints of a maximal matching is linear and at most twice optimal, since the optimum contains an endpoint of each of those disjoint edges.

What to do next

The matching half of this article has its own pages: Kuhn's bipartite matching explains augmenting paths step by step, and bipartite matching covers modelling and Hopcroft-Karp. The flow view is in the max-flow min-cut theorem, and checking that a graph really is bipartite is in bipartite checking with BFS.

1. Implement the three functions above and run them on the example; confirm the cover {c, 1, 2}.
2. Feed konig_cover a deliberately non-maximum matching and watch the assertion or the verifier fail.
3. Generate random bipartite graphs and check that verify passes on every one.
4. Complement the cover to get a maximum independent set and check that no edge lies inside it.
5. Solve one weighted instance with a min-cut library and compare against brute force on small graphs.