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 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 fine (i.e., \(1+\epsilon \) factor) approximate counting of solutions to NP-complete search problems to their 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 coarse-approximate 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 coarse-approximate counting them with the standard reduction of (fine) approximate counting to uniform generation. The key observation here is that uniform generation of t-cliques can be reduced to coarsely-approximate counting t-cliques (rather than to fine-approximate counting t-cliques). In addition, we survey the coarse approximate counter of t-cliques of Bhattacharya et al., and improve its performance by a small twist.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Coarse and Fine Approximate Counting of t-Cliques

  • Oded Goldreich

摘要

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 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 fine (i.e., \(1+\epsilon \) factor) approximate counting of solutions to NP-complete search problems to their 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 coarse-approximate 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 coarse-approximate counting them with the standard reduction of (fine) approximate counting to uniform generation. The key observation here is that uniform generation of t-cliques can be reduced to coarsely-approximate counting t-cliques (rather than to fine-approximate counting t-cliques). In addition, we survey the coarse approximate counter of t-cliques of Bhattacharya et al., and improve its performance by a small twist.