# Tagged Questions

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

45 views

### Individualization of two Subgraphs

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
62 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 ...
114 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 ...
168 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 ...
190 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$,...
229 views

198 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 ...
182 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 ...
109 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?
140 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 ...
160 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?
74 views

### Fourier transformation of the automorphism group of a graph

Following is an example of permutation cycle graph $\Gamma$ for a given permutation $\pi = \left(1\text{ } 2\right) \left(3\text{ } 4\text{ } 5\text{ } 6\right)$. The adjacency matrix $A$ is given ...
106 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 ...
92 views

336 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 ...
137 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 ...
573 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 ...
846 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 ...
291 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 ...
134 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 ...
307 views

### Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
32 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 ...
116 views

### When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
138 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). ...
478 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 ...
210 views

### Is the finite inverse semigroup isomorphism problem GI-complete?

Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.
200 views

### Known algorithms for Graph isomorphism [closed]

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?
164 views

### checking isomorphism between K regular graph

Problem Input is a k regular graph of n vertices and I have to check whether this is isomorphic to another given k regular graph G. This is a restricted version of graph isomorphism in the sense that ...
580 views

141 views

### When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory. As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI. A ...
220 views

### Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

This paper gives example of polynomial GI for certain graphs. Probably I am misunderstanding the paper, but appears to me it implies polynomial GI for cubic, $4$-regular and probably higher degree ...
352 views

### “Tiny” Graph Isomorphism

While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind. Suppose that we have a polynomial time ...
58 views

### Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

There are two ways to extend infinitary logic with counting: Grädel's way (cf. p. 11): We extend $L_{\infty\omega}$ by introducing a counting existential quantifier:  \mathcal{A} \models \exists^{...
158 views

### Complexity of counting graph endomorphisms

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An ...
142 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, ...
270 views

### Testing isomorphism of asymmetric graphs

While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) ...
288 views

### graph isomorphism given a partial isomorphism

Is there an approach to graph isomorphism considering that we are already given a partial isomorphism ? In particular, it would be interesting to have conditions on this partial isomorphism that makes ...
Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...