Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graph-isomorphism]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
35 votes
5 answers
9k views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
D.W.'s user avatar
  • 161k
13 votes
4 answers
2k views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
Tyler Spaeth's user avatar
13 votes
2 answers
1k views

Group isomorphism to graph ismorphism

In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For ...
Jernej's user avatar
  • 2,460
12 votes
2 answers
4k views

Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
Max's user avatar
  • 121
11 votes
1 answer
208 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
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
9 votes
2 answers
320 views

How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$ So, to solve the problem, if two graphs are ...
user avatar
8 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
  • 221
8 votes
1 answer
458 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
7 votes
1 answer
158 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
7 votes
1 answer
321 views

Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch

I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ ...
user avatar
6 votes
1 answer
1k views

Subgraph isomorphism in planar graphs

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-...
mohsaied's user avatar
  • 173
6 votes
1 answer
536 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
  • 263
5 votes
1 answer
58 views

Is complexity of $GI_{di}$ same as $GI_{un}$?

Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)? It is clear $$GI_{un}\leq GI_{di}$$ since the set of ...
Turbo's user avatar
  • 2,891
5 votes
1 answer
273 views

Efficient algorithm for graph canonization for directed acyclic graphs?

I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed ...
BeeOnRope's user avatar
  • 241
5 votes
2 answers
208 views

Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
Massimiliano Pavan's user avatar
5 votes
1 answer
90 views

Subgraph isomorphisms: does large out-expansion imply large in-expansion?

Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)...
D.W.'s user avatar
  • 161k
5 votes
0 answers
212 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
4 votes
2 answers
685 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
4 votes
2 answers
4k views

Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show ...
intcreator'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$; ...
bkoodaa's user avatar
  • 367
4 votes
2 answers
654 views

NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are ...
user3280193's user avatar
4 votes
1 answer
560 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
4 votes
0 answers
213 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
4 votes
0 answers
106 views

Shortest paths in isomorphic graphs with different edge weights

I'm looking for a way to find the shortest paths from a source to all destinations in isomorphic undirected graphs with different edge weights. The only thing I can think of is using Dijkstra on each ...
devil0150's user avatar
  • 225
3 votes
3 answers
4k views

Finding an isomorphism between finite automata

Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states. More specifically, heres an example: It's easy to generate a regular expression ...
user avatar
3 votes
2 answers
978 views

Generating all directed acyclic graphs with constraints

I am interested in listing all the unlabeled1 acyclic digraphs with n vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for ...
BeeOnRope's user avatar
  • 241
3 votes
1 answer
114 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,435
3 votes
1 answer
458 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
3 votes
1 answer
254 views

Common subgraph isomorphism with K vertex

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph A. ...
Zyoo's user avatar
  • 131
3 votes
1 answer
133 views

If graph isomorphism yields a polynomial time algorihtm

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
Someguy's user avatar
  • 77
3 votes
2 answers
858 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
3 votes
0 answers
37 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
  • 351
3 votes
0 answers
58 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
3 votes
0 answers
145 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
3 votes
0 answers
387 views

Enumerate all non-isomorphic graphs of size n

I am trying to enumerate all non-isomorphic graphs of size n and found this question: Enumerate all non-isomorphic graphs of a certain size The accepted answer ...
Alex's user avatar
  • 159
2 votes
3 answers
2k 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
  • 351
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
2 votes
2 answers
589 views

counterexample for this graph isomorphism algorithm

I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can ...
Albert Hendriks's user avatar
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
2 votes
1 answer
70 views

On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
user avatar
2 votes
1 answer
45 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
2 votes
1 answer
86 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: ...
HighAsAKiteOnMath's user avatar
2 votes
1 answer
62 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 ...
HighAsAKiteOnMath's user avatar
2 votes
1 answer
68 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
  • 351
2 votes
1 answer
75 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
  • 351
2 votes
1 answer
261 views

Automorphism of a Graph with a given Set of Permutations

Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$. The permutation set $\alpha$ has automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the ...
Michael's user avatar
  • 291
2 votes
0 answers
73 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
  • 53
2 votes
0 answers
56 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
2 votes
0 answers
33 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