Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
121 views

Is the protocol perfect zero knowledge?

Consider such protocol for $GI$ (Graph-isomorphism problem). $P$ randomly chooses permutations $\sigma_1, \sigma_2, ..., \sigma_k$ and sends $H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$;...
GeoArt's user avatar
  • 9
1 vote
1 answer
178 views

Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: “A Canonical String Encoding for Pure Bigraphs.” On page 2, they define the notion of a bigraph, which is roughly a forest and ...
Oscar Bender-Stone's user avatar
3 votes
0 answers
69 views

Property testing algorithm for isomorphism to a balanced 3-sided complete graph

I am looking for testing algorithm in the dense graph model, that checks for a graph with $3n$ vertices whether it's isomorphic to a balanced 3-sided complete graph with $n$ vertices in each set. The ...
Z.L's user avatar
  • 31
6 votes
0 answers
235 views

Two graphs indistinguishable by 4-WL

There are pairs of non-isomorphic graphs that are indistinguishable by the k-WL (but distinguishable by (k+1)-WL) [1]. For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the ...
DeepOak's user avatar
  • 61
0 votes
1 answer
139 views

2xn grid graphs from ring graphs via local complementations

(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
Dotman's user avatar
  • 109
1 vote
2 answers
138 views

On lattice and code isomorphism

We know deciding isomorphism between lattices or codes is difficult if the presentation is through arbitrary bases. What if the presentation of the lattice is through minimum bases? Likewise the ...
Turbo's user avatar
  • 13k
1 vote
0 answers
116 views

Efficient enumeration of connected functional digraphs (up to isomorphism)

Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
Antonio E. Porreca's user avatar
1 vote
0 answers
68 views

Are there classes where all Eulerian orientations can be listed in polynomial time?

Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations? An Eulerian orientaiton of an (undirected simple) graph ...
Cyriac Antony's user avatar
8 votes
1 answer
497 views

Can you find a counter-example for this proposed Graph Isomorphism algorithm?

As D. Eppstein pointed out here regarding proposed poly-time algorithms for Graph Isomorphism: ... it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle ...
Neal Young's user avatar
  • 10.8k
7 votes
1 answer
349 views

Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism. By ordered I mean that each vertex has a list of ...
Manuel Eberl's user avatar
0 votes
0 answers
146 views

Comparing two graphs when starting from a single edge

Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes. $G_1$ ...
Freiburger0's user avatar
4 votes
1 answer
311 views

Isomorphism preserving transformation CNF to Graph?

In short we are interested in isomorphism preserving transformation CNF to Graph. Let $\phi_1,\phi_2$ be CNF formulas. Define $\phi_1$ and $\phi_2$ to be isomorphic $\phi_1 \cong \phi_2$ if there ...
joro's user avatar
  • 1,955
5 votes
1 answer
212 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 ...
Springberg's user avatar
7 votes
0 answers
170 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 ...
LeechLattice's user avatar
8 votes
1 answer
276 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 ...
Arnaud Casteigts's user avatar
3 votes
1 answer
141 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 ...
VS.'s user avatar
  • 539
7 votes
1 answer
235 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 ...
Stephane Bersier's user avatar
10 votes
1 answer
275 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 ...
user avatar
1 vote
0 answers
87 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}$ ...
Simon Segert's user avatar
6 votes
1 answer
191 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 ...
domotorp's user avatar
  • 14k
1 vote
0 answers
58 views

Is there an efficient way to reduce a set of graphs under isomorphism?

Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $...
oink's user avatar
  • 111
3 votes
0 answers
68 views

Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)

Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
Izaak Meckler's user avatar
3 votes
1 answer
127 views

Isomorphism Problems with Unknown Single-Exponential Algorithms

Isomorphism problems come in several variants: Group isomorphism can be solved in time $n^{O(\log n)}$ Graph isomorphism can be solved in time $n^{\log^{O(1)} n}$ Isomorphism of linear codes can be ...
verifying's user avatar
  • 1,072
30 votes
1 answer
5k views

What's the status of Babai's Graph isomorphism result?

It's been over a year since his January 2017 retraction and correction. Is there news? If not is this normal for validation to take this long? I would expect it would get plenty of attention. Has ...
Meir Maor's user avatar
  • 444
12 votes
1 answer
641 views

Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
Jarek Duda's user avatar
2 votes
0 answers
175 views

Practical polynomial-time implementation of bounded degree graph isomorphishm

There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not ...
Raven's user avatar
  • 137
13 votes
2 answers
939 views

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial. Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for ...
Mark S's user avatar
  • 1,125
-3 votes
1 answer
270 views

On a GI complete class

https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_classes_of_graphs says deciding diameter $2$ radius $1$ graph isomorphism is $GI$ complete. Is it possible only the diameter $2$ ...
Turbo's user avatar
  • 13k
12 votes
1 answer
278 views

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

I want to be very specific. Does anyone know of a disproof or a proof of the following proposition: $\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$ $\forall G, H \in STRUC[\Sigma_{graph}] (...
Samuel Schlesinger's user avatar
2 votes
2 answers
256 views

One Generalization of Graph Isomorphism Problem

Say I generalize the language which consists of pairs of isomorphic graphs to take the following form: $GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \...
Samuel Schlesinger's user avatar
4 votes
1 answer
331 views

A Combinatorial algorithm for trivalent graph isomorphism (except some small subclass)

I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent ...
new's user avatar
  • 358
5 votes
0 answers
193 views

Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
new's user avatar
  • 358
1 vote
0 answers
90 views

Easy instances for coset intersection problem

Coset Intersection Problem Given : $K,H \le S_n$, and $\sigma \in S_n$ Find : $K \cap H\sigma$ Known results are : $n^{O(\sqrt n )}$ time algorithm by L.Babai. $n^{O(1)} m^{O(\sqrt m )}$, where $...
new's user avatar
  • 358
17 votes
1 answer
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 ...
Nobo Dy's user avatar
  • 195
2 votes
1 answer
260 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 ...
Omar Shehab's user avatar
-2 votes
1 answer
269 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 graphs can ...
vzn's user avatar
  • 11k
4 votes
0 answers
155 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? ...
Michael's user avatar
  • 553
30 votes
2 answers
895 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 ...
Thomas Klimpel's user avatar
4 votes
0 answers
203 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 ...
Michael's user avatar
  • 553
4 votes
1 answer
186 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 ...
Michael Davis's user avatar
5 votes
0 answers
238 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 ...
Mohammad Al-Turkistany's user avatar
7 votes
1 answer
326 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$, ...
tarulen's user avatar
  • 251
5 votes
2 answers
545 views

Local Graph Isomorphism to construct Global Graph Isomorphism

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism? For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq ...
Michael's user avatar
  • 553
7 votes
1 answer
259 views

Complexity of a graph-rewriting problem

I recently came across the following problem which seems to fall in the context of graph rewriting problems: Input: A graph $G=(V,E)$ with maximum degree 3, an edge $e_0 \in E$ and pairs of graphs $(...
Listing's user avatar
  • 607
4 votes
1 answer
936 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 ...
Heinz-Heinrich's user avatar
-4 votes
1 answer
273 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 ...
joro's user avatar
  • 1,955
4 votes
1 answer
135 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?
Turbo's user avatar
  • 13k
5 votes
1 answer
245 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 ...
Turbo's user avatar
  • 13k
-2 votes
1 answer
417 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?
Turbo's user avatar
  • 13k
3 votes
1 answer
187 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 ...
user avatar