<p>I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in <a href="https://www.researchgate.net/publication/226508658_On_counting_and_approximation" rel="nofollow noreferrer">this paper</a>. Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the graph (of course order the nodes beforehand so that you don't output the same graph twice). For 2) something similar should work.</p>

<p>In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number <span class="math-container">$k$</span> is also part of the input and they want only the Hamiltonian subgraphs of size <span class="math-container">$k$</span> (I'm assuming the "positive integer <span class="math-container">$c$</span>" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size <span class="math-container">$k$</span>) and they that they do not know if it is Span-P hard. </p>

CC BY-SA 4.0
2019-05-22T23:11:20.830Z
2019-05-22T23:11:20.830Z
M.Monet
<p>I'm confused about how to prove either of the following closely related statements. They are both from this paper: <a href="https://epubs.siam.org/doi/10.1137/0208032" rel="nofollow noreferrer">https://epubs.siam.org/doi/10.1137/0208032</a></p>

<p>1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)</p>

<p>2) "Given a complete graph on n nodes and arbitrary
probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."</p>

<p>Given <span class="math-container">$1)$</span>, it's easy to see that <span class="math-container">$2)$</span> problem is <span class="math-container">$\sharp P$</span> hard<span class="math-container">$^*$</span>, but it's unclear to me why this problem is in <span class="math-container">$\sharp P$</span>. Valiant mentions that <span class="math-container">$1)$</span> is likely not in <span class="math-container">$\sharp P$</span>, so maybe this is a typo. <span class="math-container">$2)$</span> appears to perhaps even strictly harder than <span class="math-container">$1)$</span>.</p>

<p>Can anyone give me a hint on how to think about <span class="math-container">$1)$</span>?</p>

<p>(*In the following way: For any given graph <span class="math-container">$G$</span>, embed <span class="math-container">$G$</span> into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to <span class="math-container">$1/2$</span>. Then each subgraph of <span class="math-container">$G$</span> has probability <span class="math-container">$(1/2)^{E(G)}$</span> of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is <span class="math-container">$\sharp P$</span> hard to compute those probabilities.)</p>

<cc.complexity-theory><counting-complexity>
Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?
Elle Najt
# Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?

(Asked by: username_0 on 2019-01-27)

I'm confused about how to prove either of the following closely related statements. They are both from this paper: <https://epubs.siam.org/doi/10.1137/0208032>

1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)

2) "Given a complete graph on n nodes and arbitrary
probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."

Given $1)$, it's easy to see that $2)$ problem is $\sharp P$ hard$^\*$, but it's unclear to me why this problem is in $\sharp P$. Valiant mentions that $1)$ is likely not in $\sharp P$, so maybe this is a typo. $2)$ appears to perhaps even strictly harder than $1)$.

Can anyone give me a hint on how to think about $1)$?

(\*In the following way: For any given graph $G$, embed $G$ into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to $1/2$. Then each subgraph of $G$ has probability $(1/2)^{E(G)}$ of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is $\sharp P$ hard to compute those probabilities.)

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


---

## 1 answers

### Answer by username_1 on 2019-05-22. Score: 2

I think you could be interested by the counting class Span-P (which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time). It was introduced in [this paper](https://www.researchgate.net/publication/226508658_On_counting_and_approximation). Both 1) and 2) are in Span-P. For 1): guess a subgraph, then guess a Hamiltonian circuit, then output the graph (of course order the nodes beforehand so that you don't output the same graph twice). For 2) something similar should work.

In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number $k$ is also part of the input and they want only the Hamiltonian subgraphs of size $k$ (I'm assuming the "positive integer $c$" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size $k$) and they that they do not know if it is Span-P hard.


---

