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

59 questions
Filter by
Sorted by
Tagged with
0answers
150 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.$$ ...
0answers
51 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 ...
0answers
83 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 ...
1answer
737 views

3answers
549 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,...
1answer
120 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 \...
0answers
108 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 ...
0answers
223 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 ...
3answers
410 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 ...
1answer
120 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$.
2answers
254 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 (...
1answer
238 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.
2answers
261 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 ...
1answer
114 views