Reducing subset sum to zero weight cycle

4.5k Views Asked by At

I'm trying to convert an instance of zero subset sum to zero weight cycle in directed graphs to prove that the ZWC problem belongs to the np-complete class. My solution: for each element like x in the zero subset-sum array, create a node in graph G and add an edge from this node to all the other nodes in the graph with weight x. Then if this graph contains a zero weight cycle, our zero subset sum has a solution and vice versa. But when I searched for the solution on the web I found a different way of constructing the graph.

the solution I found on the web

Now the question is that are there any problems with my reduction algorithm?