[Math] A combination of two well-known complexity problems

computational complexity

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other doesn't. Can you tell in polynomial time which situation you are in? Obviously you can if graph isomorphism is easy or if finding Hamilton cycles is easy, so let's assume that they are both hard.

There may be a trivial answer, but it seems to me that the question is not obviously as hard as graph isomorphism, since if you can always solve it, it isn't clear that you can modify the algorithm to tell whether an arbitrary pair of graphs is isomorphic. If there isn't a trivial answer, then my guess is that the question is more or less as hard as resolving the P versus NP problem or the graph isomorphism problem, but maybe it isn't, since you're allowed to assume answers to those problems. Anyhow, the question has just occurred to me and I haven't yet found a reason not to like it, so here it is.

Best Answer

The Graph Isomorphism problem can be reduced to the Gowers hybrid problem.

Given a pair $A,B$ of graphs, each with $n$ vertices, we seek to construct a graph $G_{A,B}$ whose Hamiltonicity is equivalent to $A$ and $B$ being isomorphic. Moreover, we shall construct this carefully as to not break any symmetry: if $A,A'$ are isomorphic, and $B,B'$ are isomorphic, then so are $G_{A,B}$ and $G_{A',B'}$.

Now, given a graph isomorphism problem determined by graphs $A,B$, we consider the Gowers hybrid problem with graphs $G_{A,A}$ and $G_{A,B}$. By construction, these are isomorphic if $A, B$ are isomorphic. Otherwise, $G_{A,A}$ is Hamiltonian and $G_{A,B}$ is not.

Provided we can perform such a construction in polynomial time, and ensure that the order of $G_{A,B}$ is polynomial in $n$, then Graph Isomorphism and the Gowers hybrid problem are equally difficult (i.e. there is a polynomial-time reduction between them).

The rest of this answer is simply describing this construction.

Let $A,B$ be a pair of graphs on the vertex-set $[n] := \{ 1, 2, \dots, n \}$. We create a variable $v_{a,b}$ for every ordered pair $(a,b)$ of a vertex in $A$ and a vertex in $B$. Then, we write down the clauses:

  • $(\neg v_{a_i,b_j} \lor \neg v_{a_i,b_k}) \forall i,j,k \in [n]$
  • $(\neg v_{a_j,b_i} \lor \neg v_{a_k,b_i}) \forall i,j,k \in [n]$
  • $(v_{a_i,b_1} \lor v_{a_i,b_2} \lor \cdots \lor v_{a_i,b_n}) \forall i \in [n]$
  • $(v_{a_1,b_i} \lor v_{a_2,b_i} \lor \cdots \lor v_{a_n,b_i}) \forall i \in [n]$

which specify that our variables describe a bijection between the vertex-sets of $A$ and $B$. Then, for every edge $(a,a')$ and non-edge $(b,b')$, we specify the clause:

  • $(\neg v_{a,b} \lor \neg v_{a',b'})$

and do the same for non-edges in $A$ and edges in $B$. This forces our variables to specify an isomorphism between the graphs $A$ and $B$.

Now, the following page reduces $3$-SAT to vertex cover:

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2001/CW/npproof.html

We need $k$-SAT rather than $3$-SAT, but we can note that the triangle-shaped gadget described on this page can be replaced with an arbitrary-sized complete graph $K_k$ to allow clauses of arbitrary length: we can cover the edges within the complete graph with $k-1$ vertices (and no fewer) provided at least one of the adjoining $k$ edges is already covered.

So far, we have constructed a vertex-covering problem of a graph which (up to isomorphism) only depends on the graphs $A, B$ up to isomorphism. Moreover, it has a vertex cover of the correct size if and only if $A$ and $B$ are isomorphic.

Now appeal to this result:

http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Hamiltonian%20Circuits.pdf

which shows how to convert a vertex-covering problem into a Hamiltonian cycle problem, again canonically (so not depending on how we've labelled the vertices of our graphs).

Hence, we can canonically construct a graph $G_{A,B}$ which has a Hamiltonian cycle if and only if $A$ and $B$ are isomorphic. Moreover, $G_{A,B}$ up to isomorphism only depends on $A, B$ up to isomorphism. Also, $G_{A,B}$ is only of size polynomial in $n$ (namely $O(n^4)$ vertices if I counted correctly).

The result follows.

Related Question