47

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo." But besides that, there are several others: Show that your problem is in NP ∩ coNP. (Example: Factoring.) Show that your problem is solvable in quasipolynomial time. (Examples: VC dimension, approximating free games.) Show that your ...


28

These problems are polynomially equivalent. Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are. Attach a clique of size $n+1$ to an arbitrary vertex of each graph. Test whether the resulting graphs are isomorphic or not. If they are, then we can conclude that there's an isomorphism ...


25

It's GI-complete which means it's probably not NP-complete. Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges) ...


23

From the comment above: if a problem seems hard enough, but you are not able to prove that it is NP-complete, a quick check is to count the number of strings of length $n$ in the language: if the set is sparse it is unlikely to be NPC, otherwise P=NP by Mahaney's theorem ... so it's better to direct efforts towards proving that it is in P :-) :-) An example ...


23

Here are three additions to Scott's list: Show your problem is in fewP. This means that the number of solutions is bounded by some polynomial. (Example: Turnpike problem). No NP-complete problem is known to be in fewP. (impossible unless fewP=NP). Show your problem is in $LOGNP$ or in $NP[log^2n]$ (Can be solved using limited number of nondeterministic ...


20

Aggregating comments by Thomas Klimpel, Sasho Nikolov and Mohammad Al-Turkistany into a community answer: The correction (and hence the quasi-polynomial result) was immediately supported by Harald Andrés Helfgott. His expository paper (https://arxiv.org/abs/1701.04372) and its translation (https://arxiv.org/abs/1710.04574) are all the support that is ...


19

Graph isomorphism is not known to be in $\mathsf{UP}$ nor known to be in $\mathsf{coUP}$. For $\mathsf{UP}$: the natural nondeterministic algorithm - guess a map between the two graphs and check if it's an isomorphism - has either 0 witnesses (iff the graphs are not isomorphic) or $|\text{Aut}(G)|$ witnesses. Although most graphs have $|\text{Aut}(G)|=1$ (...


19

I highly recommend Paolo Codenotti's thesis for the group-theoretic aspects, and the book The Graph Isomorphism Problem: Its Structural Complexity by Johannes Köbler, Uwe Schöning, and Jacobo Torán for the complexity aspects.


18

Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact. 1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199. 2- R. Mathon, Sample graphs for isomorphism ...


18

For graphA.txt: 25 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 ...


17

One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic. And in the graph case it's possible to transform graphs into manifolds in such a way that the ...


17

More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the algorithm, that is, without the reduction of domotorp's answer. In terms of deciding existence of an isomorphism (resp., unknotting) vs actually finding one, the ...


14

The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult Paolo Codenotti's Ph.D. thesis for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the ...


13

For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open. pathwidth / treewidth (see [2], has been asked here), maybe solved: http://arxiv.org/abs/1404.0818 cutwidth / bandwidth [1] treewidth-k vertex deletion set size (feedback vertex set number in [7]) tree / ...


13

For the second question: Fixing rank-width (equivalently, fixing clique-width), polynomial time solvability of GI is not known. Recently, Mamadou Kanté posed an open question if the graph isomorphism problem can be solved in polynomial time for graphs of bounded linear rank-width.


13

Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two isomorphic Johnson graphs in polynomial time. Johnson graphs come into the proof in a different way. Very roughly speaking, the proof juggles between group-theoretic ...


12

As pointed out by @Marzio De Biasi, the problem you are asking about is $\mathsf{coNP}$-complete, by a direct reduction from TAUTOLOGY: given a boolean formula $\varphi$, is $\varphi$ equivalent to the constant 1 circuit? It is easily seen to be in $\mathsf{coNP}$. (Given that Marzio really answered the question, I suggest anyone thinking of upvoting this ...


11

Matrices A and B whose elements are in a field F are similar (in F) if and only if they have the same Frobenius normal form. According to a quick search, it seems that the Frobenius normal form of an n×n matrix can be computed with O(n3) field operations [Sto98], and that this can be improved to something comparable to the complexity of matrix ...


11

I believe all known GI-completeness results are functorial (definition in the paper), and Babai has recently shown (ITCS 2014, free author's copy) - based on bounds on the structure of automorphism groups of strongly regular graphs - that there is no functorial reduction from GI to strongly regular GI.


11

The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See M. Grohe, Equivalence in finite-variable logics is complete for polynomial time. Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.) Note that colour refinement equivalence corresponds to ...


11

Upon request of Marzio De Biasi I'm converting my comment into an answer. A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open: 1) Is isomorphism of asymmetric graphs in P? 2) Can ...


11

Let $g_1, \ldots, g_k, g \in S_n$ where $S_n$ is the permutation group on $n$ elements. Testing whether $g \in \langle g_1, \ldots, g_k \rangle$ can be done in $\text{NC} \subseteq \text{P}$ by [1]. Let $u, v \in \Gamma^n$, then simply guess $g \in S_n$, test in polynomial time whether $g \in G$ and whether $g(u) = v$. This yields an $\text{NP}$ upper bound. ...


11

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.) Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS ...


11

Due to Babai's recent result (see the paper) $GI$ is in quasi-polynomial time ($QP$). If $GI$ is $NP$-complete, then it implies $NP\subseteq QP=DTIME(n^{polylog\, n})$. This, in turn, implies $EXP=NEXP$, see here. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.


11

The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than $n!$ but still exponential, OEIS A186202. The number of bits needed to store an unlabeled graph is $log_{2}$ of ${n\choose 2}-n log(n) +O(n)$. See Naor, Moni. "Succinct representation of general unlabeled graphs." ...


11

Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If there were mature algorithms for $p$-group isomorphism that fully exploited the available structure of $p$-groups and still would have no hope to achieve polynomial ...


10

Your problem is known as ($\Gamma$-)string $G$-isomorphism. It is in a fairly narrow class of problems around Graph Isomorphism: it's at least as hard as GI, and is in $\mathsf{NP} \cap \mathsf{coAM}$. Reduction from GI: let $N = \binom{n}{2}$, and let $G \leq S_N$ be the induced action of $S_n$ on pairs. $\mathsf{coAM}$ protocol: Arthur randomly chooses ...


10

The paper you linked in the comments - and references therein - already seems to answer your first question. For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq ...


9

If H is the cycle on |G| vertices (and is of maximum degree 2), then this is the Hamiltonian cycle problem. Seems like your problem is NP-hard.


9

The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). ...


Only top voted, non community-wiki answers of a minimum length are eligible