<p>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)</p>

<p>In <a href="http://eccc.hpi-web.de/report/2012/078/" rel="nofollow">this paper</a>, 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.</p>

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

CC BY-SA 4.0
2024-03-22T00:31:55.463Z
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."
Neal Young
CC BY-SA 3.0
2015-12-24T07:50:33.767Z
2015-12-24T07:50:33.767Z
Joe Bebel
<p>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.</p>

<p>Is there an operation on graphs that produces "gap amplification" in the style of <a href="https://www.lri.fr/perso/~mdr/pcp-newproof.pdf">Dinur's proof of the PCP Theorem</a>? In other words, is there a polynomial time computable transformation from $(G_1,G_2)$ to $(G'_1,G'_2)$ such that </p>

<ul>
<li>if $G_1$ and $G_2$ are isomorphic, then $G'_1$ and $G'_2$ are also isomorphic, and</li>
<li>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
<ul>
<li>$(i,j)$ is an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is not an edge of $G'_2$, or</li>
<li>$(i,j)$ is not an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is an edge of $G'_2$.</li>
</ul></li>
</ul>

CC BY-SA 3.0
2011-11-25T15:27:38.853Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-12T18:01:20.190Z
I thought the PCP theorem was valid for any NP problem, so in particular it should hold for Graph Isomorphism ?
Denis
CC BY-SA 3.0
2012-09-26T22:31:49.773Z
@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...
argentpepper
CC BY-SA 3.0
2012-11-03T17:43:19.723Z
Probably a long shot, but could you show that if this were the case, then you could solve graph isomorphism in quantum polynomial time?
Neal Young
CC BY-SA 3.0
2013-11-14T17:23:41.233Z
Every problem related to permutations is unsolvable in linear time, if you find a solution then you would have solved P=NP.
Skywalker
CC BY-SA 3.0
2013-11-14T22:47:03.470Z
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.
Kaveh
CC BY-SA 3.0
2014-11-03T20:53:36.750Z
(1/2) Here is some information on recent work that does not answer the question, but has a similar flavor, when viewed in a certain light. If we view the graph isomorphism problem as the problem of finding a permutation matrix $P$ satisfying $PA = BP$, then consider the relaxation to doubly stochastic matrices $S$ such that $SA = BS$, we get the "fractional graph isomorphism" problem. This can be further relaxed as an optimization problem of the form "minimize $\|SA - BS\|^2$, subject to $S \mathbf{1} = \mathbf{1}^T S = \mathbf{1}$.
argentpepper
CC BY-SA 3.0
2014-11-03T20:56:26.577Z
(2/2) This optimization problem is the "approximate fractional graph isomorphism problem". In this problem, our goal is to find an $S$ that minimizes the number of "edge disagreements" between the graphs $A$ and $B$. When there is a solution $S$ that causes the objective function to have the value $0$, it is an exact solution to the fractional graph isomorphism problem. When $S$ is furthermore a permutation matrix, it is an exact solution to the graph isomorphism problem.
argentpepper
CC BY-SA 3.0
2014-11-03T20:59:56.207Z
(3/2, woops) Solving the approximate fractional graph isomorphism problem amounts to iteratively reducing the number of edge disagreements; this is what happens in, for example, "Power Iterated Color Refinement" http://tinyurl.com/ptujvjy. This question essentially wants to do the exact opposite: find an operation that causes $\|SA - BS\|$ to get farther away from the optimum objective value, for every $S$.
argentpepper
CC BY-SA 4.0
2024-03-22T00:26:08.277Z
Of course, if GI is in P, then there is, trivially, such an amplification operation.  (Just test if $G_1$ and $G_2$ are isomorphic, and if not take $G'_1$ and $G'_2$ to be, e.g. a graph with no edges and a complete graph.)  The point here is that a proof that there is no such amplification operation would also prove that GI is not in P.  So probably hard to prove that there is none.
Neal Young
<cc.complexity-theory><graph-isomorphism><pcp>
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Andre Chailloux
# Is there a gap amplification type of result for the Graph Isomorphism Problem?

(Asked by: username_0 on 2011-11-25)

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](https://www.lri.fr/perso/~mdr/pcp-newproof.pdf)? 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$.

**Tags:** cc.complexity-theory, graph-isomorphism, pcp
> **Comments:**
> **username_1**: @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.  
> **username_2**: I thought the PCP theorem was valid for any NP problem, so in particular it should hold for Graph Isomorphism ?  
> **username_3**: @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...  
> **username_4**: Probably a long shot, but could you show that if this were the case, then you could solve graph isomorphism in quantum polynomial time?  
> **username_5**: Every problem related to permutations is unsolvable in linear time, if you find a solution then you would have solved P=NP.  
> **username_6**: 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.  
> **username_3**: (1/2) Here is some information on recent work that does not answer the question, but has a similar flavor, when viewed in a certain light. If we view the graph isomorphism problem as the problem of finding a permutation matrix $P$ satisfying $PA = BP$, then consider the relaxation to doubly stochastic matrices $S$ such that $SA = BS$, we get the "fractional graph isomorphism" problem. This can be further relaxed as an optimization problem of the form "minimize $\|SA - BS\|^2$, subject to $S \mathbf{1} = \mathbf{1}^T S = \mathbf{1}$.  
> **username_3**: (2/2) This optimization problem is the "approximate fractional graph isomorphism problem". In this problem, our goal is to find an $S$ that minimizes the number of "edge disagreements" between the graphs $A$ and $B$. When there is a solution $S$ that causes the objective function to have the value $0$, it is an exact solution to the fractional graph isomorphism problem. When $S$ is furthermore a permutation matrix, it is an exact solution to the graph isomorphism problem.  
> **username_3**: (3/2, woops) Solving the approximate fractional graph isomorphism problem amounts to iteratively reducing the number of edge disagreements; this is what happens in, for example, "Power Iterated Color Refinement" http://tinyurl.com/ptujvjy. This question essentially wants to do the exact opposite: find an operation that causes $\|SA - BS\|$ to get farther away from the optimum objective value, for every $S$.  
> **username_4**: Of course, if GI is in P, then there is, trivially, such an amplification operation.  (Just test if $G_1$ and $G_2$ are isomorphic, and if not take $G'_1$ and $G'_2$ to be, e.g. a graph with no edges and a complete graph.)  The point here is that a proof that there is no such amplification operation would also prove that GI is not in P.  So probably hard to prove that there is none.  

---

## 1 answers

### Answer by username_7 on 2015-12-24. Score: 2

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](http://eccc.hpi-web.de/report/2012/078/), 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.

> **Comments:**
> **username_4**: 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."  

---

