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
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.$$ ...
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 ...
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 ...
737 views

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,...
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 \...
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 ...
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 ...
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 ...
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$.
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 (...
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.