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

68 questions
Filter by
Sorted by
Tagged with
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 ...
53 views

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 ...
1 vote
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$ ...
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?
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 ...
293 views

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

400 views

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