Consider the following problem, called the zero cycle problem (ZC). You are give
ID: 3694631 • Letter: C
Question
Consider the following problem, called the zero cycle problem (ZC). You are given an undirected graph G = (V, E) with integer weights on its edges (which may be positive, negative or zero). The question is whether there exists a simple cycle consisting of at least three edges whose total weight is zero? (For example, the graph shown in Fig. 1(b) has the zero cycle shown in Fig. 1(c).) Show that ZC is in NP. (Either give a polynomial time verification procedure or present a nondeterministic polynomial time algorithm.) Prove that ZC is NP-hard.Explanation / Answer
Both a) & b)
ZC is in NP
So now we have to prove that the sum of edge weights is zero in polynomial time.
To prove this we will reduce this problem into subset sum problem (Hamilton reduction). The subset sum problem is for a given set of integers, determining whether sum of all values in non-empty set is exactly zero.
Similarly consider weighted Graph G with 2n vertices. So element a' is corresponds to two vertices
vi,ui . Now add edge between every vi to ui with associating some weight. Then construct a cycle by
picking edges so that total weight should be zero. Thus we can obtain zero weight cycle. So by considering
this subset sum problem, it is atleast hard as subset sum problem. So subset sum problem is hard,
so zero weight cycle problem also in NP, and it is also NP-hard.