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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.