<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-12-20T08:20:55.523Z
Thank you. Is there an URL supporting this?
joro
CC BY-SA 3.0
2015-12-20T08:27:32.900Z
The conference program is [here](https://www.cs.cmu.edu/~venkatg/focs15/schedule/program_concise.html)
Joe Bebel
CC BY-SA 3.0
2015-12-20T08:16:24.667Z
2015-12-20T08:16:24.667Z
Joe Bebel
<p>To my knowledge, graph isomorphism for graphs with bounded clique width or bounded rank width is open.</p>

<p>2015 arxiv paper claims it is polynomial:</p>

<p><a href="http://arxiv.org/abs/1505.03737" rel="nofollow">Isomorphism Testing for Graphs of Bounded Rank Width</a></p>

<p>Abstract:</p>

<blockquote>
  <p>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. </p>
</blockquote>

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

<blockquote>
  <p>Q1 Is graph isomorphism still open for bounded clique width or bounded rank width?</p>
</blockquote>

CC BY-SA 3.0
2015-12-20T07:56:17.217Z
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.
Gamow
CC BY-SA 3.0
2015-12-20T08:21:37.847Z
@Gamow I don't claim any mistake.
joro
CC BY-SA 3.0
2016-05-15T12:47:23.553Z
One of the authors is Pascal Schweitzer. His [PhD thesis](http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf) 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](http://cstheory.stackexchange.com/questions/32237/is-anyone-aware-of-a-counter-example-to-the-dharwadker-tevet-graph-isomorphism-a/32291#32291). Very practical and down to earth, in a certain sense.
Thomas Klimpel
<graph-theory><graph-algorithms><graph-isomorphism>
Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial
joro
# Is graph isomorphism still open for bounded clique width or bounded rank width? 2015 paper claims it is polynomial

(Asked by: username_0 on 2015-12-20)

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](http://arxiv.org/abs/1505.03737)

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?

**Tags:** graph-theory, graph-algorithms, graph-isomorphism

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 I don't claim any mistake.  
> **username_2**: One of the authors is Pascal Schweitzer. His [PhD thesis](http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf) 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](http://cstheory.stackexchange.com/questions/32237/is-anyone-aware-of-a-counter-example-to-the-dharwadker-tevet-graph-isomorphism-a/32291#32291). Very practical and down to earth, in a certain sense.  

---

## 1 answers

### Answer by username_3 on 2015-12-20. Score: 8

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

> **Comments:**
> **username_0**: Thank you. Is there an URL supporting this?  
> **username_3**: The conference program is [here](https://www.cs.cmu.edu/~venkatg/focs15/schedule/program_concise.html)  

---

