# Tag Info

24

No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm. As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open ...

23

Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's  and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as geng in McKay'...

22

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 graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this ...

18

No, the graph isomorphism problem has not been solved. The paper you link to is from 2007–2008, and hasn't been accepted by the wider scientific community. (If it had been, I would have known about it.) Graph isomorphism, like many other famous problems, attracts many attempts by amateurs. They are almost always wrong. I would advise against trying to ...

15

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 the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost ...

12

The reduction is described in a classic paper of Miller.

12

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 testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of ...

12

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 of $G$ and $H$, and $H^\sigma$ is the graph obtained from $H$ by renaming the vertices according to the permutation $\sigma$. I believe it satisfies all your ...

8

I would be very dubious that it has (in the sense of the proof of existence of a polynomial time algorithm). While it is not impossible that the paper is correct, there are a number of warning signs: The author has not published the result in a peer reviewed venue (even after 7 years). The author does not seem to have published anything else, anywhere. The ...

7

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 suggest you look at the following paper, which will both explain that method and show a class of graphs whose isomorphism problem it cannot solve, even though graph ...

7

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 weight say equal to some constant $c$. Also graph isomorphism is not known to have a polynomial time solution. It is a still an open question.

7

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 the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF). Take any connected, $3$-regular graph $G=(V,E)$. We will produce ...

7

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,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$. You take it from here.

6

The Wikipedia page mentions that digraph isomorphism is GI-complete, and gives a reference. For the proof, something along the following lines should work. Replace each $u\to v$ edges with a path $u\to x\to y\to v$, and attack a clique of size $A$ to $x$, and a clique of size $B \neq A$ to $y$. Choose $A,B > n$ to ensure to these are the only cliques of ...

6

You might be interested in this paper: Aidan Hogan: Skolemising Blank Nodes while Preserving Isomorphism. WWW 2015: 430-440 It has an algorithm (based on Nauty) for testing the isomorphism of RDF graphs, which are essentially directed labelled graphs that may contain fixed labels. The algorithm takes labels into account to narrow the search space. If you ...

6

I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions. For subgraph isomorphism in general (i.e. not planar), the practical state of ...

6

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 and is known to be an NP-hard problem when $n$ increases. I don't think the author knows what NP-hard entails and confuses it with simply exponential. Further ...

5

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 same. Therefore your problem can only be more difficult. On the other hand, it is easy to reduce your problem to the usual graph isomorphism. Assuming that only ...

5

The answer is no. A counterexample is given by the following two graphs both having $(-1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)$ as the multiset that you describe. If you want to play further, you can use the following Sage program that found them def tupleDet(G): ...

5

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/science/article/pii/0166218X84901264 "Succinct representation of general unlabelled graphs", Moni Naor, Discrete Applied Mathematics, Volume 28, Issue 3, September ...

5

Here's a simpler approach to testing whether two descriptions of regular languages $L_1, L_2$ are descriptions of the same language ($L_1 = L_2$). Compute the complement of $L_2$, denoted $\overline{L_2}$. If it's represented as a DFA, this can be done in polynomial time (linear I believe). Compute the intersection of the automata, $L_1 \cap \overline{L_2}$...

5

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 graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from ...

4

I propose an improvement on your third idea: Fill the adjacency matrix row by row, keeping track of vertices that are equivalent regarding their degree and adjacency to previously filled vertices. So initially the equivalence classes will consist of all nodes with the same degree. When a newly filled vertex is adjacent to only some of the equivalent nodes, ...

4

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 post follows: Years ago, I created a simple and flexible algorithm for exactly this problem (graph isomorphism with labels). I named it "Powerhash", and to ...

4

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://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

4

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 resulting complexity. The version cited in Miller is one of the least natural and for example you wont find that in a computer algebra system such as GAP, Magma, ...

4

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 provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity. Examples: ...

4

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, constructed using geng as part of the Nauty graph isomorphism package. See Enumerate all non-isomorphic graphs of a certain size for more details and citations.

4

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 clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this ...

4

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 think of the Bitcoin proof-of-work as being: find $x$ such that $H_2(x)=0$. This is loosely similar to the Goldwasser-Sipser protocol; you could imagine that ...

Only top voted, non community-wiki answers of a minimum length are eligible