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.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
24
votes
0answers
1k views

Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
7
votes
0answers
127 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 ...
7
votes
0answers
396 views

Number of non-isomorphic induced subgraphs of a graph

Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs). ...
7
votes
0answers
376 views

Embedded dynamic programming (and planar subgraph isomorphism)

In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
5
votes
0answers
177 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 ...
5
votes
0answers
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 ...
4
votes
0answers
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 ...
4
votes
0answers
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? ...
4
votes
0answers
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 ...
3
votes
0answers
59 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\}^...
3
votes
0answers
168 views

Fixed parameter tractable algorithms for graph isomorphism

What are the future directions in fixed parameter tractability of graphs isomorphism after these two recent papers: Reduction Techniques for Graph Isomorphism in the Context of Width Parameters, ...
2
votes
0answers
123 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 ...
2
votes
0answers
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 ...
2
votes
0answers
160 views

Fractional chromatic number of Johnson graphs

Johnson graphs have a dual like construction to Kneser graphs in the sense that in Kneser we encode non-intersecting k-sets by joining vertices that represent the sets while in Johnson graphs we ...
2
votes
0answers
294 views

On the subgraph isomorphism problem

The subgraph isomorphism problem problem is to determine given $G$ and $H$ whether $G$ is a subgraph of $H$. Let $G$ and $H$ be regular graphs with degree of $H$ greater than degree of $G$. Does the ...
1
vote
1answer
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 ...
1
vote
0answers
57 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}$ ...
1
vote
0answers
53 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 $...
1
vote
0answers
79 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 $...
1
vote
0answers
55 views

First register in the hidden subgroup representations of Simon's and graph isomorphism problems

The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
1
vote
0answers
35 views

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 ...
1
vote
0answers
125 views

Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
1
vote
0answers
79 views

Definition of Clique vertex and separator vertex

While converting a tree decomposition of graph to Normalized tree decomposition, the definitions of clique vertex and separator vertex are used in Sequential and parallel algorithms for embedding ...
1
vote
0answers
56 views

Number of non-isomorphic codes

We have number of non-isomorphic graphs given in http://planetmath.org/enumeratinggraphs Over an alphabet $q$ how many non-isomorphic $[n,k,d]_q$ codes are possible particularly in the special case ...
1
vote
0answers
102 views

Equivalence relations on strongly regular graphs with same parameters

Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter $(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set? My motivation is to approach ...