All problems
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
pass4 test cases · run your code against them in the editor