Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
109 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$ ...
0
votes
0answers
41 views

Does similar automorphism group imply similar extension complexity?

Definition: Extension complexity of a polytope $P$ in $\mathbb R^n$ is the minimal number of facets a polytope in $\mathbb R^{n'}$ with $n'\geq n$ needs such that its projection is $P$. Do there ...
0
votes
0answers
58 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?
0
votes
1answer
55 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 ...
2
votes
0answers
162 views

Canonical labeling of graphs

Definition : Let $V$ be a linearly ordered set and $\Sigma$ an alphabet. A $\Sigma$- string on $V$ is a function $x : V \mapsto \Sigma$. The set of all $\Sigma$- strings on $V$ is defined by $\Sigma^{...
0
votes
1answer
78 views

Doubt on size of the automorphism of regular graphs [closed]

Let $X= (V,E)$ be a input graph with vertex set $V$ and edge set $E$. Now we can define the AUT$(X)= \{\sigma | X^{\sigma} = X\}$. We know that if $X= K_n$ (complete graph with $n$ vertices) its AUT$...
1
vote
1answer
191 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 ...
3
votes
1answer
127 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 ...
0
votes
1answer
102 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 ...
7
votes
3answers
788 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
1answer
269 views

Elliptic Curve, characteristic equation of Frobenius endomorphism relation to isogeny

Let E be an elliptic curve over $F_p$. Suppose that its j invarient is not supersingular and that $j\neq 0 $ or 1728. Then the modular polynomial $\Phi_l(j,T)$ has a zero $\tilde{\jmath} \in \...
0
votes
1answer
69 views

Number of non-isomorphic block graphs on n nodes

A block in a graph is a maximal connected subgraph that has no cut-vertex. A complete graph having $n$ nodes is denoted by $K_n$. A block graph is a graph in which each block is a complete graph. For ...
1
vote
1answer
68 views

Complexity of quadratic polynomials isomorphism

Two polynomials $f,g$ are isomorphic iff $f(x_1,\ldots x_n)=g(\pi(x_1, \ldots x_n))$ for a permutation $\pi$. $f,g$ are equivalent if there exists invertible linear transormation $A$ such that $f(X)=...
4
votes
2answers
250 views

How to show the two convex bodies are affinely isomorphic?

This problem comes from the response of the author of papers. Consider two convex bodies $A$ and $B$: $$A= \{X\in \mathcal{S}^4 : \operatorname{tr}(X) = 1, X\succeq 0 \}$$ $$B = \operatorname{...
7
votes
2answers
369 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,...
1
vote
1answer
115 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 \...
1
vote
0answers
96 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 ...
9
votes
0answers
217 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 ...
10
votes
2answers
262 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
1answer
119 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
2answers
228 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 (...
2
votes
1answer
164 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.
12
votes
2answers
251 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 ...
3
votes
1answer
104 views

A possible GI isomorphic problem

Here I try to seek if restricting the structure of permutations would still keep GI property. Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,...
6
votes
1answer
231 views

Deciding isomorphism between graphs which interpret in the pure set

I am interested in the following decision problem: Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....
5
votes
1answer
135 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
6
votes
0answers
100 views

Contradicting claims about complexity of directed path graphs isomorphism

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs. Since this means GI is polynomial likely I am missing something or there is something ...
2
votes
1answer
476 views

Why is graph automorphism sometimes easier than canonical labeling (for current software)?

László Babai recently hinted that graph isomorphism is solved for all practical purposes: It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably ...
12
votes
1answer
1k views

Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned: 'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
0
votes
0answers
78 views

What is wrong with this isomorphism preserving transformation to a graph of bounded clique width and bounded rank width?

Got an isomorphism preserving transformation to a graph of bounded clique width and rank width. It, a paper and graphclasses.org imply graph isomorphism is in P, so likely something is wrong. Let $G$ ...
5
votes
3answers
231 views

Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs? (2) Is there a repository of adjacencies from such classes?
5
votes
2answers
243 views

Group acting on two different sets, can isomorphisms be computed efficiently?

For the permutation group isomorphism problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between ...
4
votes
0answers
272 views

Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
3
votes
3answers
429 views

Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...
1
vote
0answers
221 views

“Graph Individualization”[ reference request] [closed]

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below- ...
8
votes
1answer
363 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
2
votes
0answers
389 views

Partitioning graph for Graph Isomorphism [closed]

Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases . Construction: $G$ is an $r$ regular graph, $k$ connected (not a ...
1
vote
0answers
147 views

Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
8
votes
2answers
191 views

Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic. Now it feels to me that this class of graphs is "too ...
1
vote
1answer
175 views

Linear algebra formulation for colored node graph isomorphism

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.) Some basic definitions for completeness: Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...
1
vote
2answers
1k views

Are hyperreal numbers isomorphic to formal power series?

I wonder whether hyperreal numbers isomorphic with formal Laurent series? It seems that any hyperreal number can be represented in the form of Laurent series over $\omega$. For instance, $e^{\omega}=...
0
votes
0answers
90 views

When is edge colored circulant isomorphism polynomial?

Don't understand enough group theory, but two papers appear to give partial results about an open problem. Edge colored graph isomorphism is isomorphism which preserves the edge coloring (the ...
4
votes
2answers
480 views

Automorphism group of directed complete graph

Given a directed complete graph on $n$ vertices, is there an efficient algorithm for computing its automorphism group? Is there a nontrivial upper bound on the order of its automorphism group? How ...
15
votes
1answer
2k views

Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
5
votes
1answer
558 views

Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$ with the same number of vertices, edges, are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...
2
votes
0answers
105 views

When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored). There are several reductions using transformations/gadgets of (edge) colored GI to GI. For edge ...
3
votes
1answer
203 views

Graph transformation related to graph isomorphism

Basically got graph transformation related to graph isomorphism. Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$. ...
4
votes
3answers
357 views

Isomorphism testing in STS(13)

What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points? Train structure and cycle structure, as described here, do the ...