Questions tagged [graph-isomorphism]

Two graphs G, H are isomorphic if there is a relabeling of the vertices of G that produces H, and vice-versa. The graph isomorphism problem (GI) is to decide whether two given are isomorphic. In addition to its practical interest, it was identified by Karp in 1972 as having unknown complexity, is one of the few remaining natural candidates for an NP-intermediate problem, and led to the creation of the complexity class AM.

Filter by
Sorted by
Tagged with
53
votes
1answer
2k views

Is there a gap amplification type of result for the Graph Isomorphism Problem?

Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
41
votes
3answers
3k views

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

The Graph Isomorphism problem (GI) is arguably the best known candidate for an NP-intermediate problem. The best known algorithm is sub-exponential algorithm with run-time $2^{O(\sqrt{n \log n})}$. ...
36
votes
3answers
2k views

Techniques for showing that problem is in hardness “limbo”

Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this ...
30
votes
1answer
742 views

Can graph isomorphism be decided with square root bounded nondeterminism?

Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
29
votes
3answers
3k views

coNP certificate for Graph Isomorphism

It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP ...
29
votes
2answers
826 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
24
votes
0answers
1k views

Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
23
votes
3answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
23
votes
4answers
3k views

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

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete ...
23
votes
1answer
3k views

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

It's been over a year since his January 2017 retraction and correction. Is there news? If not is this normal for validation to take this long? I would expect it would get plenty of attention. Has ...
21
votes
1answer
1k views

What is the current known hardness of Graph Isomorphism?

Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if ...
19
votes
2answers
443 views

“Tiny” Graph Isomorphism

While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind. Suppose that we have a polynomial time ...
18
votes
4answers
1k views

Open problems related to Graph isomorphism

Presently I am doing literature survey on Graph isomorphism (GI) problem. I would like to know some open questions related to the following What are the graph parameters for which fixed parameter ...
17
votes
2answers
589 views

Complexity of the coset intersection problem

Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold? As far as I know, the problem is known as the coset intersection problem. I am ...
17
votes
2answers
1k views

Graph Isomorphism Problem

I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai. These papers uses the high level knowledge of group theory ...
17
votes
2answers
2k views

Gentle introduction to graph isomorphism for bounded valance graphs

I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it ...
16
votes
1answer
468 views

Counterexample for Corneil's efficient algorithm for Graph Isomorphism

In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely: that ...
16
votes
2answers
2k views

Hard Instances for graph isomorphism testing

Is the case of strongly regular graphs the hardest one for GI testing? where "hardest" is used in some "common sense" meaning, or "in average", so to speak. Wolfram MathWorld mentions some "...
16
votes
2answers
327 views

similar matrices

Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
16
votes
2answers
862 views

Relationship between symmetry and computational intractability?

The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0. However, If $k(n)=O(\log n)$ ...
16
votes
1answer
398 views

Strongly Regular Graph and GI-Completeness

It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? (...
16
votes
1answer
1k views

NP-hardness of a graph partition problem?

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
16
votes
1answer
1k views

How to cite Babai's new graph isomorphism result?

Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time. In the beginning of 2017, Babai retracted the quasipolynomial claim due to ...
15
votes
1answer
734 views

Hardness of Computing Weisfeiler-Lehman labels

The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows : The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all ...
15
votes
2answers
672 views

GI-hard graph problem not known to be $NP$-complete

Graph Isomorphism ($GI$) is good candidate for $NP$-intermediate problem. $NP$-intermediate problems exist unless $P=NP$. I'm looking for natural problem that is hard for $GI$ under Karp reduction (A ...
15
votes
1answer
474 views

Imperfect subgraph isomorphism

Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges ...
14
votes
2answers
481 views

Approaches to GI inspired by knot problem

GI and Knot Problem both are problem of deciding structural equivalence of mathematical objects. Are there any results establishing connections between them? Nice connections of knot problem to ...
14
votes
1answer
357 views

Testing isomorphism of asymmetric graphs

While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) ...
14
votes
1answer
316 views

Generating Graphs with Trivial Automorphisms

I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism. It is "commonplace" (yet controversial!) to assume the existence of BPP ...
13
votes
2answers
720 views

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

I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial. Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for ...
13
votes
2answers
623 views

Complexity of permutation related problems

Given a group $G$ of permutations on $[n]=\{1, \cdots, n\}$, and two vectors $u,v\in \Gamma^n$ where $\Gamma$ is a finite alphabet which is not quite relevant here, the question is whether there ...
12
votes
3answers
569 views

$NP\cap coAM$ Languages

What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references? Update: I forgot to mention that I'm interested in languages not known to be in $...
12
votes
1answer
250 views

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

I want to be very specific. Does anyone know of a disproof or a proof of the following proposition: $\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$ $\forall G, H \in STRUC[\Sigma_{graph}] (...
12
votes
1answer
613 views

automorphism in Cai-Furer-Immerman gadgets

In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman. They construct a graph $X_k = (V_k, ...
12
votes
1answer
564 views

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

Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
12
votes
1answer
330 views

Negative results on identical particles approach to Graph Isomorphism (GI) problem

There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed ...
11
votes
3answers
658 views

History and status of the graph matching problem

Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from ...
11
votes
1answer
566 views

what are known bounds on complexity of nontrivial graph automorphism

Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?
11
votes
3answers
1k views

Regular Graphs and Isomorphism

I would like to ask whether there is an already published result on that: We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
11
votes
1answer
289 views

Is the finite inverse semigroup isomorphism problem GI-complete?

Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.
11
votes
1answer
618 views

On Graph Isomorphism Complete Problems

I am interested to study Graph Isomorphism (GI) complete problems. In the Paper " Problems Polynomially Equivalent to Graph Isomorphism" by Kellogg S. Booth, (1979), proved that many basic problems ...
11
votes
1answer
380 views

Redundancy and Structure of computational problems

It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). ...
10
votes
1answer
420 views

Is graph isomorphism in UP ${\cap}$ coUP?

Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).
10
votes
1answer
1k views

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

At http://www.dharwadker.org/tevet/isomorphism/, there is a presentation of an algorithm for determining if two graphs are isomorphic. Given a number of shall we say, "interesting" claims by A ...
10
votes
1answer
518 views

Is there a polynomial-time algorithm to solve graph isomorphism for Delaunay graphs of (finite) hexagonal tessellations?

Given a finite plane, I have a hexagonal tessellation of that plane with a fixed-size regular hexagon. I then compute the Delaunay graph G for the tessellation. Given such a graph G, I delete specific ...
10
votes
1answer
1k views

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

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
10
votes
1answer
243 views

Efficient graph isomorphism for similar graph queries

Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one ...
10
votes
2answers
301 views

When polynomial GI implies polynomial (edge) colored GI?

Crossposted from MO. (edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored). There are several reductions using transformations/gadgets of (edge) colored ...
9
votes
2answers
531 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
9
votes
2answers
615 views

Graph isomorphism with equivalence relation on the vertex set

A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there ...