Skip to main content

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
4 votes
1 answer
152 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\...
user avatar
1 vote
0 answers
59 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 ...
Omar Shehab's user avatar
1 vote
1 answer
263 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 $\...
gdiazc's user avatar
  • 419
8 votes
1 answer
538 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 ...
Thomas Klimpel's user avatar
0 votes
1 answer
229 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 ...
Omar Shehab's user avatar
13 votes
1 answer
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 ...
Bill Province's user avatar
28 votes
4 answers
6k 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 ...
Mohammad Al-Turkistany's user avatar
9 votes
2 answers
798 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 ...
Michael's user avatar
  • 553
2 votes
0 answers
157 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 ...
Michael's user avatar
  • 553
0 votes
2 answers
623 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 ...
Omar Shehab's user avatar
1 vote
0 answers
37 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 ...
Omar Shehab's user avatar
5 votes
1 answer
148 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 ...
domotorp's user avatar
  • 14k
7 votes
0 answers
596 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). ...
user32149's user avatar
  • 313
11 votes
1 answer
2k 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 ...
Mohammad Al-Turkistany's user avatar
11 votes
1 answer
315 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.
Thomas Klimpel's user avatar
1 vote
0 answers
314 views

Known algorithms for Graph isomorphism [closed]

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?
shuhalo's user avatar
  • 1,159
1 vote
1 answer
368 views

checking isomorphism between K regular graph

Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that ...
v78's user avatar
  • 119
9 votes
1 answer
3k views

Is DAG isomorphism NP-C

Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in D(...
Peng Zhang's user avatar
  • 1,453
10 votes
2 answers
326 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 ...
joro's user avatar
  • 1,955
17 votes
2 answers
697 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 ...
maomao's user avatar
  • 1,345
14 votes
2 answers
1k 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 ...
user27313's user avatar
  • 143
9 votes
2 answers
795 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 ...
John D.'s user avatar
  • 568
10 votes
2 answers
914 views

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

What is the fastest known undirected graph isomorphism algorithm?
bbejot's user avatar
  • 1,099
3 votes
1 answer
281 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
Omar Shehab's user avatar
2 votes
2 answers
545 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \...
Mohammad Al-Turkistany's user avatar
3 votes
1 answer
229 views

When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory. As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI. A ...
joro's user avatar
  • 1,955
1 vote
1 answer
356 views

Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

This paper gives example of polynomial GI for certain graphs. Probably I am misunderstanding the paper, but appears to me it implies polynomial GI for cubic, $4$-regular and probably higher degree ...
joro's user avatar
  • 1,955
19 votes
2 answers
473 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 ...
Marzio De Biasi's user avatar
2 votes
1 answer
89 views

Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

There are two ways to extend infinitary logic with counting: Grädel's way (cf. p. 11): We extend $L_{\infty\omega}$ by introducing a counting existential quantifier: $$ \mathcal{A} \models \exists^{...
Joachim's user avatar
  • 513
9 votes
1 answer
255 views

Complexity of counting graph endomorphisms

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An ...
a3nm's user avatar
  • 9,527
4 votes
0 answers
171 views

Fixed parameter tractable algorithms for graph isomorphism

What are the future directions in fixed parameter tractability of graphs isomorphism after these two recent papers: Reduction Techniques for Graph Isomorphism in the Context of Width Parameters, ...
Kumar's user avatar
  • 2,044
14 votes
1 answer
460 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$) ...
Marzio De Biasi's user avatar
5 votes
2 answers
596 views

graph isomorphism given a partial isomorphism

Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ? In particular, it would be interesting to have conditions on this partial isomorphism that makes ...
Denis's user avatar
  • 8,903
31 votes
1 answer
828 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 ...
András Salamon's user avatar
5 votes
1 answer
565 views

Probability of random (in)finite graphs being isomorphic

I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite ...
John D.'s user avatar
  • 568
1 vote
0 answers
130 views

Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
Vivek Bagaria's user avatar
1 vote
0 answers
81 views

Definition of Clique vertex and separator vertex

While converting a tree decomposition of graph to Normalized tree decomposition, the definitions of clique vertex and separator vertex are used in Sequential and parallel algorithms for embedding ...
Kumar's user avatar
  • 2,044
39 votes
4 answers
3k 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 ...
Suresh Venkat's user avatar
6 votes
1 answer
336 views

How hard is the Circuit Isomorphism problem?

Given two circuits, how hard is it to tell if they represent the same function? Clearly, this must be at least as easy as Graph Isomorphism since you can represent any circuit as a graph.
Eric Bahr's user avatar
  • 115
18 votes
4 answers
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 ...
Kumar's user avatar
  • 2,044
15 votes
2 answers
820 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 ...
Mohammad Al-Turkistany's user avatar
43 votes
3 answers
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})}$. ...
Mohammad Al-Turkistany's user avatar
-1 votes
1 answer
300 views

Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs? [closed]

Let the Graph Isomorphism Problem be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations. Let the Graph Isomorphism ...
Nils Wisiol's user avatar
7 votes
3 answers
336 views

FPT algorithm for Partial k-tree Isomorphism

H.L. Bodlander in Polynomial algorithms for graph isomorphism and chromatic index on partial $k$-trees given a polynomial time algorithm for graph isomorphism when $k$ is constant. Is there any FPT ...
Kumar's user avatar
  • 2,044
1 vote
0 answers
61 views

Number of non-isomorphic codes

We have number of non-isomorphic graphs given in http://planetmath.org/enumeratinggraphs Over an alphabet $q$ how many non-isomorphic $[n,k,d]_q$ codes are possible particularly in the special case ...
Turbo's user avatar
  • 13k
2 votes
0 answers
189 views

Fractional chromatic number of Johnson graphs

Johnson graphs have a dual like construction to Kneser graphs in the sense that in Kneser we encode non-intersecting k-sets by joining vertices that represent the sets while in Johnson graphs we ...
Turbo's user avatar
  • 13k
2 votes
0 answers
359 views

On the subgraph isomorphism problem

The subgraph isomorphism problem problem is to determine given $G$ and $H$ whether $G$ is a subgraph of $H$. Let $G$ and $H$ be regular graphs with degree of $H$ greater than degree of $G$. Does the ...
Turbo's user avatar
  • 13k
5 votes
1 answer
190 views

Cayley subgraph isomorphism and complexity of linear subcode decision

Let $G$ be an undirected Cayley graph over an abelian group. Let $H$ a regular graph whose independence number and chromatic number are known. Let $inj(G,H)$ be the number of injective homomorphisms ...
Turbo's user avatar
  • 13k
11 votes
1 answer
730 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 ...
Kumar's user avatar
  • 2,044
27 votes
0 answers
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 ...
Gil Kalai's user avatar
  • 6,063