6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Have you ever written an algorithm that exploits the symmetries of the underlying object? $\endgroup$
    – Stella Biderman
    Commented Nov 1, 2016 at 19:15
  • 1
    $\begingroup$ Knowing the whole group or just knowing some non-trivial automorphism? One could imagine that might make a difference to the answer. $\endgroup$
    – David Richerby
    Commented Nov 1, 2016 at 19:31

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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