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

Filter by
Sorted by
Tagged with
0 votes
0 answers
53 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 ...
user avatar
  • 103
0 votes
1 answer
53 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) \...
user avatar
1 vote
0 answers
203 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 ...
user avatar
0 votes
0 answers
45 views

Definition of graph canonization and good textbook reference

I am struggling a bit with finding a good and generally accepted definition of graph canonization and canonical forms as well as a good textbook reference. From what I understand, a canonical form is ...
5 votes
2 answers
171 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 ...
user avatar
2 votes
0 answers
40 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)\...
user avatar
  • 161
3 votes
2 answers
293 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 ...
user avatar
  • 23.5k
5 votes
2 answers
332 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 $...
user avatar
  • 23.5k
1 vote
0 answers
41 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 ...
user avatar
1 vote
0 answers
124 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 ...
user avatar
  • 348
2 votes
0 answers
161 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. $$ ...
user avatar
1 vote
0 answers
106 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 ...
user avatar
  • 23.5k
2 votes
0 answers
97 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 ...
user avatar
  • 23.5k
4 votes
1 answer
755 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-...
user avatar
4 votes
0 answers
221 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 ...
user avatar
  • 23.5k
-3 votes
1 answer
131 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$...
user avatar
  • 23.5k
9 votes
2 answers
498 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 ...
user avatar
2 votes
0 answers
64 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 ...
user avatar
  • 23.5k
3 votes
1 answer
146 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, ...
user avatar
2 votes
1 answer
136 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)\...
user avatar
  • 203
3 votes
0 answers
64 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 ...
user avatar
  • 23.5k
1 vote
0 answers
117 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$ ...
user avatar
  • 13k
2 votes
0 answers
677 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?
user avatar
0 votes
1 answer
87 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 ...
user avatar
2 votes
0 answers
293 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^{...
user avatar
  • 303
0 votes
1 answer
145 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$...
user avatar
  • 303
1 vote
1 answer
216 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 ...
user avatar
  • 303
3 votes
1 answer
171 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 ...
user avatar
  • 303
0 votes
1 answer
131 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 ...
user avatar
  • 303
8 votes
3 answers
1k 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 ...
user avatar
  • 303
1 vote
1 answer
572 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 \...
user avatar
0 votes
1 answer
76 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 ...
user avatar
1 vote
1 answer
80 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)=...
user avatar
  • 23.5k
4 votes
2 answers
400 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{...
user avatar
8 votes
3 answers
740 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,...
user avatar
  • 585
1 vote
1 answer
124 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 \...
user avatar
  • 195
1 vote
0 answers
114 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 ...
user avatar
  • 257
9 votes
0 answers
231 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 ...
user avatar
11 votes
3 answers
431 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 ...
user avatar
  • 23.5k
1 vote
1 answer
122 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$.
user avatar
1 vote
2 answers
274 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 (...
user avatar
2 votes
1 answer
283 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.
user avatar
  • 257
12 votes
2 answers
267 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 ...
user avatar
3 votes
1 answer
119 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,...
user avatar
6 votes
1 answer
259 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....
user avatar
5 votes
1 answer
146 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$. ...
user avatar
  • 81
7 votes
0 answers
110 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 ...
user avatar
  • 23.5k
2 votes
1 answer
616 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 ...
user avatar
14 votes
1 answer
2k 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 ...
user avatar
0 votes
0 answers
92 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$ ...
user avatar
  • 23.5k