53
$\begingroup$

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$.
$\endgroup$
  • 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$ – Tsuyoshi Ito Nov 25 '11 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 May 12 '12 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$ – argentpepper Sep 26 '12 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 Nov 3 '12 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 Nov 14 '13 at 22:47
2
+50
$\begingroup$

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.

$\endgroup$

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.