patternMinor
Find all non-isomorphic graphs with a particular degree sequence
Viewed 0 times
degreeallnonwithgraphsisomorphicsequencefindparticular
Problem
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?
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?
Solution
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:
-
Use what you have (perhaps as a baseline for benchmarking other approaches).
-
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.
-
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").
With that being said, I can think of three possible engineering approaches that might work:
-
Use what you have (perhaps as a baseline for benchmarking other approaches).
-
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.
-
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").
Context
StackExchange Computer Science Q#56159, answer score: 4
Revisions (0)
No revisions yet.