<p>If we are satisfied with <em>approximately</em> 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 (<a href="https://www.math.cmu.edu/%7Eaf1p/Mixing.html" rel="nofollow noreferrer">https://www.math.cmu.edu/~af1p/Mixing.html</a>) .  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.</p>
<p>It would be tempting to think that <em>exactly</em> uniform sampling of cliques is similarly equivalent to <em>exact</em> 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.</p>
<p>As far as I know, it might be the case that <em>exactly</em> uniform sampling of cliques is essentially not any harder than <em>approximately</em> uniform sampling, but I am not aware of a formal reduction of the former to the latter.</p>

CC BY-SA 4.0
2023-03-05T14:47:36.013Z
2023-03-05T14:47:36.013Z
Andras Farago
<p>Let <span class="math-container">$G$</span> be an undirected graph, and let <span class="math-container">$C_1, ..., C_M$</span> denote all possible cliques in <span class="math-container">$G$</span>.</p>
<p>What is known on the complexity of sampling a clique uniformly at random. That is, returning clique <span class="math-container">$C_i$</span> with probability <span class="math-container">$\frac{1}{M}$</span>.</p>

<counting-complexity><sampling>
Complexity of sampling a clique uniformly at random
user3508551
# Complexity of sampling a clique uniformly at random

(Asked by: username_0 on 2023-03-04)

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}$.

**Tags:** counting-complexity, sampling

---

## 1 answers

### Answer by username_1 on 2023-03-05. Score: 4

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](https://www.math.cmu.edu/%7Eaf1p/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.


---

