-3
$\begingroup$

To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open.

2015 arxiv paper claims it is polynomial:

Isomorphism Testing for Graphs of Bounded Rank Width

Abstract:

We give an algorithm that, for every fixed $k$, decides isomorphism of graphs of rank width at most $k$ in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

The paper is 48 pages and doesn't appear published in peer reviewed journal. There is only one citation on Scholar.google.

Q1 Is graph isomorphism still open for bounded clique width or bounded rank width?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ The authors of this paper are strong and well-respected researchers. If you have found a mistake in their paper, you should simply contact them. $\endgroup$ – Gamow Dec 20 '15 at 7:56
  • $\begingroup$ @Gamow I don't claim any mistake. $\endgroup$ – joro Dec 20 '15 at 8:21
  • $\begingroup$ One of the authors is Pascal Schweitzer. His PhD thesis gave me a very good introduction into different existing approaches to solve graph isomorphism, and how to shoot them down. I also used his software while shooting down the Dharwadker-Tevet Graph Isomorphism algorithm. Very practical and down to earth, in a certain sense. $\endgroup$ – Thomas Klimpel May 15 '16 at 12:47
8
$\begingroup$

This paper was presented at FOCS 2015 and is published in those proceedings. As far as I am concerned, this means it was peer reviewed and found to be plausibly correct, within the limits of a conference review process.

So I would not consider this problem open, unless a specific flaw is discovered or there is some additional evidence introduced that this paper is not correct.

Of course, that is not the same as a journal review process, which can often take years (this paper is only from 7 months ago!)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Is there an URL supporting this? $\endgroup$ – joro Dec 20 '15 at 8:20
  • 1
    $\begingroup$ The conference program is here $\endgroup$ – Joe Bebel Dec 20 '15 at 8:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.