Questions tagged [graph-isomorphism]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
AmirD's user avatar
  • 11
1 vote
0 answers
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 ...
SAS's user avatar
  • 43
0 votes
1 answer
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$-...
badroit's user avatar
  • 727
2 votes
1 answer
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$ ...
Tobias Kietreiber's user avatar
0 votes
2 answers
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 ...
XYJ's user avatar
  • 1
0 votes
0 answers
15 views

Ordered nodes/edges subgraph isomorphism

I'm given two graphs: $G=(V_G,E_G)$ and $H=(V_H,E_H)$. Additionally, there is a special ordering provided that is consisted between these two graphs. Node indexes below are mapped to the $G$: $V_G: [0,...
Alexandr Dorofeev's user avatar
0 votes
1 answer
376 views

Subgraph Isomorphism Problem NP complete?

I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set? I'm struggling to figure out this ...
Anonymous Molecule's user avatar
1 vote
1 answer
43 views

Constructive Graph Isomorphism Algorithm Literature

I have consulted the literature concerning graph isomorphism algorithms, and all papers I could find involve finding a canonical representation of a graph. So to decide whether two graphs are ...
Florian Ingels's user avatar
2 votes
0 answers
54 views

Subgraph Isomorphism with Same Number of Nodes

I am looking at a specific variant of subgraph isomorphism: Instance A graph $G = (V_G, E_G)$ and a target graph $H = (V_H, E_H)$ such that $|V_G| = |V_H|$. Question Is there a subgraph $G' = (V'_G, ...
Siolan's user avatar
  • 21
4 votes
2 answers
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 ...
Lev Knoblock's user avatar
1 vote
1 answer
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: ...
Daniel Donnelly's user avatar
2 votes
0 answers
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 ...
user856754's user avatar
2 votes
1 answer
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 ...
Daniel Donnelly's user avatar
2 votes
0 answers
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 ...
user3078261's user avatar
10 votes
2 answers
1k views

How to define a similarity between two graphs?

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}$(...
flawr's user avatar
  • 373
2 votes
0 answers
75 views

Bipartite Planar Graph Isomorphism

I want a hueristic algorithm for the following problem. Here, $V(G)$, $E(G)$ respectively refer to the vertex set and edge set of a graph $G$. Input: two planar bipartite graphs, $G,H$ and a map $\...
Zach Hunter's user avatar
1 vote
1 answer
2k views

How to prove graph isomorphism is NP?

I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.
user avatar
2 votes
0 answers
25 views

Why the soundness error in the $\mathrm{IP}$ of GNI can implicate $\mathrm{\Sigma_2} \subseteq \mathrm{\Pi_2}$ if GNI is co-NP-Complete?

PDF here shows a way to proof GI is NP-Complete $\implies \Sigma_2 = \Pi_2$. In the last step, it writes following: In other words, (1) is false in this case as required. Book Computational ...
linux40's user avatar
  • 121
2 votes
1 answer
66 views

Selecting the right partition in NAUTY

Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and ...
novadiva's user avatar
  • 331
3 votes
2 answers
762 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
Toothpick Anemone's user avatar
1 vote
0 answers
41 views

Directed weighted multigraph isomorphism algorithms

Are there known algorithms for the isomorphism problem for directed weighted multigraphs? If not, could one be created simply by adapting existing algorithms for graphs or digraphs, or is it entirely ...
apen's user avatar
  • 369
2 votes
0 answers
49 views

Are isomorphic (untyped) lambda expressions semantically equivalent?

"Isomorphic" is defined as having the same shape of syntax trees and the same bindings of variables. However, the variable names might be completely different. In other words, it is to say that we ...
apen's user avatar
  • 369
4 votes
1 answer
525 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
Agnishom Chattopadhyay's user avatar
2 votes
1 answer
104 views

Isomorphism problem on bounded degree digraphs

By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed. Is isomorphism ...
padawan's user avatar
  • 1,425
3 votes
1 answer
395 views

Rooted Tree Isomorphism Algorithm

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture: Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$. ...
Mateus Buarque's user avatar
2 votes
2 answers
2k views

Isomorphisms between regular graphs of same degree

Are all $n$-vertex regular graphs of degree $d$ isomorphic? Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number ...
Jim Newton's user avatar
5 votes
0 answers
209 views

What is the current fastest algorithm for finding the maximum common subgraph?

First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question. So, I'm currently researching algorithms for ...
joxeankoret's user avatar
7 votes
1 answer
2k views

If graph isomorphism is in P, is then P = NP?

I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold. Additionally, in ...
PascalIv's user avatar
  • 211
2 votes
0 answers
175 views

Implementation of Babai's GI algorithm

Babai proved that there is a quasi-polynomial-time algorithm for graph isomorphism. Has anyone implemented this algorithm? I think the code will be easier to understand than his paper, because of the ...
Zirui Wang's user avatar
3 votes
0 answers
36 views

Complementary of graph invariant

Graph invariant is a property that holds for two isomorphic graphs. For example, degree sequence is graph invariant. We can write $d(G) \ne d(G') \Rightarrow G \ncong G'$, although $d(G) = d(G')$ ...
novadiva's user avatar
  • 331
2 votes
3 answers
1k views

Hard connected instances for Weisfeiler-Lehman test of isomorphism

There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm. However, one of these graphs is disconnected. So what are the instances ...
novadiva's user avatar
  • 331
0 votes
0 answers
39 views

Repeated subgraph isomorphism query for single-edge addition for bounded degree graphs

I have a source undirected colored graph $G$ and a base query graph $g$. I know $g$ is subisomorphic to $G$ and now I want to identify which edges I can add to $g$ to preserve subisomorphism. That is, ...
Eric J's user avatar
  • 211
7 votes
1 answer
154 views

Is distinguishing Hadamard matrices _really_ NP-hard?

In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&...
Alex Meiburg's user avatar
0 votes
1 answer
133 views

Subgraph Isomorphism checking in Multigraphs

I am considering the following problem: Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs Question: Find a subgraph in G which is isomorphic to H Is there any algorithm available ...
Möbius's user avatar
  • 21
0 votes
1 answer
207 views

What is sub graph isomorphism?

I am confused about the definition of sub graph isomorphism, wikipedia says that the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one ...
Perseus14's user avatar
  • 141
8 votes
1 answer
421 views

Graph isomorphism and the automorphism group

A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not. ...
user88338's user avatar
3 votes
0 answers
57 views

Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
fingerprints's user avatar
1 vote
1 answer
146 views

Sub-Graph Isomorphism for graphs with multiple edge types and multiple node types

I found that there are algorithms like VFlib and LAD filtering for subgraph isomorphism with one edge type. For multiple node types,one idea could be color all node types with the same type and use ...
Perseus14's user avatar
  • 141
0 votes
0 answers
172 views

brute-force canonical labelling of a simple graph

I am looking for an example that shows how to canonically label a graph using brute-force approach. An example with a 3 vertex or 4 vertex simple graph is preferred.
GustavoS's user avatar
1 vote
1 answer
131 views

Is it a valid graph canonical form?

This question is motivated from this post. Let $G$ be a given graph, for each vertex $v \in V$, I will label $v$ with $Triangle(v)$. $Triangle(v) : $ means number of distinct triangles contain $v$. ...
Complexity's user avatar
  • 1,157
1 vote
1 answer
67 views

Proof that locality is sufficient in showing two graphs are isomorphic

Using the graph representation with (node, [list of neighbours]), to show that two graphs are isomorphic it is sufficient to: show that the vertices have the same degree and for every pair of ...
marianstefi20's user avatar
0 votes
1 answer
54 views

Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$, $$\#f = |\{v : f(v) \neq v\}|$$ For graph $G$ we denote: $$\#G = \max\{\#f : \text{$f$ is isomorphism $G$} \}$$ Prove ...
Haskell Fun's user avatar
1 vote
0 answers
92 views

Interactive protocols for showing knots are "hard" to untie

Given two graphs $G_1$ and $G_2$, a zero-knowledge interactive protocol for a prover to convince a verifier that $G_1\not\cong G_2$ entails: The verifier choosing a random $i\in\{1,2\}$ The verifier ...
Mark S's user avatar
  • 253
5 votes
1 answer
528 views

How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such ...
Mark S's user avatar
  • 253
2 votes
1 answer
68 views

Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree

From Wolfram: A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks ...
novadiva's user avatar
  • 331
4 votes
0 answers
196 views

Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
mikebolt's user avatar
  • 176
2 votes
1 answer
68 views

Algorithm for getting symetric vertex sets of undirected graph

For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph. My definition of symmetric vertex set is: Let $G$ be a graph with ...
Pepper M's user avatar
  • 325
3 votes
0 answers
144 views

Generate all non-isomorphic bounded-degree rooted graphs of bounded radius

I need to generate/enumerate isomorphism classes of vertex-rooted graphs with the following properties. Let $\Delta$ be the maximal degree (say 3 for subcubic graphs) and $r$ the maximal distance of a ...
JS_'s user avatar
  • 131
11 votes
1 answer
198 views

Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices

I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work. Given two adjacency matrices $G, H$, an ...
Lieuwe Vinkhuijzen's user avatar
4 votes
2 answers
12k views

Subgraph isomorphism reduction from the Clique problem

I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence: Let $H$ be the complete graph $K_k$; ...
Atte Juvonen's user avatar