<p>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 <a href="http://en.wikipedia.org/wiki/Line_graph" rel="nofollow noreferrer">line graph</a> 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.</p>

<p>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 <a href="https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length">the MO post</a> 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.</p>

CC BY-SA 2.5
2010-12-10T14:30:44.213Z
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?!
marjoonjan
CC BY-SA 2.5
2010-12-09T12:30:30.867Z
2010-12-09T12:30:30.867Z
2017-04-13T12:57:54.777Z
Hsien-Chih Chang 張顯之
<p>Assume a planar graph G, and all its vertices have degree at most 4.<br>
 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:</p>

<p>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.)</p>

<p>1-What is the complexity of finding a cycle with total weight k? (k is a given value)<br>
2-Is finding weighted cycles in G harder than finding cycles in general weighted graphs? 
<img src="https://i.sstatic.net/Zj8Us.png" alt="alt text"> </p>

<p>this is also the link of pic:<br>
<a href="http://rapidshare.com/files/435859757/a.bmp" rel="nofollow noreferrer">http://rapidshare.com/files/435859757/a.bmp</a></p>

<cc.complexity-theory><graph-theory><complexity-classes><graph-algorithms>
Weighted cycles in weighted line graphs
marjoonjan
# Weighted cycles in weighted line graphs

(Asked by: username_0 on 2010-12-09)

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](https://i.sstatic.net/Zj8Us.png)

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

**Tags:** cc.complexity-theory, graph-theory, complexity-classes, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2010-12-09. Score: 3 | Accepted answer

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](http://en.wikipedia.org/wiki/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](https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length) 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.

> **Comments:**
> **username_0**: 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?!  

---

