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?

$\endgroup$
  • $\begingroup$ Have you ever written an algorithm that exploits the symmetries of the underlying object? $\endgroup$ – Stella Biderman Nov 1 '16 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 Nov 1 '16 at 19:31
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.

$\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.