# What is the complexity of counting Hamiltonian cycles of a graph?

Since deciding whether a graph contains a Hamiltonian cycle is $$NP$$-complete, the counting problem which counts the number of such cycles of a graph is $$NP$$-hard.

Is it also $$PP$$-hard in the sense that $$PP\subseteq P^{\#HAM-CYCLE}$$?

## 1 Answer

In this paper, Liskiewicz et al. state their Lemma 4 as follows:

Lemma 4: The problem of counting Hamiltonian paths in planar graphs of max-deg $$\Delta=3$$ is $$\#P$$-complete under $$\leq^p_{r-shift}$$-reductions.

And, the definition of $$\leq^p_{r-shift}$$-reductions is as follows:

DEFINITION: Polynomial-time Right-bit-Shift Reduction

Let $$f,g:\Sigma^*\rightarrow\mathbb{N}$$, $$f$$ is poly-time right-bit-shift reducible to $$g$$, denoted $$f\leq^p_{r-shift}g$$, if there exists a poly-time computable function $$R_3:\Sigma^*\rightarrow\mathbb{N}-\{0\}$$ and a polynomial-time computable function $$R_1:\Sigma^*\rightarrow\Sigma^*$$, such that $$f(x)=g(R_1(x))\mathrm{div}\ 2^{R_3(x)}$$, for all $$x$$.

So, yes, $$PP\subseteq P^{\#HAM-CYCLE}$$.