<p>If you allow repetition of vertices, but not edges, within a cycle, then the problem is $\text{#P}$-complete.  This <a href="http://arxiv.org/abs/1009.5019" rel="nofollow">paper</a> shows that the problem of counting Eulerian tours is $\text{#P}$-complete for 4-regular planar graphs.  Therefore the problem I just described (call it $\text{#}A^\prime$) is $\text{#P}$-hard, because it is at least that difficult: in the special case where all edges have weight 1 and all nodes have weight 0, the Eulerian tours are just those cycles with total weight equal to the number of edges in the graph.  On the other hand, $\text{#}A^\prime\in\text{#P}$, because the corresponding decision problem $A^\prime \in \text{NP}$.</p>

CC BY-SA 2.5
2011-01-17T22:48:14.517Z
I wonder if the problem is easier than #P-hard for smaller K
Yaroslav Bulatov
CC BY-SA 2.5
2011-01-17T05:44:49.873Z
2011-01-17T05:44:49.873Z
mjqxxxx
<p>If all edge weights are $1$-weighted and $K = |V|$ then this problem is the problem of counting hamiltonian cycles in planar graph,which is #P-complete. </p>

<p>But if $K$ is $O(1)$ then let $K = 0$ and all edge weights are $0$. We need to count number of cycles in planar graph (It seems that it is #P-complete also). It is easy to prove that if we can solve this counting problem in polynomail time then we can decide existence of hamiltonian cycle in polynomial time. Let us replace each edge $e=(u, v)$ by two pathes from $u$ to $v$ of length $p = 2|V|^3$, first path is $u,a_1,v_1,a_2,v_2,\ldots,v_{p-1},a_p,v$ and second path is 
$u,b_1,v_1,b_2,v_2,\ldots,v_{p-1},b_p,v$, (for different edges $(u,v)$ there are different vertices $a_i,b_i$). Thus for each edge $(u,v)$ we have $2^p$ correponding simple pathes from $u$ to $v$ in new planar graph. There are no hamiltonian path in original graph iff number of cycles in new graph is less then $|V|!\cdot 2^{|V|} \cdot (2^p)^{|V|-1} + |V|^2 \cdot 2^p $  (because at least $(2^p)^{|V|}$ cycles correspond to hamiltinian path in new graph).</p>

CC BY-SA 2.5
2011-01-17T12:00:44.247Z
Do you have a reference that counting Hamiltonian cycles in a planar graph is #P-complete?  If that is true, then isn't that just the answer here?  I don't understand what your second paragraph is supposed to prove.
mjqxxxx
CC BY-SA 2.5
2011-01-17T15:55:31.253Z
Second part for the case K = O(1), beacause in the quastion K is a constant.
MikleB
CC BY-SA 2.5
2011-01-17T11:50:43.523Z
2011-01-17T11:59:24.217Z
2011-01-17T11:59:24.217Z
MikleB
<p>Assume G is a <strong>weighted planar</strong> graph, nodes and edges in G are weighted, and K is a given constant. 
A is a decision problem with following description:    </p>

<blockquote>
  <p>Does G contain a cycle with total
  weight K ?</p>
</blockquote>

<p>What is the complexity of the counting version of A (#A)? (i.e the complexity of counting all cycles with total weight K) </p>

CC BY-SA 2.5
2010-12-03T19:17:08.737Z
Tahnks Suresh Venkat for editting! :)
marjoonjan
CC BY-SA 2.5
2010-12-03T19:40:03.733Z
By cycle, do you mean simple cycle (i.e., no vertex is visited twice?)
Peter Shor 
CC BY-SA 2.5
2010-12-03T21:16:32.693Z
I would interpret it that way, I think. otherwise are you thinking of operating in the vector space of cycles ?
Suresh Venkat
CC BY-SA 2.5
2010-12-04T04:40:28.937Z
Cycles are vertex disjoint and simple, but if you have any idea for nonsimple cycles plz share it!
marjoonjan
<cc.complexity-theory><graph-theory><counting-complexity>
Complexity of counting weighted cycles in planar graphs?
marjoonjan
# Complexity of counting weighted cycles in planar graphs?

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

Assume G is a **weighted planar** graph, nodes and edges in G are weighted, and K is a given constant.
A is a decision problem with following description:

> Does G contain a cycle with total
> weight K ?

What is the complexity of the counting version of A (#A)? (i.e the complexity of counting all cycles with total weight K)

**Tags:** cc.complexity-theory, graph-theory, counting-complexity

> **Comments:**
> **username_0**: Tahnks username_2 for editting! :)  
> **username_1**: By cycle, do you mean simple cycle (i.e., no vertex is visited twice?)  
> **username_2**: I would interpret it that way, I think. otherwise are you thinking of operating in the vector space of cycles ?  
> **username_0**: Cycles are vertex disjoint and simple, but if you have any idea for nonsimple cycles plz share it!  

---

## 2 answers

### Answer by username_3 on 2011-01-17. Score: 3

If you allow repetition of vertices, but not edges, within a cycle, then the problem is $\text{#P}$-complete. This [paper](http://arxiv.org/abs/1009.5019) shows that the problem of counting Eulerian tours is $\text{#P}$-complete for 4-regular planar graphs. Therefore the problem I just described (call it $\text{#}A^\prime$) is $\text{#P}$-hard, because it is at least that difficult: in the special case where all edges have weight 1 and all nodes have weight 0, the Eulerian tours are just those cycles with total weight equal to the number of edges in the graph. On the other hand, $\text{#}A^\prime\in\text{#P}$, because the corresponding decision problem $A^\prime \in \text{NP}$.

> **Comments:**
> **username_4**: I wonder if the problem is easier than #P-hard for smaller K  

---

### Answer by username_5 on 2011-01-17. Score: 0

If all edge weights are $1$-weighted and $K = |V|$ then this problem is the problem of counting hamiltonian cycles in planar graph,which is #P-complete.

But if $K$ is $O(1)$ then let $K = 0$ and all edge weights are $0$. We need to count number of cycles in planar graph (It seems that it is #P-complete also). It is easy to prove that if we can solve this counting problem in polynomail time then we can decide existence of hamiltonian cycle in polynomial time. Let us replace each edge $e=(u, v)$ by two pathes from $u$ to $v$ of length $p = 2|V|^3$, first path is $u,a\_1,v\_1,a\_2,v\_2,\ldots,v\_{p-1},a\_p,v$ and second path is
$u,b\_1,v\_1,b\_2,v\_2,\ldots,v\_{p-1},b\_p,v$, (for different edges $(u,v)$ there are different vertices $a\_i,b\_i$). Thus for each edge $(u,v)$ we have $2^p$ correponding simple pathes from $u$ to $v$ in new planar graph. There are no hamiltonian path in original graph iff number of cycles in new graph is less then $|V|!\cdot 2^{|V|} \cdot (2^p)^{|V|-1} + |V|^2 \cdot 2^p $ (because at least $(2^p)^{|V|}$ cycles correspond to hamiltinian path in new graph).

> **Comments:**
> **username_3**: Do you have a reference that counting Hamiltonian cycles in a planar graph is #P-complete?  If that is true, then isn't that just the answer here?  I don't understand what your second paragraph is supposed to prove.  
> **username_5**: Second part for the case K = O(1), beacause in the quastion K is a constant.  

---

