Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ for all $i$ and $j$.

Fix vertices $i_0$ and $i_1$. I am interested in finding approximate automorphisms of $G$ that carry $i_0$ to $i_1$. More precisely, consider the problem of finding a permutation $\sigma$ with the properties that:

  1. $\sigma(i_0)=i_1$
  2. $\sigma$ is an approximate automorphism in the sense that $\sum_{i<j} (w_{ij}-w_{\sigma(i),\sigma(j)})^2$ (or some similar measure) is small

Question: What is known about this problem in terms of algorithms/complexity? I would also appreciate pointers to any appropriate literature. (Obviously there are many papers on graph automorphism problems, but I was unable to find anything on this specific problem.)

  • 2
    $\begingroup$ I doubt restricting this to automorphisms will make too much difference. Approximate iso in terms of minimizing the number of mismatching edges/non-edges has been studied, e.g. arxiv.org/abs/1802.08509 and eccc.weizmann.ac.il/report/2012/078. Your notion in terms of weights is a generalization. Would be interesting to know if those results can be extended to your weighted case. $\endgroup$ – Joshua Grochow May 30 '19 at 16:22
  • $\begingroup$ BTW, by using a standard coloring reduction and allowing huge weights, you can force one vertex to be mapped to another. So you might as well just ask about weighted graph approximate isomorphism. That might also make an improved title for the question... $\endgroup$ – Joshua Grochow May 30 '19 at 18:05

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.