1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your construction fails for $\{0\}$ but I can't think of a non-trivial counterexample $\endgroup$ – Akababa Jun 5 '17 at 12:59
  • 1
    $\begingroup$ @Akababa So, to resolve this issue maybe we can add self-loops so that zero elements can be detected since self-loops are cycles too. $\endgroup$ – Winston Jun 5 '17 at 13:14
  • $\begingroup$ Yes, adding a self loop with weight x will resolve the issue. $\endgroup$ – user137481 Jun 7 '17 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.