6
$\begingroup$

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)

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

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}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I wonder if the problem is easier than #P-hard for smaller K $\endgroup$
    – Yaroslav Bulatov
    Jan 17 '11 at 22:48
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Jan 17 '11 at 12:00
  • $\begingroup$ Second part for the case K = O(1), beacause in the quastion K is a constant. $\endgroup$
    – MikleB
    Jan 17 '11 at 15:55

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.