Questions tagged [graph-isomorphism]

Two graphs G, H are isomorphic if there is a relabeling of the vertices of G that produces H, and vice-versa. The graph isomorphism problem (GI) is to decide whether two given are isomorphic. In addition to its practical interest, it was identified by Karp in 1972 as having unknown complexity, is one of the few remaining natural candidates for an NP-intermediate problem, and led to the creation of the complexity class AM.

127 questions
Filter by
Sorted by
Tagged with
36 views

Constructing Orbits of the Automorphism of a Graph Group in Bliss

I'm using the Bliss package for graph isomorphism and canonization. The program is working great for the type of graphs I'm interested in. In one of the applications I need to compute the orbits of ...
123 views

Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
164 views

Complexity of graph isomorphism with properly colored edges (ref. request)

An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I ...
122 views

Complexity of unbalanced bipartite isomorphism

For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and $|B_1|=|B_2|=b$ with $a\le b$. Question. Is the problem of ...
101 views

Is the isomorphism problem between posets represented by DAGs GI-complete?

Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete? I believe this problem is equivalent to ...
241 views

Efficient graph isomorphism for similar graph queries

Given the graph G1, G2 and G3, we want to perform isomorphism test F between G1 and G2 as well as G1 and G3. If G2 and G3 are very similar such that G3 is formed by deleting one node and inserting one ...
56 views

Graph automorphism with prescribed values

Consider a graph $G$ with vertices labeled $1,...,n$ and edge weights $w_{ij}$. Recall an automorphism of G is a permutation $\sigma$ of the vertex labels such that $w_{\sigma(i),\sigma(j)}=w_{ij}$ ...
149 views

Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
52 views

234 views

168 views

Tight upper bound on the number of iterations of Weisfeiler–Lehman Procedure (Graph isomorphism)

Graph Isomorphism is a very well known problem in computer science. A generic procedure for the graph isomorphism problem builds on a simple color refinement procedure given below (One dimensional ...
1k views

How to cite Babai's new graph isomorphism result?

Recently, Babai has published a paper on STOC 2016 claiming that graph isomorphism can be solved in quasipolynomial time. In the beginning of 2017, Babai retracted the quasipolynomial claim due to ...
165 views

Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
220 views

questions on implications Babais quasi P time graph isomorphism result

Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs. based on the proof, does this mean now that if Johnson ...
141 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete?...
825 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
191 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
150 views

Maximum common subgraph of two planar graphs of bounded degree k

Given two planar graphs of bounded degree (i.e. each node has no more than D edges), I'd like to find their maximum common subgraph. I know that the more general problem applied to maximal planar ...
217 views

Testing Isomorphism of projective planes

Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
311 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
359 views

616 views

Canonical way of coloring graphs (individualization) for isomorphism purpose

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism ...
259 views

Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial [closed]

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open. 2015 arxiv paper claims it is polynomial: Isomorphism Testing for Graphs of Bounded Rank Width ...
129 views

On low rank graph isomorphism

Is there a $c>1$ (maybe $c=2$) such that every lower than rank $n^{1/c}$ graphs on $n$ vertices can be tested to be in polynomial time?
199 views

Connections between Graph Isomorphism and Polynomial Equivalence

Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem? In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards ...
287 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
148 views

Complexity class for some group and graph homomorphism problems

Given two groups $G_1$ and $G_2$ what is the complexity class in which the following problem belongs? $$\mathsf{Is }|Hom(G_1,G_2)|>0$$ Given two graphs $H_1$ and $H_2$ what is the complexity ...
135 views

457 views

Quasi-polynomial time algorithm for permutation group isomorphism

Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism. My hope for such an ...
185 views

Graph isomorphism problem with invertible adjacency matrices

This question is supplementary to the question asked here. One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows. Given a ...
1k views

Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

At http://www.dharwadker.org/tevet/isomorphism/, there is a presentation of an algorithm for determining if two graphs are isomorphic. Given a number of shall we say, "interesting" claims by A ...
3k views

What evidence is there that Graph Isomorphism is not in $P$?

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete ...
525 views

Number of Automorphisms of a graph for graph isomorphism

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$. What is the ...
154 views

Construction of a graph which has regular subgraphs at each iteration of a recursive process

I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below Description : $G$ is a $r$ regular ...
Coset state of $3$-node graph isomorphism problem
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...