Output-Sensitive Approximate Counting via a Measure-Bounded Hyperedge Oracle, or: How Asymmetry Helps Estimate k-Clique Counts Faster

Dell, Lapinskas and Meeks [DLM SICOMP 2022] presented a general reduction from approximate counting to decision for a class of fine-grained problems that can be viewed as hyperedge counting or detection problems in an implicit hypergraph, thus obtaining tight equivalences between approximate counting and decision for many key problems such as k-clique, k-sum and more. Their result is a reduction from approximately counting the number of hyperedges in an implicit k-partite hypergraph to a polylogarithmic number of calls to a hyperedge oracle that returns whether a given subhypergraph contains an edge. The main result of this paper is a generalization of the DLM result for output-sensitive approximate counting, where the running time of the desired counting algorithm is inversely proportional to the number of witnesses. Our theorem is a reduction from approximately counting the (unknown) number of hyperedges in an implicit k-partite hypergraph to a polylogarithmic number of calls to a hyperedge oracle called only on subhypergraphs with a small “measure”. If a subhypergraph has ui nodes in the ith node partition of the k-partite hypergraph, then its measure is ∏i ui. Using the new general reduction and by efficiently implementing measure-bounded colorful independence oracles, we obtain new improved output-sensitive approximate counting algorithms for k-clique, k-dominating set and k-sum. In graphs with nt k-cliques, for instance, our algorithm (1± є)-approximates the k-clique count in time Õє(nω(k−t−1/3,k−t/3,k−t+2/3) +n2), where ω(a,b,c) is the exponent of na× nb by nb× nc matrix multiplication. For large k and t>2, this is a substantial improvement over prior work, even if ω=2.