# Questions tagged [isomorphism-testing]

Algorithmic questions concerning isomorphism testing. A prime example is the graph isomorphism problem, which is to decide if two input graphs are isomorphic. This tag may also be used for isomorphism testing between other objects (such as groups).

49
questions

**2**

votes

**1**answer

84 views

### Define a homomorphism of a set of graphs to its power set

Let $G$ be a simple graph and $S$ be the set of all sub graphs of $G$. Define two operations on $S$ as: $union$ of two graphs $ G_1$ and $G_2$ is,
$G_1\cup G_2$
$=\langle V(G_1)\cup V(G_2), (E(G_1)\...

**3**

votes

**0**answers

61 views

### Polynomial Graph Isomorphism from Star System Reconstruction?

Confusion is possible, but two papers and a simple graph
transformation imply Graph Isomorphism is polynomial, which
is an open problem.
The closed neighborhood of a vertex in a graph is sometimes ...

**1**

vote

**0**answers

111 views

### Is bounded graph isomorphism $NP$ complete?

Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$.
Is the bounded graph isomorphism problem
Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...

**2**

votes

**0**answers

267 views

### Algorithms for rooted directed acyclic graph isomorphism

Given two directed acyclic graphs $G_1$ and $G_2$, and their roots $r_1$ and $r_2$, is there a polynomial algorithm to determine if $G_1$ and $G_2$ are isomorphic?

**0**

votes

**1**answer

62 views

### Canonical form for a bipartite graph

I have a bipartite graph, including V1 and V2 vertices, and I would like to convert it to a canonical form. One simple method is converting this graph to a general graph by expanding its adjacency ...

**2**

votes

**0**answers

232 views

### Canonical labeling of graphs

Definition : Let $V$ be a linearly ordered set and $\Sigma$ an alphabet. A $\Sigma$- string on $V$ is a function $x : V \mapsto \Sigma$. The set of all $\Sigma$- strings on $V$ is defined by $\Sigma^{...

**0**

votes

**1**answer

93 views

### Doubt on size of the automorphism of regular graphs [closed]

Let $X= (V,E)$ be a input graph with vertex set $V$ and edge set $E$. Now we can define the AUT$(X)= \{\sigma | X^{\sigma} = X\}$. We know that if $X= K_n$ (complete graph with $n$ vertices) its AUT$...

**1**

vote

**1**answer

204 views

### Some doubts on the algorithm of graph isomorphism of bounded degree graph

There is an well known algorithm given by E.M Luks for bounded graph isomorphism. There are three important steps of the algorithm two of them are given below:
If the group action on vertex set of ...

**3**

votes

**1**answer

138 views

### How to find a good individualising set in graph isomorphism

The procedure called individualization breaks symmetry arbitrarily. It chooses some nodes in the graph, arbitrarily, to give their own unique names.
Suppose there exists a set $S \subset V$, such ...

**0**

votes

**1**answer

112 views

### Lower bound on the individualization set for $k$-iso-regular graphs ( degree at max three )?

Assume graphs of degree at most three for this question.
A graph is said to be k-isoregular if for every subset $S$ of at most $k$ vertices the number common neighbors of the elements of $S$ depends ...

**8**

votes

**3**answers

942 views

### Are regular graphs the hardest instance for graph isomorphism?

Regular graphs are the graphs in which the degree of each vertex is the same. The Weisfeiler-Lehman algorithm fails to distinguish between the given two non-isomorphic regular graphs.
Is there a ...

**1**

vote

**1**answer

398 views

### Elliptic Curve, characteristic equation of Frobenius endomorphism relation to isogeny

Let E be an elliptic curve over $F_p$. Suppose that its j invarient is not supersingular and that $j\neq 0 $ or 1728.
Then the modular polynomial $\Phi_l(j,T)$ has a zero $\tilde{\jmath} \in \...

**0**

votes

**1**answer

70 views

### Number of non-isomorphic block graphs on n nodes

A block in a graph is a maximal connected subgraph that has no cut-vertex. A complete graph having $n$ nodes is denoted by $K_n$. A block graph is a graph in which each block is a complete graph. For ...

**1**

vote

**1**answer

68 views

### Complexity of quadratic polynomials isomorphism

Two polynomials $f,g$ are isomorphic iff $f(x_1,\ldots x_n)=g(\pi(x_1, \ldots x_n))$ for a permutation $\pi$.
$f,g$ are equivalent if there exists invertible linear transormation
$A$ such that $f(X)=...

**4**

votes

**2**answers

297 views

### How to show the two convex bodies are affinely isomorphic?

This problem comes from the response of the author of papers.
Consider two convex bodies $A$ and $B$:
$$A= \{X\in \mathcal{S}^4 : \operatorname{tr}(X) = 1, X\succeq 0 \}$$
$$B = \operatorname{...

**7**

votes

**2**answers

407 views

### if two graphs have the same distinct eigenvalues, can we conclude that they are isomorphic?

i think i saw something like the statement of the question above but i am not sure.
Given two graph G and H if they have the same characteristic polynomial and it does not have any repeated roots,...

**1**

vote

**1**answer

120 views

### a space isomorphic to $S^{p+q}$

I've asked this question few days ago in MathStackExchange, but there was no result. So, I decided to ask it there.
In one of the paper I have met that
$$\mathbb{S}^{p+q} \cong \mathbb{S}^p \times \...

**1**

vote

**0**answers

105 views

### Isomorphism with fixed number of Permutations [closed]

Suppose, I have a fixed number of permutations for each sub-graph to determine isomorphism of whole graph. Is it possible to determine efficiently ?
For example, $G, H$ are isomorphic graphs. For ...

**9**

votes

**0**answers

221 views

### Is there an efficient algorithm for testing isomorphism of projective planes?

Isomorphism testing is a core problem in computational complexity. Recently, Babai has shown that Graph Isomorphism problem for general graphs can be solved in quasipolynomial time. Long time before ...

**10**

votes

**2**answers

270 views

### Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism
is NP-hard or harder?
Graphs and groups are not solutions.
Searching the web didn't return answer for me.
Partial result based on Chow's ...

**1**

vote

**1**answer

119 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**1**

vote

**2**answers

239 views

### Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (...

**2**

votes

**1**answer

190 views

### Graph Isomorphism for Triangle Free graph

Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs?
Anything close to the subject will help and of course, I have searched Google.

**12**

votes

**2**answers

254 views

### Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...

**3**

votes

**1**answer

107 views

### A possible GI isomorphic problem

Here I try to seek if restricting the structure of permutations would still keep GI property.
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,...

**6**

votes

**1**answer

238 views

### Deciding isomorphism between graphs which interpret in the pure set

I am interested in the following decision problem:
Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....

**5**

votes

**1**answer

139 views

### Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...

**6**

votes

**0**answers

103 views

### Contradicting claims about complexity of directed path graphs isomorphism

Thesis and a paper give conflicting claims about the
complexity of graph isomorphism for directed path graphs.
Since this means GI is polynomial likely I am missing something
or there is something ...

**2**

votes

**1**answer

528 views

### Why is graph automorphism sometimes easier than canonical labeling (for current software)?

László Babai recently hinted that graph isomorphism is solved for all practical purposes:
It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably ...

**13**

votes

**1**answer

1k views

### Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...

**0**

votes

**0**answers

85 views

### What is wrong with this isomorphism preserving transformation to a graph of bounded clique width and bounded rank width?

Got an isomorphism preserving transformation to a graph of bounded
clique width and rank width. It, a paper and graphclasses.org imply
graph isomorphism is in P, so likely something is wrong.
Let $G$ ...

**5**

votes

**3**answers

261 views

### Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs?
(2) Is there a repository of adjacencies from such classes?

**5**

votes

**2**answers

248 views

### Group acting on two different sets, can isomorphisms be computed efficiently?

For the permutation group isomorphism problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between ...

**4**

votes

**0**answers

286 views

### Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...

**3**

votes

**3**answers

508 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**1**

vote

**0**answers

226 views

### “Graph Individualization”[ reference request] [closed]

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below-
...

**8**

votes

**1**answer

380 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...

**2**

votes

**0**answers

412 views

### Partitioning graph for Graph Isomorphism [closed]

Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .
Construction:
$G$ is an $r$ regular graph, $k$ connected (not a ...

**1**

vote

**0**answers

160 views

### Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far).
What about Poly-trees (oriented trees)? These are DAG's ...

**8**

votes

**2**answers

209 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...

**1**

vote

**1**answer

196 views

### Linear algebra formulation for colored node graph isomorphism

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.)
Some basic definitions for completeness:
Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...

**1**

vote

**2**answers

1k views

### Are hyperreal numbers isomorphic to formal power series?

I wonder whether hyperreal numbers isomorphic with formal Laurent series?
It seems that any hyperreal number can be represented in the form of Laurent series over $\omega$. For instance,
$e^{\omega}=...

**0**

votes

**0**answers

93 views

### When is edge colored circulant isomorphism polynomial?

Don't understand enough group theory, but two papers
appear to give partial results about an open problem.
Edge colored graph isomorphism is isomorphism which
preserves the edge coloring (the ...

**4**

votes

**2**answers

574 views

### Automorphism group of directed complete graph

Given a directed complete graph on $n$ vertices, is there an efficient algorithm for computing its automorphism group? Is there a nontrivial upper bound on the order of its automorphism group? How ...

**15**

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

**5**

votes

**1**answer

568 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**2**

votes

**0**answers

109 views

### When polynomial GI implies polynomial (edge) colored GI?

(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 GI to GI. For edge ...

**3**

votes

**1**answer

217 views

### Graph transformation related to graph isomorphism

Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...

**4**

votes

**3**answers

378 views

### Isomorphism testing in STS(13)

What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points?
Train structure and cycle structure, as described here, do the ...