Suppose you are given two graphs $G\_1$ and $G\_2$ and are promised that both are twin free. Is the problem of determining if they are isomorphic graph isomorphism hard? I am curious for the cases of simple as well as non-simple directed graphs.



Graph isomorphism for twin free graphs
Twins are easy to detect. Equivalence classes of twins can be replaced by single vertices with colours (or attached gadgets if you don't like colours) that encode the multiplicity. So the general case is no harder than the twin-free case.


