Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-158 | 1st November 2023 11:37

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


Authors: Oded Goldreich
Publication: 1st November 2023 11:37
Downloads: 84


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.

ISSN 1433-8092 | Imprint