Questions tagged [graph-isomorphism]
The graph-isomorphism tag has no usage guidance.
76
questions
0
votes
0
answers
21
views
Does deciding the following language take polynomial time or constant time?
I've written an algorithm that decides the following language:
$$ \{ \langle G, H \rangle \mid G, H \text{ are undirected graphs, } \lvert V_H \rvert \leq 10 \text{ and } G \text { is isomorphic to a ...
- 13
4
votes
2
answers
105
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 ...
- 143
1
vote
1
answer
26
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:
...
2
votes
0
answers
25
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 ...
- 21
2
votes
1
answer
36
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 ...
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 ...
- 121
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}$(...
- 363
2
votes
0
answers
52
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 $\...
- 375
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.
user112776
2
votes
0
answers
19
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
2
votes
1
answer
57
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 ...
- 331
3
votes
2
answers
543
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 ...
1
vote
0
answers
34
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 ...
- 359
2
votes
0
answers
40
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 ...
- 359
4
votes
1
answer
434
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 ...
2
votes
1
answer
77
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 ...
- 1,405
3
votes
1
answer
275
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$.
...
- 189
2
votes
2
answers
1k
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 ...
- 315
5
votes
0
answers
183
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
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 ...
- 211
2
votes
0
answers
124
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 ...
- 824
3
votes
0
answers
35
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')$ ...
- 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 ...
- 331
0
votes
0
answers
38
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
7
votes
1
answer
126
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&...
- 816
0
votes
1
answer
112
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 ...
- 21
0
votes
1
answer
188
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 ...
- 141
8
votes
1
answer
288
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.
...
- 81
3
votes
0
answers
56
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
1
vote
1
answer
86
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 ...
- 141
0
votes
0
answers
165
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.
- 1
1
vote
1
answer
101
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$.
...
- 1,127
1
vote
1
answer
62
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 ...
0
votes
1
answer
46
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 ...
- 369
1
vote
0
answers
88
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 ...
- 253
5
votes
1
answer
512
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 ...
- 253
2
votes
1
answer
59
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 ...
- 331
4
votes
0
answers
170
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
2
votes
1
answer
67
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 ...
- 325
3
votes
0
answers
138
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
11
votes
1
answer
168
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 ...
- 4,167
4
votes
2
answers
10k
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$; ...
- 297
4
votes
0
answers
103
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
1
vote
1
answer
203
views
Find Mapping Node in a Graph
Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.
If we give a node in Graph A, how to find the corresponding one in Graph B?
Finally, we need ...
- 113
3
votes
1
answer
194
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 ...
- 221
3
votes
2
answers
810
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 ...
- 221
2
votes
1
answer
243
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 ...
- 281
3
votes
1
answer
131
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 ...
- 77
2
votes
1
answer
56
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).
user39969
0
votes
1
answer
56
views
Restricting possible permutations in Graph Isomorphism problem
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.
Call two such ...
user39969