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
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$?
- 906
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,801
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 ...
- 25.2k
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....
- 111
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 ...
- 25.2k
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 ...
- 25.2k
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 ...
- 2,763
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 ...
- 113
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) \...
- 47.9k
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 ...
- 165
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 ...
- 151
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)\...
- 161
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 ...
- 25.2k
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 $...
- 25.2k
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 ...
- 906
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.
$$
...
- 5,660
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 ...
- 25.2k
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 ...
- 25.2k
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 ...
- 25.2k
-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$...
- 25.2k
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 ...
- 25.2k
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, ...
- 133
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)\...
- 203
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 ...
- 25.2k
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$ ...
- 13.8k
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?
- 21
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 ...
- 103
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^{...
- 313
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$...
- 313
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 ...
- 313
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 ...
- 313
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 ...
- 313
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 ...
- 313
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 \...
- 19
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 ...
- 630
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)=...
- 25.2k
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{...
- 345
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,...
user95470
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 \...
- 195
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 ...
- 267
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 ...
- 2,993
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 ...
- 25.2k
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$.
user76479
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 (...
- 333
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.
- 267
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 ...
- 333