3
$\begingroup$

I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not approximately) the same probability.

If the density (i.e. $m$) is sufficiently high, then an Erdős-Rényi graph will be connected with relatively high probability. Thus we can generate such random graphs and reject any that are not connected. If $m$ is small, this approach will require an impractically large number of trials before a connected graph will be found.

I am looking for methods that will work down to $m=n-1$ (i.e. trees).

Any references to related literature would be most welcome.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Just an idea - instead of adding edges to the empty graph, remove them from the complete graph in random order, skipping removal if it destroys graph connectivity. $\endgroup$
    – Max Alekseyev
    Commented Apr 8, 2018 at 22:18
  • $\begingroup$ "If the density (i.e. m) is sufficiently high, then an Erdős-Rényi graph will be connected with relatively high probability. Thus we can generate such random graphs and reject any that are not connected." I don't see that this would be uniform (consider $p=0.99$ versus $p=0.01$). $\endgroup$
    – usul
    Commented Apr 8, 2018 at 23:50
  • 1
    $\begingroup$ @usul : OP is only saying that it is uniform for fixed $n,m$. Actually using $G_{n,m}$ would be better than using $G_{n,p}$. $\endgroup$
    – Brendan McKay
    Commented Apr 9, 2018 at 0:29
  • 1
    $\begingroup$ There's a suggestion by Yuval Filmus here cs.stackexchange.com/questions/71943/… in the small $m$ case to modify uniform spanning trees generated by e.g. Wilson's algorithm by adding edges. $\endgroup$
    – j.c.
    Commented Apr 9, 2018 at 9:43

1 Answer 1

Reset to default
5
$\begingroup$

I don't know if this has been programmed. I'll describe one method based on counting. Let $c_{n,m}$ be the number of labelled connected graphs with $n$ vertices and $m$ edges.

Choose a pair of distinct vertices $v,w$. By symmetry we can assume $vw$ is an edge. There are several cases:

  • Case 0: $vw$ is not a bridge. The number of such graphs is $\frac{\binom n2-m+1}{\binom n2}c_{n,m-1}$.
  • Case $(k,\ell)$: $vw$ is a bridge and after removing $vw$ the component containing $v$ has $k$ vertices and $\ell$ edges, while the component containing $w$ has $n-k$ vertices and $m-\ell-1$ edges. The number of such graphs is $\binom {n-1}{k-1} c_{k,\ell} c_{n-k,m-\ell-1}$, where the $\binom {n-1}{k-1}$ is for choosing which vertices form the component that contains $v$.

Now you need to choose between these cases with probabilities proportional to the number of graphs in each case. Once you choose the case, generate the graph using one or two recursive calls to your generator. In case 0 you need a connected graph with $m-1$ edges such that $vw$ is not an edge; just generate any connected graph with $m-1$ edges, choose a random non-edge and relabel so that it is $vw$.

Note that the numbers $c_{n,m}$ can be computed by the same recurrence. Use memoisation to avoid exponential time and be prepared for very large values. Using floating point approximations to $c_{n,m}$ should give random graphs practically indistinguishable from those using exact values.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .