Questions tagged [graph-isomorphism]
The graph-isomorphism tag has no usage guidance.
1
vote
0answers
21 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 ...
2
votes
0answers
17 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')$ ...
4
votes
3answers
235 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 ...
0
votes
0answers
26 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, ...
7
votes
1answer
63 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&...
0
votes
1answer
70 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 ...
0
votes
1answer
44 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 ...
8
votes
1answer
120 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.
...
4
votes
0answers
46 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 ...
1
vote
1answer
29 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 ...
0
votes
0answers
84 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
vote
1answer
51 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
vote
1answer
35 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
1answer
39 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 ...
1
vote
0answers
74 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 ...
6
votes
1answer
278 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 ...
3
votes
1answer
46 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 ...
4
votes
0answers
80 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 ...
3
votes
1answer
60 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 ...
3
votes
0answers
95 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 ...
10
votes
1answer
87 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 ...
2
votes
1answer
4k 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$; ...
3
votes
0answers
66 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 ...
1
vote
1answer
138 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 ...
3
votes
1answer
115 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 ...
3
votes
2answers
314 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 ...
3
votes
1answer
193 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 ...
4
votes
1answer
112 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 ...
2
votes
1answer
45 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).
0
votes
1answer
45 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 ...
0
votes
1answer
90 views
On deterministic weighted graph isomorphism from randomized
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.
Basically take an real edge weight set $\{w_1,\dots,...
4
votes
2answers
367 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 ...
1
vote
5answers
655 views
On graph isomorphism for weighted graphs
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.
Basically take an real edge weight set $\{w_1,\dots,...
1
vote
1answer
806 views
How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]
I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem.
Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
3
votes
2answers
329 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 ...
0
votes
0answers
70 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 ...
4
votes
2answers
1k 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 ...
2
votes
0answers
572 views
Implications of Babai's Proof that Graph Isomorphism is Quasi Polynomial Time [closed]
In the context of the very recent talk by Lazlo Babai outlining that Graph Isomorphism (GI) is Quasi Polynomial Time, what are the broader implications of this result? (I'm assuming the claim will ...
3
votes
0answers
162 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 ...
1
vote
0answers
78 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 ...
0
votes
1answer
36 views
Necessities for two undirected graphs being isomorphic
As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic:
$|V| = |V'|$
$|E| = |E'|$
$G$ has $j$ nodes of degree $k$ $...
6
votes
1answer
795 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-...
12
votes
2answers
336 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 ...
13
votes
4answers
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 ...
3
votes
1answer
128 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.
...
5
votes
1answer
42 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 ...
24
votes
4answers
3k 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$ ...
11
votes
2answers
2k 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 ...
4
votes
1answer
177 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$ ...
0
votes
1answer
72 views
graph isomorphism completeness of class X and not-X
there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg [1] & many others.
suppose a class both $X$ and not-$X$ of graphs are proven GI complete. ...
