Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

0

Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors. First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time. ...

3

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction. First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ ...

6

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.

Top 50 recent answers are included