2022 Developer Survey is open! Take survey.
28 votes
Accepted

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

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+...
user avatar
  • 13.5k
27 votes
Accepted

Is DAG isomorphism NP-C

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$, ...
user avatar
23 votes
Accepted

What's the status of Babai's Graph isomorphism result?

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 ...
22 votes
Accepted

Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

For graphA.txt: ...
user avatar
17 votes

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

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 ...
user avatar
14 votes
Accepted

What evidence is there that Graph Isomorphism is not in $P$?

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 ...
user avatar
13 votes
Accepted

questions on implications Babais quasi P time graph isomorphism result

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 ...
user avatar
  • 14.1k
11 votes

Strongly Regular Graph and GI-Completeness

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 ...
user avatar
11 votes
Accepted

Testing isomorphism of asymmetric graphs

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 ...
user avatar
11 votes
Accepted

Complexity of the coset intersection problem

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 ...
user avatar
11 votes
Accepted

Complexity of permutation related problems

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]. ...
user avatar
11 votes
Accepted

Evidence that Graph Isomorphism problem is not $NP$-complete

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=...
user avatar
11 votes

What evidence is there that Graph Isomorphism is not in $P$?

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 ...
user avatar
10 votes

Complexity of permutation related problems

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}$....
user avatar
10 votes
Accepted

Connections between Graph Isomorphism and Polynomial Equivalence

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 ...
user avatar
9 votes

Complexity of the coset intersection problem

Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in this answer, testing whether $g \in \langle g_1, \ldots, g_k\rangle$ is in $\text{...
user avatar
9 votes
Accepted

Graph isomorphism with equivalence relation on the vertex set

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 ...
user avatar
9 votes
Accepted

Is the finite inverse semigroup isomorphism problem GI-complete?

Yes, the finite inverse semigroup isomorphism problem is GI-complete! This is a corollary of Theorem: Lattice isomorphism is isomorphism complete from section 7.2 Lattices and Posets in Booth, ...
user avatar
9 votes
Accepted

Number of Automorphisms of a graph for graph isomorphism

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-...
user avatar
9 votes

What evidence is there that Graph Isomorphism is not in $P$?

Kozen in his paper, A clique problem equivalent to graph isomorphism, gives an evidence that $GI$ is not in $P$. The following is from the paper: "Nevertheless, it is likely that finding a ...
user avatar
9 votes
Accepted

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

Thanks to my colleague Maxim Zhukovskii for suggesting this answer. It turns out that the answer is negative, and the counterexample is rather simple. Just take $G=K_m\sqcup \overline{K_m}$ and $H=K_{...
user avatar
8 votes

graph isomorphism given a partial isomorphism

Only an extended comment: Lipton et al. proved [1] that if we have access to an oracle that given two graphs on $n$ vertices, reveals a partial map on at least $(3+\epsilon)\log n$ vertices (for some ...
user avatar
8 votes
Accepted

Can graph isomorphism be decided with square root bounded nondeterminism?

First, (as has now been edited into the question statement) a positive answer to your question would immediately improve the state of the art in worst-case bounds for graph isomorphism. For a $O(\sqrt{...
user avatar
8 votes

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial

This paper was presented at FOCS 2015 and is published in those proceedings. As far as I am concerned, this means it was peer reviewed and found to be plausibly correct, within the limits of a ...
user avatar
  • 2,295
8 votes
Accepted

Problem of graph bi-partition (related to graph isomorphism)

Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect ...
user avatar
8 votes
Accepted

On a GI complete class

No, that's not $\mathrm{GI}$-complete unless $\mathrm{GI}\in\textsf{P}$. Indeed, isomorphism of such graphs can be checked in polynomial time. First, note that a bipartite graph is triangle-free. ...
user avatar
8 votes
Accepted

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex ...
user avatar
  • 3,196
7 votes

Canonical way of coloring graphs (individualization) for isomorphism purpose

Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ ...
user avatar
6 votes
Accepted

Complexity of counting graph endomorphisms

Counting endomorphisms or fixed-point-free endomorphisms is complete for $\mathsf{FP}^{\mathsf{\# P}}$: given a connected graph $G$, consider the graph $G'$ which is the disjoint union of $G$ and a ...
user avatar
6 votes
Accepted

Proof of an Ising model representation of graph isomorphism problem

The counterexamples you give are not correct. I suspect your bug is this: when doing the sums over edges in (or not in) $E_1$ and $E_2$, you need to consider both orderings of each pair. Consider ...
user avatar

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