2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ All node pairs $p_i=(u_i, v_i)$ are pair-wise disjoint. $\endgroup$ – Mohammad Al-Turkistany Jul 13 '14 at 4:05
  • $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Jul 13 '14 at 6:33
  • $\begingroup$ @JoshuaGrochow since your comment, I edited the question. The pairs do not form a partition of $V$. $\endgroup$ – Mohammad Al-Turkistany Jul 13 '14 at 10:21
  • 3
    $\begingroup$ This question is cross-posted to MathOverflow at mathoverflow.net/questions/176073 . Next time you cross-post, please link the posts both ways. $\endgroup$ – Zsbán Ambrus Jul 14 '14 at 9:45
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jul 31 '14 at 6:45
4
$\begingroup$

As far as I can see, Restricted GA is NP-complete. My proof has been originally posted here

$\endgroup$
5
$\begingroup$

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

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.

$\endgroup$
  • 3
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Jul 14 '14 at 13:49
  • $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Jul 14 '14 at 14:00
  • $\begingroup$ 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. $\endgroup$ – Saeed Jul 14 '14 at 14:24
  • 1
    $\begingroup$ What software are you using for graph drawing? $\endgroup$ – joro Jul 14 '14 at 15:32
  • 2
    $\begingroup$ @joro: yEd ... great tool for (visual) drawing graphs very quickly (but not as powerful as TikZiT, especially for rendering the labels) $\endgroup$ – Marzio De Biasi Jul 14 '14 at 15:44

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.