4
$\begingroup$

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?

$\endgroup$
  • $\begingroup$ @Juho That would be a meaningful problem. And a tough one -- I guess graph isomorphism reduces to it? (It's probably not by accident that big data/social network guys do not really sample properly when they sample...) $\endgroup$ – Raphael Apr 21 '16 at 18:41
  • $\begingroup$ You can also use the configuration model to generate all graphs, though you still need to check for isomorphism. $\endgroup$ – Yuval Filmus Apr 26 '16 at 20:49
3
+100
$\begingroup$

To the best of my knowledge, nothing considerably better is known. For instance, your problem was part of the Combinatorics REGS 2012 program at Illinois.

With that being said, I can think of three possible engineering approaches that might work:

  1. Use what you have (perhaps as a baseline for benchmarking other approaches).

  2. Use the suggestion of Yuval: use the configuration model to generate all such graphs, and check for isomorphism between them. For instance, you can use nauty that is fast and highly optimized.

  3. If your degree sequences are of length $n$ for some small $n$ (or you can afford to do a lot preprocessing), generate all $n$-vertex graphs. For this, you can either download them all from McKay's homepage, or use e.g., geng. If you have additional information, you might use an even more specific generator such as plantri (geng has options too). Once you have the graphs, iterate over them and check whether they have the right degree sequence.

By the way, Sage also has much of this functionality built-in, see e.g., here (for instance, search for "Generate all graphs with a specified degree sequence").

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.