# 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
Filter by
Sorted by
Tagged with
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
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$?
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
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
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....
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
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
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
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
115 views

• 203
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
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
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?
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
322 views

• 313
1 vote
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
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
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
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
739 views

• 25.2k
491 views

• 195
1 vote
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
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 ...
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
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
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 (...