Approximately counting and sampling edges in hypergraphs using an independence oracle
Holger Dell
In this talk, we will discuss the problem of approximately counting
edges in k-uniform hypergraphs. The hypergraph G can only be accessed
via an independence oracle: Given a set S of vertices, does G[S] contain
any edges? A trivial, exact algorithm runs in time n^k and simply tests
the presence of each edge exhaustively. The cost of an oracle query S
can depend on the size of the set S. We will discuss lower bounds and
upper bounds on the minimum number of queries (and on their minimum
overall cost) which suffice to obtain an estimate on the number of edges
that is correct up to a factor of at most 1 +/- epsilon.