Skip to content
DeepForgeby svx
All problems
HardGraph Algorithmsgraph-059

Minimum Vertex Cover from Matching

Problem

Build a minimum vertex cover of a bipartite graph from a maximum matching, as guaranteed by Koenig's theorem.

First compute a maximum matching. Then mark vertices reachable from unmatched left nodes by alternating paths: unmatched edges go left to right, matched edges go right to left. The cover is every unmarked left node plus every marked right node. Return it as a sorted list of labels like L0 and R1.

Hint

The cover size equals the matching size, which is the optimality certificate.

Test cases

case 1
in: [3,3,[[0,1],[0],[1]]]
expected: ["R0","R1"]
case 2
in: [2,2,[[0,1],[0,1]]]
expected: ["L0","L1"]
case 3
in: [3,2,[[0],[0,1],[1]]]
expected: ["R0","R1"]
case 4
in: [2,3,[[0],[1,2]]]
expected: ["L0","L1"]
Starter codePython
def min_vertex_cover_bipartite(L, R, adj):
    # Your code here
    pass

4 test cases · run your code against them in the editor