(The two proofs that CLIQ is #P-complete that I discuss in this blog are written up by Lance and myself and are here. I think both are well known but I have not been able to find a writeup,so Lance and I did one.)
I have been looking at #P (see my last blog on it it, here, for a refresher on this topic) since I will be teaching this topic in Spring 2021. Recall
#SAT(\phi) = the number of satisfying assignments for phi
#CLIQ((G,k))= the number of cliques of size \ge k of G
#SAT is #P-complete by a cursory look at the proof of the Cook-Levin theorem.
A function is #P-complete if everything else in #P is Turing-Poly red to it. To show for some set A
in NP, #A is #P-complete one usually uses pars reductions.
I wanted a proof that #CLIQ is #P-complete, so I wanted a parsimonious reduction from SAT to CLIQ (Thats a reduction f: SAT--> CLIQ such that the number of satisfying assignments of phi equals the number of cliques of size \ge k of G.)
I was sure there is such a reduction and that it was well known and would be on the web someplace. So I tried to find it.
ONE:
I tracked some references to a paper by Janos Simon (see here) where he claims that the reduction of SAT to CLIQ by Karp (see here) was pars. I had already considered that and decided that Karps reduction was NOT pars. I looked at both Simon's paper and Karp's paper to make sure I wasn't missing something (e.g., I misunderstood what Simon Says or what Karp ... darn, I can't think of anything as good as `Simon Says'). It seemed to me that Simon was incorrect. If I am wrong let me know.
TWO
Someone told me that it was in Valiant's paper (see here). Nope. Valiant's paper shows that counting the number of maximal cliques is #P-complete. Same Deal Here- if I am wrong let me know. One can modify Valiant's argument to get #CLIQ #P-complete, and I do so in the write up. The proof is a string of reductions and starts with PERM is #P-complete. This does prove that# CLIQ is #P-complete, but is rather complicated. Also, the reduction is not pars.
THREE
Lance told me an easy pars reduction that is similar to Karp's non-pars reduction, but it really is NOT Karp's reduction. Its in my write up. I think it is well known since I recall hearing it about 10 years ago. From Lance. Hmmm, maybe its just well known to Lance.
But here is my question: I am surprised I didn't find it on the web. If someone can point to a place on the web where it is, please let me know. In any case, its on the web NOW (my write up) so hopefully in the future someone else looking for it can find it.
(David Eppstein's comment- he asked me to post it for him.)
ReplyDeleteCounting independent sets is #P-complete, even in planar graphs:
SIAM J. Comput., 31(2), 398–427. (30 pages)
The Complexity of Counting in Sparse, Regular, and Planar Graphs
Salil P. Vadhan
https://doi.org/10.1137/S0097539797321602
So counting cliques is complete in the complement of planar graphs.
The reduction is not parsimonious. The definition of #P-completeness does not require parsimoniousness. I think in this case it's a Turing reduction. It should be possible to prove #P-completeness of cliques under polynomial-time counting reductions (https://en.wikipedia.org/wiki/Polynomial-time_counting_reduction) but I don't know of a reference.
Parsimonious reductions are not possible, because every graph has at least one clique (the empty set) and not every satisfiability instance has at least one satisfying assignment.
Your "easy" proof #3SAT to $CLIQ is definitely well-known; it is the reduction I've been teaching since mid-nineties to show Clique is NP-hard, and later when I reach counting complexity I ask the students to check back that the reduction is parsimonious. It appears in the AroraBarak text in Theorem 2.15.
ReplyDeleteI am not surprised its well known, I am surprised that I could not find it online.
Delete