Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions:

  • $T(G, W)$ is invariant under permuting the vertices

  • For any two vertices $u$ and $v$, $u = v$ in $T$ if and only if there is some automorphism $f:V(G) \rightarrow V(G)\ $ such that $f(u) = v$ and $f(v) = u$

The reason I want such a thing is to have some consistent but arbitrary way to order the vertices of a graph that is invariant under permutation, as a tie-breaker for more meaningful orderings, when the vertices are actually distinct, which will usually be the case. If two vertices cannot be distinguished, picking whichever one happens to be first in my representation is fine.

I expect this problem is in $NP$, as it seems like there's some way to compute graph isomorphisms with it, but my graphs are small and I can precompute the ordering once, so it would still be useful to figure out how to do it.

  • $\begingroup$ What do you mean by "$T$ is invariant under permuting the vertices"? Also, what is a "weak ordering"? $\endgroup$ – Yuval Filmus Jul 26 '19 at 0:18
  • $\begingroup$ Can you solve graph isomorphism using your primitive? $\endgroup$ – Yuval Filmus Jul 26 '19 at 0:18
  • $\begingroup$ @YuvalFilmus If the weighted graph $G$ with weights $W$ is isomorphic to a weighted graph $G'$ with weights $W'$, then $T(G, W) = T(G', W')$. This just means $T(G, W)$ doesn't depend on the specific representation of G and W, only the isomorphism class of equivalent graphs. $\endgroup$ – Fricative Melon Jul 26 '19 at 1:05
  • $\begingroup$ @YuvalFilmus Weak ordering just means a ranking of the vertices where vertices can be tied, rather than always strictly greater or less than each other. $\endgroup$ – Fricative Melon Jul 26 '19 at 1:07
  • $\begingroup$ @YuvalFilmus If I combined two graphs $G$ and $H$ into one unconnected graph $J$, then I could order the vertices using my primitive, then if each vertex in $G$ has an equal vertex in $H$, they're isomorphic. This would take $O(V^2)$ time to do given the ordering. So I suppose I can solve it. $\endgroup$ – Fricative Melon Jul 26 '19 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.