On coarse and fine approximate counting of $t$-cliques

Webpage for a paper by Oded Goldreich


Abstract

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph. One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and its improvement by Bhattacharya, Bishnu, Ghosh, and Mishra (STACS22). More importantly, we provide alternative presentations of their reductions, which we believe to be conceptually simpler.

The pivot of the foregoing works is the notion of {\em coarse} approximate counting; for example, think of approximating the number of $t$-cliques in $n$-vertex graphs up-to a $O(\log n)^{O(t)}$ factor. While it is easy to reduce {\em fine} (i.e., $1+\epsilon$ factor) approximate counting of solutions to NP-complete search problems to their {\em coarse versions} (ditto for natural problems in P such as perfect matching), these simple reductions fail in the context of fine grained complexity. One of the contributions of Dell et al is providing a fine-grained reduction of standard (i.e., fine) approximate counting of $t$-cliques to coarsely counting them. We survey this reduction, and also provide an alternative one. The alternative (alas inferior) reduction composes a reduction of uniform generation of $t$-cliques to {\em coarsely}-approximate counting them with the standard reduction of (fine) approximate counting to uniform generation.

In addition, we survey the coarse approximate counter of $t$-cliques of Bhattacharya et al, and improve its performance by a small twist.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.