# Tag Info

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
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
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

### 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
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
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

### 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

• 12.5k
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
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

### 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

### 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

### 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
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

### 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

### 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
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 ...
• 156k

### 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 ...
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 ...
• 156k

### 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
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, ...
• 156k

### 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

### Hard connected instances for Weisfeiler-Lehman test of isomorphism

Connect all vertices to a common one.
• 275k

### 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://...
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

### 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

### 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

### 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