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$.
Improve this question
$\endgroup$
9
  • 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, 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
    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$
    – argentpepper
    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
    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
    Nov 14, 2013 at 22:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.