22
votes
Accepted
If graph isomorphism is in P, is then P = NP?
We don't know.
We do know that $\textbf{P} = \textbf{NP}$ implies graph isomorphism is in $\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected ...
- 4,979
15
votes
Accepted
How to define a similarity between two graphs?
One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on ...
- 1,110
12
votes
Accepted
Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices
Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism ...
- 5,382
12
votes
How to define a similarity between two graphs?
A very natural metric for graphs on the vertex set $[n]$ is
$$
d(G,H) = \min_{\sigma \in S_n} |G \Delta H^\sigma|,
$$
where $|G \Delta H|$ is the size of the symmetric difference between the edge sets
...
- 275k
7
votes
Accepted
On graph isomorphism for weighted graphs
This on contrary appears to be a problem of greater difficulty than graph isomorphism. If you had a polynomial time solution to this problem,you can reduce graph isomorphism to it by keeping each edge ...
- 2,932
7
votes
Accepted
counterexample for this graph isomorphism algorithm
I've not looked closely at your algorithm so I'm not sure exactly what it does. However, it sounds quite a lot like colour refinement (also known as the 1-dimensional Weisfeiler-Lehman method). I ...
- 81.4k
7
votes
Hard connected instances for Weisfeiler-Lehman test of isomorphism
Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on ...
- 81.4k
7
votes
How to prove graph isomorphism is NP?
You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic.
Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,...
- 275k
7
votes
Accepted
Generating Isomorphic Graphs
create a graph $G = (V, E)$ as you like
generate a random permutation $\sigma\in \mathfrak{S}(V)$, for example with Knuth's algorithm
create the graph $G' = (V, E')$ where $E' = \{(\sigma(u), \sigma(v)...
- 12.5k
6
votes
Accepted
Is distinguishing Hadamard matrices _really_ NP-hard?
Both sources you cite are from the same author. Note the full quote:
For identifying the equivalence of two Hadamard matrices of order $n$, a complete search compares $(2^n n!)^2$ pairs of matrices ...
- 12.7k
5
votes
Accepted
Algorithm for getting symetric vertex sets of undirected graph
You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical ...
- 275k
5
votes
On graph isomorphism for weighted graphs
As sasha mentions, your problem is actually a generalization of the usual graph isomorphism. To put it differently, graph isomorphism is a special case of your problem, in which all weights are the ...
- 275k
5
votes
Enumerate all non-isomorphic graphs of a certain size
These papers might be of interest.
"On the succinct representation of graphs",
Gyorgy Turan,
Discrete Applied Mathematics,
Volume 8, Issue 3, July 1984, pp. 289-294
http://www.sciencedirect.com/...
- 278
5
votes
Isomorphisms between regular graphs of same degree
Of course not.
Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.
...
- 4,979
5
votes
Accepted
Isomorphisms between regular graphs of same degree
Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take ...
- 81.4k
4
votes
Group isomorphism to graph ismorphism
Not so fast. There is a big lurking ambiguity here:
How do you input your group for computation?
Unlike graphs, groups can be input be means that are far different in terms of input size and ...
- 281
4
votes
Has the graph isomorphism problem been solved?
Laszlo Babai has claimed to have found a quasipolynomial solution for the graph isomorphism problem as of November 11th 2015.
... and retracted the claim yesterday (4/1/2017):
Source: http://...
- 159
4
votes
Accepted
Can the isomorphic graph problem be solved in deterministic polynomial time?
Your approach sounds intuitively appealing on first glance, but it doesn't work. It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time. There has to be a way to ...
D.W.♦
- 156k
4
votes
Enumerate all non-isomorphic graphs of a certain size
There is a paper from the early nineties dealing with exactly this question:
Efficient algorithms for listing unlabeled graphs by Leslie Goldberg.
The approach guarantees that exactly one ...
- 41
4
votes
Accepted
How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?
I can see some similarity too, but only in a loose sense; there are also some significant differences.
Here's the similarity. Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$. Then you can ...
D.W.♦
- 156k
4
votes
Efficient algorithm for graph canonization for directed acyclic graphs?
According to Wikipedia (which references lecture notes of Zemlyachenko, Korneenko and Tyshkevic), isomorphism of directed acyclic graphs is GI-complete. Therefore any polynomial time canonicalization ...
- 275k
4
votes
Accepted
Generating all directed acyclic graphs with constraints
For small $n$, the easiest solution might be to download a list of all non-isomorphic graphs and then filter them according to your condition.
You might take a look at Brendan McKay's collection, ...
D.W.♦
- 156k
4
votes
Subgraph isomorphism reduction from the Clique problem
The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the ...
- 5,382
4
votes
Hard connected instances for Weisfeiler-Lehman test of isomorphism
Connect all vertices to a common one.
- 275k
4
votes
Generating Isomorphic Graphs
While Nathaniel's response answered my question perfectly, part of my question also asked about where to find testsets for graph isomorphism algorithms. As such, I thought I'd start a list.
http://...
3
votes
Accepted
Find Mapping Node in a Graph
You want to solve the problem of graph isomorphism (GI). GI is not known to be in P or NP-complete; that is, we do not know any efficient algorithms.
Many algorithms have been proposed for GI. None ...
- 72k
3
votes
counterexample for this graph isomorphism algorithm
Although the question is somewhat different, the following answer by Yuval Filmus also answers my question:
There are two non-isomorphic graphs with 16 vertices in which each
vertex has 6 ...
- 2,469
3
votes
Can the isomorphic graph problem be solved in deterministic polynomial time?
The best algorithm for graph isomorphism, due to Babai, runs in time $e^{O(\log^C n)}$ for some constant $C > 1$. We don't know any polynomial time algorithm for the problem.
Your algorithm, which ...
- 275k
3
votes
Graph isomorphism problem for labeled graphs
I've found out that the algorithm belongs in the category of k-dimension Weisfeiler-Lehman algorithms, and it fails with regular graphs. For more here:
http://dabacon.org/pontiff/?p=4148
Original ...
- 39
3
votes
Accepted
On graph isomorphism over exponential word sizes
Yes, this is known. It has been shown that if you allow unlimited word sizes, then programs in the RAM model can compute arbitrary #PSPACE problems in polynomial time. #PSPACE is a huge complexity ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible