# Complexity of counting weighted cycles in planar graphs?

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)

• Tahnks Suresh Venkat for editting! :) Dec 3 '10 at 19:17
• By cycle, do you mean simple cycle (i.e., no vertex is visited twice?) Dec 3 '10 at 19:40
• I would interpret it that way, I think. otherwise are you thinking of operating in the vector space of cycles ? Dec 3 '10 at 21:16
• Cycles are vertex disjoint and simple, but if you have any idea for nonsimple cycles plz share it! Dec 4 '10 at 4:40

If you allow repetition of vertices, but not edges, within a cycle, then the problem is $\text{#P}$-complete. This paper 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}$.
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).