Skip to main content
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+...
domotorp's user avatar
  • 14.1k
27 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 ...
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 ...
Joshua Grochow's 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 ...
Yuval Filmus's user avatar
  • 14.5k
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_{...
Daniil Musatov's 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. ...
Bjørn Kjos-Hanssen's user avatar
8 votes
Accepted

Is the isomorphism problem between posets represented by DAGs GI-complete?

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite ...
Laakeri's user avatar
  • 1,831
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 ...
daniello's user avatar
  • 3,276
7 votes
Accepted

Can you find a counter-example for this proposed Graph Isomorphism algorithm?

Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen & Schweitzer (STOC '18, arXiv) gave examples with an ...
Joshua Grochow's user avatar
6 votes
Accepted

Efficient graph isomorphism for similar graph queries

This is a simple polynomial time reduction to show that the problem is GI complete: even if you know that $G_1, G_2$ are isomorphic, checking if $G_3$, built from $G_2$ deleting and adding a node, is ...
Marzio De Biasi's user avatar
6 votes

Isomorphism Problems with Unknown Single-Exponential Algorithms

A. Permutational isomorphism (aka conjugacy) of permutation groups. Input: Two lists of permutations $\pi_1, \dotsc, \pi_k, \rho_1, \dotsc, \rho_l$ Decide: Is there a permutation $\gamma$ such that $\...
Joshua Grochow's user avatar
6 votes

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

As far as I can tell, if you ask simply about the consequences of the mere fact (as a black box) that GI is in QP, I think the answer is very little. The one thing I can think of, which is not a ...
Joshua Grochow's user avatar
6 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks. You even get a mild form of peer review for your posts, ...
Bjørn Kjos-Hanssen's user avatar
6 votes

Maximum common subgraph of two planar graphs of bounded degree k

Maybe I misunderstood the question, but it seems it's NPC and this is trivial. Finding hamiltonian cycle in planar graphs of max degree $3$ is NPC. Therefore this problem is also NPC (input: A planar ...
Saeed's user avatar
  • 3,440
6 votes

How to cite Babai's new graph isomorphism result?

First off, I would discourage submitting for publication an unconditional paper which depends on the quasi-polynomial result, if that's what you want the citation for. Rephrase the result as ...
Stella Biderman's user avatar
5 votes
Accepted

A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know ...
Joshua Grochow's user avatar
5 votes

Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

I think this is open. Note that if instead of testing equivalence under rotations you ask for equivalence under the general linear group, then already testing equivalence of degree three polynomials ...
Joshua Grochow's user avatar
5 votes

Complexity of graph isomorphism with properly colored edges (ref. request)

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. ...
user55611's user avatar
4 votes
Accepted

On lattice and code isomorphism

The reduction from graph isomorphism to linear code isomorphism (Petrank and Roth '97) has the property that the vectors used in the reduction are precisely the lowest-weight vectors, having weight 5, ...
Joshua Grochow's user avatar
4 votes
Accepted

Is parity of GI easy?

This is open and at least as hard as the Graph Automorphism problem. If G,H have no nontrivial automorphisms (aka rigid), then N(G,H)=0 or 1, so even N(G,H) mod 2 solves the promise problem RigidGI. ...
Joshua Grochow's user avatar
3 votes
Accepted

Complexity of unbalanced bipartite isomorphism

If you are willing to relax the 2 to some other constant, then yes: this can be solved in $O(c^a)$ time for some absolute constant $c$. You can view this problem as isomorphism of hypergraphs, where ...
Joshua Grochow's user avatar
3 votes

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

Babai invented the fastest known algorithm which runs in quasipolynomial time $2^{(\log n)^{O(1)}}$.
Mohammad Al-Turkistany's user avatar
3 votes

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

Concerning the last question: the time hierarchy theorem immediately implies that QP has no complete problems under polynomial-time many-one or Turing reductions. (On the other hand, every problem ...
Emil Jeřábek's user avatar
3 votes

FPT algorithm for Partial k-tree Isomorphism

In the meantime, it was shown that Graph Isomorphism is FPT with respect to the treewidth of the graphs. Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh: Fixed-Parameter ...
Christian Komusiewicz's user avatar
3 votes

Gentle introduction to graph isomorphism for bounded valance graphs

Notation: Let $X = (V,E)$ be graph, $e = (v_1, v_2) $ an edge of $X$. The vertex set $V_k$ be the set of vertices of distance $k$ from $e$, and let $h$ be the height of $X$. According to definition of ...
Michael's user avatar
  • 553
3 votes

One Generalization of Graph Isomorphism Problem

I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable. Proof: It suffices ...
Bjørn Kjos-Hanssen's user avatar
3 votes

On lattice and code isomorphism

It's important to be precise about what it means to be a "minimum basis," which as Josh points out is not a priori well-defined. However, for lattice isomorphism the answer is basically that ...
Huck Bennett's user avatar
  • 5,013
2 votes
Accepted

One Generalization of Graph Isomorphism Problem

This is the decision version of what is sometimes called "Approximate Graph Isomorphism." While I won't say it's been studied a lot, it has been studied. See, for example: [AKKV] Arvind, Kobler, ...
Joshua Grochow's user avatar
2 votes
Accepted

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a ...
Joshua Grochow's user avatar
2 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

The ScienceOpen website has a page for most arXiv articles (e.g., here), and it has an option where you can post your own review of any preprint. I do not know if they are recommendable or not (but ...
a3nm's user avatar
  • 9,677

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