Let $G$ be an undirected graph, and let $C_1, ..., C_M$ denote all possible cliques in $G$.
What is known on the complexity of sampling a clique uniformly at random. That is, returning clique $C_i$ with probability $\frac{1}{M}$.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If we are satisfied with approximately uniform sampling, then it is known that approximately uniform sampling of cliques is equivalent (under randomized polynomial time reductions) with the approximate counting of cliques, see, for example, the notes of Alan Frieze, Martin Dyer and Mark Jerrum (https://www.math.cmu.edu/~af1p/Mixing.html) . This makes the approximately uniform sampling of cliques NP-hard (under randomized polynomial time reductions), because it is known that the approximate counting of cliques is NP-hard under randomized polytime reductions, even in bounded degree graphs.
It would be tempting to think that exactly uniform sampling of cliques is similarly equivalent to exact counting of cliques, but I am not aware of such a result. Such a result would make exact uniform sampling of cliques #P-hard, because it is known that the exact counting of cliques is #P-complete.
As far as I know, it might be the case that exactly uniform sampling of cliques is essentially not any harder than approximately uniform sampling, but I am not aware of a formal reduction of the former to the latter.
