TY - JOUR

T1 - Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

AU - Dell, Holger

AU - Lapinskas, John

AU - Meeks, Kitty

PY - 2022/7/5

Y1 - 2022/7/5

N2 - 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 colourful independence oracle: The colourful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colourful with respect to a given vertex-colouring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. (ITCS 2018), Dell and Lapinskas (STOC 2018), and Bhattacharya et al. (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 approximate-counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as k-SUM, k-OV and weighted k-Clique) and parameterised complexity (such as induced subgraphs of size k or weight-k solutions to CSPs).

AB - 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 colourful independence oracle: The colourful independence oracle returns yes or no depending on whether a given subset of the vertices contains an edge that is colourful with respect to a given vertex-colouring. Our results extend and/or strengthen recent results in the graph oracle literature due to Beame et al. (ITCS 2018), Dell and Lapinskas (STOC 2018), and Bhattacharya et al. (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 approximate-counting/sampling-to-decision reduction to key problems in fine-grained complexity (such as k-SUM, k-OV and weighted k-Clique) and parameterised complexity (such as induced subgraphs of size k or weight-k solutions to CSPs).

KW - k-hypergraph

KW - colourful independence oracle

KW - approximate counting

KW - uniform edge sampling

KW - fine-grained complexity

KW - k-hypergraph

KW - colourful independence oracle

KW - approximate counting

KW - uniform edge sampling

KW - fine-grained complexity

U2 - 10.1137/19M130604X

DO - 10.1137/19M130604X

M3 - Journal article

SN - 0097-5397

VL - 51

SP - 849

EP - 899

JO - S I A M Journal on Computing

JF - S I A M Journal on Computing

IS - 4

ER -