Vertex Cover 2-Approximation

Problem

Build a vertex cover with the classic 2-approximation: repeatedly take the uncovered edge with lexicographically smallest endpoints and add both endpoints to the cover.

Remove all edges incident to chosen nodes and continue until every edge is covered. Return the sorted cover as a list of node indices. edges is a list of [u, v] pairs.

Hint

Every chosen edge contributes two cover nodes, and at least one endpoint of each must be in any cover.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]]]

expected: [0,1,2,3]

case 2

in: [3,[[0,1],[1,2],[2,0]]]

expected: [0,1]

case 3

in: [4,[[0,1],[0,2],[0,3]]]

expected: [0,1]

case 4

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: [0,1,2,3]

case 5

in: [3,[]]

expected: []

Starter codePython

def vertex_cover_approx(n, edges):
    # Your code here
    pass

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