<p>If I understood well the question, this is an attempt to prove that your problem is $GI$-complete.</p>

<p>Given two graphs $G_1, G_2$ connect all the nodes of $G_1$ to a new node $x$ and all the nodes of $G_2$ to a new node $y$. Then connect $x$ and $y$ with a path of new nodes: $ x_1, x_2, ... x_k,\; z\;, y_k, ...,y_2, y_1$ (there is an odd number of nodes between $x$ and $y$, and $z$ is the central node).</p>

<p><img src="https://i.sstatic.net/buKAm.jpg" alt="enter image description here"></p>

<p>Now you can pick some pairs of nodes at the two endpoints: $(x,y),(x_1,y_1),(x_2,y_2),...$. In this way you end up with an instance of your problem that has a solution if and only if the two original graphs are isomorphic.</p>

CC BY-SA 3.0
2014-07-14T13:49:31.097Z
Nice! The proof looks right to me. But this is just a GI-hardness proof; it isn't immediately clear to me that GI is an upper bound. I don't see why GI-hardness would make it hard to prove that the problem is NP-hard. Also, although it is obviously hard to prove unconditionally that it is *not* NP-complete, one could hope to prove that it is in, say, coAM, and hence only NP-complete if PH collapses. Again, I don't see why a GI-hardness result should make a coAM upper bound any more difficult...
Joshua Grochow
CC BY-SA 3.0
2014-07-14T14:00:33.100Z
@JoshuaGrochow: indeed you are right, I quickly wrote it and missed the correct order of $\leq$ ("it should be hard to prove that it is in P" looks better but it is obvious, so I deleted the final note at the end of the answer).
Marzio De Biasi
CC BY-SA 3.0
2014-07-14T14:24:40.550Z
I think I didn't get something, maybe both $G_1$ and $G_2$ are admitting automorphism, then this cannot be GI-complete (with current beliefs). P.S: But your reduction is a nice motivation toward NP-completeness of GI by considering NPC of fixed point free automorphism.
Saeed
CC BY-SA 3.0
2014-07-14T14:38:59.700Z
@Saeed: informally, the extra contraint $f(u)=v$ (or $f(v)=u$) (side note: only one pair $(u,v)$ is needed for the above contruction) forces the two halves to "WRAP" one on the other in a valid automorphism. So the two halves must be isomorphic (if and only if the original graphs are isomorphic)
Marzio De Biasi
CC BY-SA 3.0
2014-07-14T14:51:38.147Z
I made a mistake, I thought that wrapping happens just on path part not on whole graph, and I thought maybe we have two graph which are admitting automorphism then this does not lead to GI-completeness.
Saeed
CC BY-SA 3.0
2014-07-14T15:32:55.580Z
What software are you using for graph drawing?
joro
CC BY-SA 3.0
2014-07-14T15:44:15.880Z
@joro: [yEd](http://www.yworks.com/en/downloads.html#yEd) ... great tool for (visual) drawing graphs very quickly (but not as powerful as TikZiT, especially for rendering the labels)
Marzio De Biasi
CC BY-SA 3.0
2014-07-15T02:54:10.317Z
@MarzioDeBiasi Good partial answer. :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-15T03:04:58.750Z
@JoshuaGrochow It would be nice if you find conditional proof that my problem can not be $NP$-hard and for me this is the most interesting part (when we compare it to the fixed-point free automorphism problem). That would be an excellent evidence.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-14T13:03:50.233Z
2014-07-14T14:00:56.073Z
2014-07-14T14:00:56.073Z
Marzio De Biasi
<p>I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).</p>

<p><strong>Restricted GA</strong></p>

<p><strong>Input:</strong> Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \ne v$ ( all pairs $(u_i, v_i)$ are pair-wise disjoint and $0 \le \epsilon \le 1$)</p>

<p><strong>Question:</strong> Is there a non-trivial automorphism $f$ of $G$ such that for every pair $p_i$ either $v_i=f(u_i)$ or $u_i= f(v_i)$?</p>

<p>This problem is at least as hard as Graph Automorphism Problem. I guess it is harder than Graph Automorphism but not $NP$-hard.</p>

<blockquote>
  <p>Is there a computational evidence that supports (or against) my guess regarding the complexity of this variant of $GA$?</p>
</blockquote>

<p><strong>Motivation</strong>: My problem is a relaxation of NP-complete problem known as fixed-point free graph automorphism problem.</p>

<p><strong>EDIT</strong>: Cross-posted on <a href="https://mathoverflow.net/questions/176073/how-hard-is-a-variant-of-graph-automorphism-problem">mathOverflow</a></p>

CC BY-SA 3.0
2014-07-13T04:05:25.037Z
All node pairs $p_i=(u_i, v_i)$ are pair-wise disjoint.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-13T06:33:43.457Z
To make sure I understand correctly, is the following equivalent to your problem? Given an undirected graph $G(E,V)$ and a partition of  $V$ (the vertices) into parts of size exactly two, is there an automorphism such that, for each part $\{u_i, v_i\}$ of the partition, either $f(u_i) = v_i$ or $f(v_i) = u_i$.
Joshua Grochow
CC BY-SA 3.0
2014-07-13T10:21:05.170Z
@JoshuaGrochow since your comment, I edited the question. The pairs do not form a partition of $V$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-13T15:16:17.147Z
Okay, so just to clarify: if $\epsilon$ *had been* 1 (I understand that you want it to be strictly $< 1$), then the pairs you're talking about would have been a partition as described in my previous comment?
Joshua Grochow
CC BY-SA 3.0
2014-07-13T17:18:31.927Z
@JoshuaGrochow Yes, and the problem would be trivially in $P$. If $ \epsilon = 0$ then the problem is $GA$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-13T17:55:15.323Z
Even for $\epsilon=1$, I don't see why it's trivially in P. For a naive algorithm, there are $2^n$ choices (in each pair, whether $u_i \mapsto v_i$ or vice versa), and for each such choice one must determine whether it extends to an automorphism, which involves figuring out where the other member of each pair gets mapped (which can be any of the remaining $n/2$ vertices). What algorithm did you have in mind?
Joshua Grochow
CC BY-SA 3.0
2014-07-13T18:00:49.170Z
My intuition is that if $G$ has such automorphism on the given set of pairs then $u_i$ and $v_i$ are interchangeable. This would lead to P-time algorithm. Right?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-13T18:06:01.480Z
If that were true it would lead to a P-time algorithm, since then there is just one automorphism to check. But it's not necessarily true. In the $\epsilon=1$ case, for any graph that has a fixed-point free automorphism $\pi$ such that the cycles of $\pi$ all have even length, one can construct a partition of the vertices into pairs so that $\pi$ is a solution to your problem. (This is essentially a complete characterization in the $\epsilon=1$ case.)
Joshua Grochow
CC BY-SA 3.0
2014-07-13T19:57:23.257Z
@JoshuaGrochow So even if $\epsilon = 1$ then you do not see a P-time algorithm for my problem. If that the case, I will modify it so that $ 0 \le \epsilon \le 1 $.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-14T09:45:50.913Z
This question is cross-posted to MathOverflow at http://mathoverflow.net/questions/176073/ .  Next time you cross-post, please link the posts both ways.
Zsbán Ambrus
CC BY-SA 3.0
2014-07-31T06:45:30.787Z
In addition, you are not supposed to simultaneously cross-post: you should only consider cross-posting if a reasonable amount of time has passed (say a week) with no answers on one of the forums; and you should cross-link them and update both to summarize what has been found on the other.  See the faq for details.
D.W.
<cc.complexity-theory><graph-theory><graph-isomorphism>
How hard is a variant of graph automorphism problem?
Mohammad Al-Turkistany
# How hard is a variant of graph automorphism problem?

(Asked by: username_0 on 2014-07-13)

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).

**Restricted GA**

**Input:** Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \ne v$ ( all pairs $(u\_i, v\_i)$ are pair-wise disjoint and $0 \le \epsilon \le 1$)

**Question:** Is there a non-trivial automorphism $f$ of $G$ such that for every pair $p\_i$ either $v\_i=f(u\_i)$ or $u\_i= f(v\_i)$?

This problem is at least as hard as Graph Automorphism Problem. I guess it is harder than Graph Automorphism but not $NP$-hard.

> Is there a computational evidence that supports (or against) my guess regarding the complexity of this variant of $GA$?

**Motivation**: My problem is a relaxation of NP-complete problem known as fixed-point free graph automorphism problem.

**EDIT**: Cross-posted on [mathOverflow](https://mathoverflow.net/questions/176073/how-hard-is-a-variant-of-graph-automorphism-problem)

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

> **Comments:**
> **username_0**: All node pairs $p_i=(u_i, v_i)$ are pair-wise disjoint.  
> **username_1**: To make sure I understand correctly, is the following equivalent to your problem? Given an undirected graph $G(E,V)$ and a partition of  $V$ (the vertices) into parts of size exactly two, is there an automorphism such that, for each part $\{u_i, v_i\}$ of the partition, either $f(u_i) = v_i$ or $f(v_i) = u_i$.  
> **username_0**: @JoshuaGrochow since your comment, I edited the question. The pairs do not form a partition of $V$.  
> **username_1**: Okay, so just to clarify: if $\epsilon$ *had been* 1 (I understand that you want it to be strictly $< 1$), then the pairs you're talking about would have been a partition as described in my previous comment?  
> **username_0**: @JoshuaGrochow Yes, and the problem would be trivially in $P$. If $ \epsilon = 0$ then the problem is $GA$.  
> **username_1**: Even for $\epsilon=1$, I don't see why it's trivially in P. For a naive algorithm, there are $2^n$ choices (in each pair, whether $u_i \mapsto v_i$ or vice versa), and for each such choice one must determine whether it extends to an automorphism, which involves figuring out where the other member of each pair gets mapped (which can be any of the remaining $n/2$ vertices). What algorithm did you have in mind?  
> **username_0**: My intuition is that if $G$ has such automorphism on the given set of pairs then $u_i$ and $v_i$ are interchangeable. This would lead to P-time algorithm. Right?  
> **username_1**: If that were true it would lead to a P-time algorithm, since then there is just one automorphism to check. But it's not necessarily true. In the $\epsilon=1$ case, for any graph that has a fixed-point free automorphism $\pi$ such that the cycles of $\pi$ all have even length, one can construct a partition of the vertices into pairs so that $\pi$ is a solution to your problem. (This is essentially a complete characterization in the $\epsilon=1$ case.)  
> **username_0**: @JoshuaGrochow So even if $\epsilon = 1$ then you do not see a P-time algorithm for my problem. If that the case, I will modify it so that $ 0 \le \epsilon \le 1 $.  
> **username_2**: This question is cross-posted to MathOverflow at http://mathoverflow.net/questions/176073/ .  Next time you cross-post, please link the posts both ways.  
> **username_3**: In addition, you are not supposed to simultaneously cross-post: you should only consider cross-posting if a reasonable amount of time has passed (say a week) with no answers on one of the forums; and you should cross-link them and update both to summarize what has been found on the other.  See the faq for details.  

---

## 1 answers

### Answer by username_4 on 2014-07-14. Score: 5

If I understood well the question, this is an attempt to prove that your problem is $GI$-complete.

Given two graphs $G\_1, G\_2$ connect all the nodes of $G\_1$ to a new node $x$ and all the nodes of $G\_2$ to a new node $y$. Then connect $x$ and $y$ with a path of new nodes: $ x\_1, x\_2, ... x\_k,\; z\;, y\_k, ...,y\_2, y\_1$ (there is an odd number of nodes between $x$ and $y$, and $z$ is the central node).

![enter image description here](https://i.sstatic.net/buKAm.jpg)

Now you can pick some pairs of nodes at the two endpoints: $(x,y),(x\_1,y\_1),(x\_2,y\_2),...$. In this way you end up with an instance of your problem that has a solution if and only if the two original graphs are isomorphic.

> **Comments:**
> **username_1**: Nice! The proof looks right to me. But this is just a GI-hardness proof; it isn't immediately clear to me that GI is an upper bound. I don't see why GI-hardness would make it hard to prove that the problem is NP-hard. Also, although it is obviously hard to prove unconditionally that it is *not* NP-complete, one could hope to prove that it is in, say, coAM, and hence only NP-complete if PH collapses. Again, I don't see why a GI-hardness result should make a coAM upper bound any more difficult...  
> **username_4**: @JoshuaGrochow: indeed you are right, I quickly wrote it and missed the correct order of $\leq$ ("it should be hard to prove that it is in P" looks better but it is obvious, so I deleted the final note at the end of the answer).  
> **username_5**: I think I didn't get something, maybe both $G_1$ and $G_2$ are admitting automorphism, then this cannot be GI-complete (with current beliefs). P.S: But your reduction is a nice motivation toward NP-completeness of GI by considering NPC of fixed point free automorphism.  
> **username_4**: @username_5: informally, the extra contraint $f(u)=v$ (or $f(v)=u$) (side note: only one pair $(u,v)$ is needed for the above contruction) forces the two halves to "WRAP" one on the other in a valid automorphism. So the two halves must be isomorphic (if and only if the original graphs are isomorphic)  
> **username_5**: I made a mistake, I thought that wrapping happens just on path part not on whole graph, and I thought maybe we have two graph which are admitting automorphism then this does not lead to GI-completeness.  
> **username_6**: What software are you using for graph drawing?  
> **username_4**: @username_6: [yEd](http://www.yworks.com/en/downloads.html#yEd) ... great tool for (visual) drawing graphs very quickly (but not as powerful as TikZiT, especially for rendering the labels)  
> **username_0**: @MarzioDeBiasi Good partial answer. :)  
> **username_0**: @JoshuaGrochow It would be nice if you find conditional proof that my problem can not be $NP$-hard and for me this is the most interesting part (when we compare it to the fixed-point free automorphism problem). That would be an excellent evidence.  

---

