(Disclaimer: I am new here, so be patient with my mistakes, but I welcome corrections, advice or comments.)

I am interested in if anyone knows of ways of characterizing the orbits of an adjacency matrix of a multi-graph when it is conjugated by a permutation matrix. To clarify: The matrices in question are symmetric, with zero diagonal (sometimes called hollow symmetric), and all entries non-negative integers.

Conjugation by a permutation matrix will give another adjacency matrix with all the same properties. From a certain perspective this can be visualized as re-drawing the graph that gave rise to the adjacency matrix (in a manner that is isomorphic in the graph-theory sense).

I want to know if, given two adjacency matrices with the same dimensions, is it possible to determine if they lie in the same orbit (without re-constructing the necessary permutation matrices). However, I am interested in any results that are related to this question, since I believe the answer is not known (correct me if I am wrong here).

  • 5
    $\begingroup$ I believe you asking for a (full) solution to the weighted graph isomorphism problem. Practically, I have found nauty to be very good at unweighted graph isomorphism. I have used GAP (to refine nauty's answers) when the unweighted algorithm in nauty was not sufficient. $\endgroup$ – Jack Schmidt Apr 11 '12 at 15:18
  • 3
    $\begingroup$ Possible? Yes. Write down all the permutations of each adjacency matrix and then check whether any two of them are the same. However, it's a big open question whether this can be done efficiently; your problem contains graph isomorphism (en.wikipedia.org/wiki/Graph_isomorphism_problem) as a subproblem and graph isomorphism isn't known to be in P. $\endgroup$ – Qiaochu Yuan Apr 11 '12 at 15:54
  • $\begingroup$ @Qiaochu Yuan - I did specifically state "without reconstructing the necessary permutation matrices," however, the reference to the wikipedia topic is welcome. I feel kind dumb for not noticing that connection... $\endgroup$ – Justin Apr 11 '12 at 16:10
  • $\begingroup$ @ Jack Schmidt - Though I didn't realize it at the time, that is what I was looking for. I knew a lot of research had been done in the area, but I just didn't know how to find it. (There are numerous ways to characterize the problem, it has implications for the reconstruction problem, Hamiltonian circuits, arbitrary subgraphs, and probably many more. Thanks for the practical workaround. $\endgroup$ – Justin Apr 11 '12 at 16:15

You are asking for an algorithm to determine if two multigraphs given by adjacency matrices are equivalent. The problem of graph isomorphism is a notorious one in complexity theory, since it is only known to sit somewhere inbetween P and NP, but it is not known if it is P or NP.

From this it is clear that the problem is not an easy one. The best existing program for graph isomorphism problems is nauty. However, I don't know if it supports multigraphs out of the box. There are interfaces to nauty in Sage and Magma.


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.