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+...
- 13.9k
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 ...
- 36.9k
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 ...
- 14.3k
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=...
- 11.3k
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 ...
- 36.9k
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_{...
- 546
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 ...
- 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 ...
- 20.8k
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.
...
- 4,475
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 ...
- 1,767
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 ...
- 3,256
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$ ...
- 36.9k
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 ...
- 36.9k
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 ...
- 36.9k
6
votes
Accepted
Graph isomorphism problem with invertible adjacency matrices
Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).
- 1,907
6
votes
Accepted
Some nuances on Group and Subgroup Isomorphism?
(1) In terms of structural complexity classes (as opposed to just upper bounds on deterministic time), for general Group Isomorphism, the known upper bounds are essentially the same as for Graph ...
- 36.9k
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, ...
- 4,475
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 ...
- 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 ...
- 1,046
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 $\...
- 36.9k
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 ...
- 22.6k
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 ...
- 36.9k
5
votes
Accepted
Complexity of a graph-rewriting problem
I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.
We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL)...
- 22.6k
5
votes
Complete problems or alternative definitions of the complexity class NP^GI?
[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.]
$\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time Turing reductions, which ...
5
votes
Local Graph Isomorphism to construct Global Graph Isomorphism
This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms ...
- 36.9k
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 ...
- 36.9k
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. ...
- 51
4
votes
Local Graph Isomorphism to construct Global Graph Isomorphism
NAUTY "colors" nodes with constant depth neighborhood canonical forms. Babai's new algo does likewise with log size neighborhoods.
The kicker is that in a random graph the diameter is about log n, so ...
- 2,359
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, ...
- 36.9k
Only top scored, non community-wiki answers of a minimum length are eligible