Name
Abstract | ||
|---|---|---|
In this paper, we design efficient algorithms to approximately count the number of edges of a given k-hypergraph, and to sample an approximately uniform random edge. The hypergraph is not given explicitly and can be accessed only through its colorful independence or-acle: The colorful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colorful with respect to a given vertex-coloring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. [ACM Trans. Algorithms , 16 (2020), 52], Dell and Lapinskas [Proceedings of STOC , ACM, 2018, pp. 281-288], and Bhattacharya et al. [Proceedings of ISAAC , 2019]. Our results have consequences for approximate counting/sampling: We can turn certain kinds of decision algorithms into approximate counting/sampling algorithms without causing much overhead in the running time. We apply this ap-proximate counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as k-SUM, k-OV, and weighted k-Clique) and parameterized complexity (such as induced subgraphs of size k or weight -k solutions to constraint satisfaction problems). |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/19M130604X | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
approximate counting, FPTRAS, fine-grained complexity, parameterized complexity, graph oracles | Journal | 51 |
Issue | ISSN | Citations |
4 | 0097-5397 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Holger Dell | 1 | 220 | 16.74 |
| John Lapinskas | 2 | 0 | 0.34 |
| Kitty Meeks | 3 | 0 | 0.34 |