2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.