pythonalgorithmgraphnetworkxvertex-cover

Networkx min_weighted_vertex_cover in python returns whole set instead of vertex cover

I have an adjacency matrix A with nodes = {0, 1, 2, 3, 4, 5}

A = [[0,1,1,0,0,0],[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,0,0,1,1],[0,0,1,1,0,0],[0,0,0,1,0,0]]

I want to find the minimum weight vertex cover of this graph. I converted this adjacency matrix with 

g_n = nx.from_numpy_matrix(A)

and following function to find the vectex cover

cover = nx.min_weighted_vertex_cover(g_n)

But the output is 

set([0, 1, 2, 3, 4, 5])

which is just the set of all vertices. The expected output should be

set([1, 2, 3])

What is wrong with this process?

Solution

  • This function is approximate and returns "a set of vertices whose weight sum is no more than 2 * OPT" (Prooflink). In your case, OPT=3, so the set of all six nodes is an acceptable answer.