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

Improve this question
$\endgroup$
11
  • $\begingroup$ All node pairs $p_i=(u_i, v_i)$ are pair-wise disjoint. $\endgroup$
    – Mohammad Al-Turkistany
    Jul 13, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 6:45

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$
9
  • 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, 2014 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, 2014 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, 2014 at 14:24
  • 1
    $\begingroup$ What software are you using for graph drawing? $\endgroup$
    – joro
    Jul 14, 2014 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, 2014 at 15:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.