# Questions tagged [graph-isomorphism]

The tag has no usage guidance.

84 questions
Filter by
Sorted by
Tagged with
1 vote
47 views

### GNI public coin interactive proof: why randomize y?

I've read this scribe that provides a public coin interactive proof for graph non-isomorphism. In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
1 vote
69 views

### How does the standard proof that IP is in PSPACE apply to, say, the graph non-isomorphism problem?

I learned years ago that $IP \subseteq PSPACE$ since you could simulate all sets of messages and then determine the probability of success. But lately I’ve been looking at the standard proof of this ...
53 views

### Is graph isomorphism $P$-hard?

Intuitively speaking, it would seem like the graph isomorphism problem (which might be $NP$-intermediate) should be $P$-hard. But maybe it's not? Or maybe it's an open question? If it is indeed $P$-...
37 views

### Largest isomorphic subgraphs of two graphs with features

the following question came up in a problem I am working on: Suppose you have two graphs $G_1=(V_1, E_1), G_2=(V_2,E_2)$ that have features attached to them, i.e. to every $v\in V_1$ or $v\in V_2$ ...
199 views

### Automata: Are there algorithms to judge whether two automata are isomorphic?

When I want to judge whether two regular forms represent the same language, I have learned the next method: create the (non-deterministic) finite-state automata which accepts the language the given ...
15 views

517 views

### Generating Isomorphic Graphs

Is there a way of generating random isomorphic graphs for the purposes of testing tools like Nauty or BLISS? Every paper I've found says the authors had a database of certain isomorphic graphs, but I ...
1 vote
66 views

### Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
31 views

### The practical importance of Graph Isomorphism Problem

It is known that Graph Isomorphism is important in chemistry (studying molecule structures) and in chip design. Are there other applications of significant practical importance, and how much money is ...
58 views

### Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
25 views

### Subgraph isomorphism index/precomputation

I'm currently working on problem in which a set of graphs $T=\{t_1,\dots,t_n\}$ is given and fixed. Given a graph $m$ I want to check which of the $t_i$ are subgraphs of it, as quick as possible. Is ...
Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(...