<p>Consider a graph <span class="math-container">$G$</span> with vertices labeled <span class="math-container">$1,...,n$</span> and edge weights <span class="math-container">$w_{ij}$</span>. Recall an automorphism of G is a permutation <span class="math-container">$\sigma$</span> of the vertex labels such that <span class="math-container">$w_{\sigma(i),\sigma(j)}=w_{ij}$</span> for all <span class="math-container">$i$</span> and <span class="math-container">$j$</span>. </p>

<p>Fix vertices <span class="math-container">$i_0$</span> and <span class="math-container">$i_1$</span>. I am interested in finding approximate automorphisms of <span class="math-container">$G$</span> that carry <span class="math-container">$i_0$</span> to <span class="math-container">$i_1$</span>. More precisely, consider the problem of finding a permutation <span class="math-container">$\sigma$</span> with the properties that: </p>

<ol>
<li><span class="math-container">$\sigma(i_0)=i_1$</span></li>
<li><span class="math-container">$\sigma$</span> is an approximate automorphism in the sense that <span class="math-container">$\sum_{i&lt;j} (w_{ij}-w_{\sigma(i),\sigma(j)})^2$</span> (or some similar measure) is small</li>
</ol>

<p>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.)</p>

CC BY-SA 4.0
2019-05-30T16:22:39.983Z
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. https://arxiv.org/abs/1802.08509 and https://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.
Joshua Grochow
CC BY-SA 4.0
2019-05-30T18:05:41.043Z
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...
Joshua Grochow
<cc.complexity-theory><graph-theory><graph-algorithms><graph-isomorphism>
Graph automorphism with prescribed values
Simon Segert
# Graph automorphism with prescribed values

(Asked by: username_0 on 2019-05-30)

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 (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.)

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, graph-isomorphism

> **Comments:**
> **username_1**: 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. https://arxiv.org/abs/1802.08509 and https://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.  
> **username_1**: 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...  

---

## 0 answers

