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 ...

learn more… | top users | synonyms

7
votes
0answers
45 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). ...
5
votes
0answers
165 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 ...
5
votes
0answers
82 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.
2
votes
0answers
125 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)?
0
votes
1answer
127 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 ...
2
votes
1answer
407 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 ...
9
votes
2answers
164 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 ...
17
votes
2answers
301 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 ...
10
votes
3answers
316 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 ...
8
votes
2answers
148 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 ...
8
votes
1answer
295 views
2
votes
1answer
99 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 ...
2
votes
2answers
341 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 ...
3
votes
1answer
125 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 ...
1
vote
1answer
169 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 ...
18
votes
2answers
313 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 ...
2
votes
1answer
56 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 ...
9
votes
1answer
143 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 ...
2
votes
0answers
129 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, ...
13
votes
1answer
234 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$) ...
5
votes
2answers
188 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 ...
27
votes
1answer
405 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 ...
5
votes
1answer
132 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 ...
1
vote
0answers
90 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 ...
1
vote
0answers
61 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 ...
28
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 ...
6
votes
1answer
187 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.
17
votes
4answers
737 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 ...
14
votes
1answer
476 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 ...
6
votes
0answers
290 views

Quasi-polynomial time algorithm for graph isomorphism

GI arguably is the best known candidate for NP-intermediate problem. The best known algorithm is sub-exponential algorithm. However, I am not aware of any quasi-polynomial algorithm for it. GI is not ...
-1
votes
1answer
190 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 ...
6
votes
2answers
198 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 ...
1
vote
0answers
23 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 ...
2
votes
0answers
71 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 ...
2
votes
0answers
215 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 ...
5
votes
1answer
116 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 ...
10
votes
1answer
413 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 ...
16
votes
0answers
400 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 ...
15
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 ...
15
votes
1answer
314 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: ...
8
votes
1answer
304 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). ...
9
votes
3answers
464 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 ...
5
votes
1answer
165 views

Canonical labeling of special classes of DAGs

Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known. What are some special classes of DAGs that can be ...
4
votes
1answer
263 views

How hard is to compute $\Delta_{|V|}$?

Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds: $$ |\mathcal{C}| = 2^{|V|} - \sum_{k = ...
1
vote
0answers
91 views

Equivalence relations on strongly regular graphs with same parameters

Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter $(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set? My motivation is to approach ...
4
votes
2answers
233 views

Optimal upper bound on the number of non-isomorphic graphs with certain parameter

What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of non-isomorphic (unlabelled) simple (no self-loop), undirected ...
11
votes
1answer
351 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
248 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 ...
0
votes
1answer
166 views

Is there any special property the resulting graph G' has?

Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. That is, each block pair ...
13
votes
2answers
350 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 ...