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

73
questions

2
votes

1
answer

89
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

87
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

21
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

60
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

79
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

76
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

92
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) \...

1
vote

0
answers

224
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

277
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

46
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

309
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

443
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

72
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

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

3
votes

0
answers

179
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

146
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

103
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

767
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

235
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

138
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

511
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

203
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

147
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

68
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

120
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

855
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

120
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

309
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

172
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

227
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

183
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

159
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

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

667
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

78
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

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

8
votes

3
answers

929
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

132
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

116
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

239
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

463
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

280
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

326
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

279
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

122
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

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