2
$\begingroup$

Assume a planar graph G, and all its vertices have degree at most 4.
Consider a cycle in G. The weight of cycle c is the total weight of its vertices, and a vertex is weighted with the following manner:

For example look at vertex v, if cycle c traverses vertex v by passing through e2 and e4 then it would cost w1 and if it traverses v by passing through e4 and e3 then it would cost w2 and so on! (G is undirected, so traversing v by passing through e4 and e3 costs the same as traversing v by passing through e3 and e4, and all possible traversal from a vertex contain weights; some of them are showed with pink curves in pic.)

1-What is the complexity of finding a cycle with total weight k? (k is a given value)
2-Is finding weighted cycles in G harder than finding cycles in general weighted graphs? alt text

this is also the link of pic:
http://rapidshare.com/files/435859757/a.bmp

$\endgroup$
3
$\begingroup$

For the second problem, this question is no harder than finding a cycle of a specific weight k in a general weighted graph in the following sense: consider the line graph of G, that is, a graph L(G) with V(L(G)) = E(G), and two nodes u,v in L(G) are adjacent if the corresponding edges in G are incident to each other. By assigning weights to the edges of L(G) according to your definition, it reduces to the normal weighted cycle problem.

Thus to the first problem, in general if we do not have any constrain on k, we can assign 1/|V(G)| to each edge in an unweighted graph G, and reduced the Hamiltonian cycle problem to the weighed cycle problem by asking k=1, thus it is NP-hard. If you are asking non-negative integral weights, then the algorithm mentioned in the MO post again works since we can subdivide the edges into an unweighted graph. But be careful since the size of the subdivided graph will depends on the total weight on the original graph.

$\endgroup$
  • $\begingroup$ What if some one is searching about those cycles with total weight k which are not hamiltonian cycles? In the other words: what is the complexity of finding nonhamiltonian cycle of total weight k? any suggestion?! $\endgroup$ – marjoonjan Dec 10 '10 at 14:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.