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

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
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$ ...
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?
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 ...
309 views

1 vote
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 ...
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 ...
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 ...
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
667 views

449 views

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