Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [graph-isomorphism]

The tag has no usage guidance.

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
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
386 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
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
2 votes
0 answers
27 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
2 votes
0 answers
81 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
2 votes
0 answers
26 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
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
2 votes
0 answers
186 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
2 votes
0 answers
74 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ &&...
frafl's user avatar
  • 2,299
1 vote
0 answers
28 views

Efficiently generating the smallest directed graph subject to degree constraints that yields a requested flow

Given two (small-ish) sequences $I$ and $O$ of rational numbers with $\sum_{x \in I}x=\sum_{y \in O}y$, generate a directed graph $G = (V,E)$ with minimum $|V|$ that respects the following: $|I|$ ...
MarioVX's user avatar
  • 11
1 vote
0 answers
47 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
1 vote
0 answers
93 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
  • 263
1 vote
0 answers
109 views

Complexity lower bounds via Cook reductions

Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information ...
Mohammad Al-Turkistany's user avatar
1 vote
0 answers
22 views

Name and complexity of a problem concerning metrics

Do you know the name of the following problem and can you give a reference for its complexity (especially the relation to $\mathsf{GraphIsomorphism}$ and/or other isomorphism/homomorphism problems)? ...
frafl's user avatar
  • 2,299
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
0 votes
0 answers
173 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
0 votes
0 answers
107 views

Isomorphic induced subgraph problem using Courcelle's theorem

The isomorphic induced subgraph problem, is the problem of deciding whether, given two graphs $G$ and $H$, $G$ contains an induced subgraph isomorphic to $H$. Is there a proof using ...
opsorst's user avatar