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
-2
votes
0answers
61 views

Comparisons between Graph isomorphism algorithms

I have heard quite a few algorithms for isomorphism tests. Can anyone tell me which one is the best and their difference? More specifically, what is the relationship between Weisfeiler-Lehman and VF2 ...
10
votes
1answer
205 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 ...
1
vote
0answers
56 views

Graph automorphism with prescribed values

Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ ...
6
votes
1answer
135 views

Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
1
vote
0answers
50 views

Is there an efficient way to reduce a set of graphs under isomorphism?

Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $...
3
votes
0answers
55 views

Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)

Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
3
votes
1answer
114 views

Isomorphism Problems with Unknown Single-Exponential Algorithms

Isomorphism problems come in several variants: Group isomorphism can be solved in time $n^{O(\log n)}$ Graph isomorphism can be solved in time $n^{\log^{O(1)} n}$ Isomorphism of linear codes can be ...
22
votes
1answer
2k 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 ...
12
votes
1answer
463 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$...
2
votes
0answers
112 views

Practical polynomial-time implementation of bounded degree graph isomorphishm

There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not ...
13
votes
2answers
560 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 ...
-3
votes
1answer
143 views

On a GI complete class

https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_classes_of_graphs says deciding diameter $2$ radius $1$ graph isomorphism is $GI$ complete. Is it possible only the diameter $2$ ...
12
votes
1answer
230 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}] (...
2
votes
2answers
225 views

One Generalization of Graph Isomorphism Problem

Say I generalize the language which consists of pairs of isomorphic graphs to take the following form: $GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \...
4
votes
1answer
282 views

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

I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent ...
5
votes
0answers
162 views

Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
1
vote
0answers
77 views

Easy instances for coset intersection problem

Coset Intersection Problem Given : $K,H \le S_n$, and $\sigma \in S_n$ Find : $K \cap H\sigma$ Known results are : $n^{O(\sqrt n )}$ time algorithm by L.Babai. $n^{O(1)} m^{O(\sqrt m )}$, where $...
4
votes
0answers
159 views

Tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure (Graph isomorphism)

Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional ...
16
votes
1answer
921 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 ...
2
votes
1answer
148 views

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

The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
-2
votes
1answer
207 views

questions on implications Babais quasi P time graph isomorphism result

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs. based on the proof, does this mean now that if Johnson ...
4
votes
0answers
138 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete?...
24
votes
1answer
674 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 ...
4
votes
0answers
174 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
4
votes
1answer
145 views

Maximum common subgraph of two planar graphs of bounded degree k

Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar ...
6
votes
0answers
213 views

Testing Isomorphism of projective planes

Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
7
votes
1answer
292 views

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

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
5
votes
2answers
317 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
7
votes
1answer
216 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
4
votes
1answer
522 views

Canonical way of coloring graphs (individualization) for isomorphism purpose

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism ...
-3
votes
1answer
249 views

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

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open. 2015 arxiv paper claims it is polynomial: Isomorphism Testing for Graphs of Bounded Rank Width ...
4
votes
1answer
129 views

On low rank graph isomorphism

Is there a $c>1$ (maybe $c=2$) such that every lower than rank $n^{1/c}$ graphs on $n$ vertices can be tested to be in polynomial time?
4
votes
1answer
192 views

Connections between Graph Isomorphism and Polynomial Equivalence

Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem? In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards ...
-3
votes
1answer
276 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
3
votes
1answer
142 views

Complexity class for some group and graph homomorphism problems

Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs? $$\mathsf{Is }|Hom(G_1,G_2)|>0$$ Given two graphs $H_1$ and $H_2$ what is the complexity ...
3
votes
1answer
126 views

Some nuances on Group and Subgroup Isomorphism?

(1) Is it known Group Isomorphism is in $\mathsf{coNP}$ and is the conjecture so? Is there a good reference for $\mathsf{coNP}$-ness in similar situations? (2) Is subgroup isomorphism $\mathsf{NP\...
1
vote
0answers
52 views

First register in the hidden subgroup representations of Simon's and graph isomorphism problems

The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
0
votes
1answer
190 views

Complete problems or alternative definitions of the complexity class NP^GI?

Definition: Let $GraphIso$ be the decision problem whose input is a pair of undirected graphs $(G_1, G_2)$ and the output is true if and only if $G_1$ and $G_2$ are isomorphic. Definition: Define $\...
7
votes
1answer
435 views

Quasi-polynomial time algorithm for permutation group isomorphism

Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism. My hope for such an ...
0
votes
1answer
171 views

Graph isomorphism problem with invertible adjacency matrices

This question is supplementary to the question asked here. One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows. Given a ...
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 ...
22
votes
4answers
2k 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 ...
9
votes
2answers
481 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 ...
2
votes
0answers
153 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
0
votes
2answers
402 views

Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
1
vote
0answers
34 views

Coset state of $3$-node graph isomorphism problem

The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
5
votes
1answer
138 views

When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
7
votes
0answers
332 views

Number of non-isomorphic induced subgraphs of a graph

Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs). ...
10
votes
1answer
832 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 ...
11
votes
1answer
246 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.