patternModerate
Applications of Graph Automorphisms
Viewed 0 times
automorphismsgraphapplications
Problem
I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me.
Is there any practical (or impractical for that matter) applications of knowing the automorphism group of a graph?
Is there any practical (or impractical for that matter) applications of knowing the automorphism group of a graph?
Solution
Automorphism capture a natural notion of symmetry of graphs. As a result, they can be used to speed up algorithms that would otherwise run slowly by chopping down the search space.
For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to keep checking symmetric parts of the tree. We can use graph automorphisms to compute the orbits of variables in the linear programming problem, and then treat parts with the same orbit as identical. A recent application of such techniques to MILP can be read here.
For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to keep checking symmetric parts of the tree. We can use graph automorphisms to compute the orbits of variables in the linear programming problem, and then treat parts with the same orbit as identical. A recent application of such techniques to MILP can be read here.
Context
StackExchange Computer Science Q#65391, answer score: 11
Revisions (0)
No revisions yet.