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$ May 30, 2019 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$ May 30, 2019 at 18:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.