# Questions tagged [graph-isomorphism]

The tag has no usage guidance.

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
• 101
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 ...
• 176
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 ...
• 225
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')$ ...
• 351
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 ...
• 131
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 ...
• 131
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 ...
• 159
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 ...
• 53
56 views

• 395
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 ...
• 121
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 ...
• 369
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 ...
• 960
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}\\ &&...
• 2,299
1 vote
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|$ ...
• 11
1 vote
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 ...
• 369
1 vote
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 ...
• 263
1 vote
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 ...
1 vote
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)? ...
• 2,299
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, ...
• 211
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 ...