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

75
questions

0
votes

0
answers

68
views

### What is the complexity of computing isomorphism of two non-regular graphs?

Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...

1
vote

1
answer

104
views

### Non-isomorphic walk-regular graphs with the same number of closed walks at any length

Are there known examples of couples of non-isomorphic walk-regular graphs with adjacency matrix $A_1$ and $A_2$ and such that $(A_1^k)_{i,i} = (A_2^k)_{i,i}$ for all $k \gt 0$?

2
votes

1
answer

111
views

### Determining graph Isomorphism: combining invariants

It appears that there are some related questions on this forum.
For example,
Invariants that might determine graph up to isomorphism
However, someone usually emphasizes a single invariant and its ...

1
vote

0
answers

111
views

### Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the ...

1
vote

0
answers

44
views

### Check if directed graph G1 is edge-induced subgraph isomorphic to directed graph G2

From the literature I've reviewed, I've seen the following options:
Node-induced subgraph isomorphism checking: Using VF2, ISMAGS, etc.
This approach however does not check for edge-induced subgraphs....

2
votes

0
answers

179
views

### Permutation similarity of matrices with many distinct entries

This is related to graph isomorphism.
Here matrices are square $n \times n$ with non-negative integer entries.
Two matrices $A,B$ are permutation similar if there exist
permutation matrix $P$ such ...

0
votes

0
answers

86
views

### Does it help for graph isomorphism to know power of the permutation matrix?

Here all matrices are square $n \times n$ with integer entries.
If you prefer, all entries are $0-1$.
Observation: the discrete logarithm for permutation matrices is
polynomial in $n$, since the ...

0
votes

0
answers

87
views

### Commutator magma isomorphism

Define the commutator magma of a group to be the magma whose elements are the same as the group’s and whose operation is the group’s commutator.
What are the conditions for two finite groups to have ...

0
votes

0
answers

65
views

### What will be the smallest value of $k$ such that $P(k)=m$?

Let us suppose that we have a group of order $p^k$, where $p$ is prime.In General,there is one group group of order $p^k$ for each set of positive integers whose sum is $k$(such a set is called ...

0
votes

1
answer

115
views

### Non-isomorphic graphs with identical iterated degree matrix

If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$
Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...

2
votes

1
answer

342
views

### What's the worst case for strongly regular graph's isomorphism algorithm?

A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer ...

8
votes

2
answers

373
views

### Selection of an n-vertex graph at random

Let's say I want to select, at random, an $n$-vertex graph $G=(V,E)$ from the set of all $n$-vertex graphs.
One way to do this would be to take the empty graph on $n$ vertices and then add each ...

2
votes

0
answers

51
views

### Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?

I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...

3
votes

2
answers

315
views

### Relation graph isomorphism to discrete logarithm

$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...

5
votes

2
answers

518
views

### Diffie Hellman cryptography based on graph isomorphism?

We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...

1
vote

0
answers

106
views

### Is there an effective genus theory for indefinite quadratic forms?

For positive definite quadratic forms, there is a way to check if two forms are isomorphic by arithmetic equivalence over $GL_n(Z)$ by computing configurations of vector up to some norm and then ...

1
vote

0
answers

157
views

### Given a graph, how to build another "difficult" isomorphic graph from it?

Suppose I want to test an algorithm for graph isomorphism check.
Starting from a given graph, I would do a random permutation of vertices to build the second graph.
Is there a way of making another ...

4
votes

0
answers

217
views

### Categorical setting for cancellation in direct sums

I am wondering whether some criterion can be put on a category $\mathcal{C}$ with direct sums to ensure that for three objects $X,Y,Z$ one has
$$
X\oplus Y \cong X \oplus Z\Longrightarrow Y\cong Z.
$$
...

1
vote

0
answers

173
views

### Reduction graph isomorphism to maximum independent set in very dense graph

We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...

2
votes

0
answers

117
views

### Complete graph invariant based on integer programming?

Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.
Let $G$ be graph, possibly directed graph, of ...

4
votes

1
answer

774
views

### Finding isomorphism between $\mathbb{Z}^2\ltimes_{A,B} \mathbb{Z}^4$ and $\mathbb{Z}^2\ltimes_{A,C} \mathbb{Z}^4$

Let $A,B(a,b,c,d)\in\mathsf{GL}(4,\mathbb{Z})$ be given by $$A=\begin{pmatrix} I_2 & \begin{pmatrix} 0&0\\0&1 \end{pmatrix} \\0& -I_2\end{pmatrix},\quad B(a,b,c,d)=\begin{pmatrix} -2a-...

4
votes

0
answers

241
views

### Can we make cryptography signature algorithm based on hardness of isomorphism?

In public key cryptography, Alice knows functions $f$ and its inverse
$f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message
$m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...

-3
votes

1
answer

140
views

### Doubt about lemma for polynomial equivalence [closed]

Multivariate polynomials $f,g$ are equivalent if there exists
invertible linear transformation $A$ such that $f(X)=g(A\cdot X)$
From paper p.1:
Lemma 1.1. (Structure of quadratic polynomials). Let $F$...

9
votes

2
answers

528
views

### A "subtle" isomorphism testing problem: $\mathbb{Z}\ltimes_{A} \mathbb{Z}^5\cong \mathbb{Z}\ltimes_{B}\mathbb{Z}^5$ or not?

EDIT: I've made a mistake with the matrices. Now it is corrected.
A couple of days ago I asked this question. There, answerers gave me excellent hints to solve that case and others too. But I've found ...

2
votes

0
answers

70
views

### Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy

The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean width.
In particular, boolean-width of the complement ...

3
votes

1
answer

238
views

### Weisfeiler-Lehman test for hypergraphs

The Weisfeiler-Lehman test for graph isomorphism is based on iterative graph recoloring and works for almost all graphs, in the probabilistic sense. If we extend the domain to general hypergraphs, ...

2
votes

1
answer

149
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

70
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

122
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

1
answer

1k
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

137
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

322
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

204
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

245
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

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

0
votes

1
answer

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

9
votes

3
answers

2k
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

739
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

80
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

82
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

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

9
votes

3
answers

1k
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

134
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

122
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

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

11
votes

3
answers

490
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

126
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

287
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

374
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

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