Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, if there is a permutation $\Pi$ such that $(i,j)$ is an edge in $G_1$ if and only if $(\Pi(i),\Pi(j))$ is an edge in $G_2$. The Graph Isomorphism Problem is the problem of deciding whether two given graphs are isomorphic.

Is there an operation on graphs that produces "gap amplification" in the style of Dinur's proof of the PCP Theorem? In other words, is there a polynomial time computable transformation from $(G_1,G_2)$ to $(G'_1,G'_2)$ such that

  • if $G_1$ and $G_2$ are isomorphic, then $G'_1$ and $G'_2$ are also isomorphic, and
  • if $G_1$ and $G_2$ are not isomorphic, then for each permutation $\Pi$, the graph $G'_1$ is "$\epsilon$-far" from $\Pi(G'_2)$ for some small constant $\epsilon$, where $\epsilon$-far means that if we choose $(i,j)$ uniformly at random, then with probability $\epsilon$ either
    • $(i,j)$ is an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is not an edge of $G'_2$, or
    • $(i,j)$ is not an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is an edge of $G'_2$.
  • 5
    $\begingroup$ @domotorp: “Polynomial-time transformation” is a standard terminology to refer to a deterministic polynomial-time Turing machine whose input and output are both strings. In this case, this Turing machine takes pair (G1, G2) as input and produces pair (G′1, G′2) as output. Each graph is encoded as an adjacent matrix, for example. $\endgroup$ Commented Nov 25, 2011 at 15:27
  • 1
    $\begingroup$ I thought the PCP theorem was valid for any NP problem, so in particular it should hold for Graph Isomorphism ? $\endgroup$
    – Denis
    Commented May 12, 2012 at 18:01
  • 2
    $\begingroup$ @dkuper The author means to ask if there is a gap-amplifying reduction which reduces instances of graph isomorphism to instances of graph isomorphism with a bigger gap; he is not asking about the PCP Theorem directly, just about a technique used in proving hardness of approximation... $\endgroup$ Commented Sep 26, 2012 at 22:31
  • 3
    $\begingroup$ Probably a long shot, but could you show that if this were the case, then you could solve graph isomorphism in quantum polynomial time? $\endgroup$
    – Neal Young
    Commented Nov 3, 2012 at 17:43
  • 3
    $\begingroup$ It is consistent with current state of knowledge that even SAT has linear time algorithm so what you have written seems unlikely to be known. If it is please add a reference to your answer. $\endgroup$
    – Kaveh
    Commented Nov 14, 2013 at 22:47

1 Answer 1


I do not know if such a thing could exist or not. But it is interesting (and perhaps timely) to note that such a "gap amplification" would likely imply a quasipolynomial time algorithm for graph isomorphism (different than the recently announced one)

In this paper, an approximation algorithm is given for the "MAX-PGI" problem of maximizing matched pairs of edges/non-edges; if we reduce from GI to "Gap-MAX-PGI", then we can approximate to distinguish which side of the gap we are on.

So, I think Dinur's proof of the PCP theorem is unlikely to be directly generalizable to such a "gap amplifier", given the hurdles that would have to be overcome.

  • $\begingroup$ From the linked paper: "We also consider the corresponding minimization problem (of mismatches) and prove that it is NP-hard to $\epsilon$-approximate for any constant factor $\epsilon>0$. Further, we show that it is also NP-hard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94." $\endgroup$
    – Neal Young
    Commented Mar 22 at 0:31

Your Answer

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

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