<p>For the second question: Fixing rank-width (equivalently, fixing clique-width), polynomial time solvability of GI is not known. Recently, <a href="https://cstheory.stackexchange.com/users/4854/m-kante">Mamadou Kanté</a> posed an open question <a href="http://www.lsi.upc.edu/~sedthilk/grow/Open_Problems_GROW_2013.pdf" rel="nofollow noreferrer">if the graph isomorphism problem can be solved in polynomial time for graphs of bounded linear rank-width</a>.</p>

CC BY-SA 3.0
2013-12-25T10:13:44.290Z
2013-12-25T11:43:17.803Z
2017-04-13T12:32:28.053Z
G. Baum
<p>For the third question you can also take a look to <a href="http://www.graphclasses.org" rel="nofollow">www.graphclasses.org</a> : launch the java applet and select Problems -> Boundary/Open problems -> Graph isomorphism.</p>

<p>You'll get a huge list of graph classes for which the GI problem status is <em>unknown to ISGCI</em> (it could be in P or GI-complete); probably for some of them the GI-completeness has been already settled, or  simply they have not been studied, yet; but it is a good starting point to search for papers about them.</p>

CC BY-SA 3.0
2014-10-08T14:28:24.437Z
2014-10-08T14:34:52.667Z
2014-10-08T14:34:52.667Z
Marzio De Biasi
<p>For the third question: The survey paper of Brandstadt, Le, and Spinrad, Graph Classes: A Survey, SIAM, 1999, contains several graph classes for which GI-completeness is not known. One such class is <a href="https://dspace.jaist.ac.jp/dspace/bitstream/10119/4896/1/C3941.pdf" rel="nofollow">trapezoid graphs</a>. Another class is circular arc graphs which is mentioned as open problem in the introduction of the paper, <a href="http://www.mdpi.com/1999-4893/6/1/60" rel="nofollow">Tractabilities and Intractabilities on Geometric Intersection Graphs</a> by Uehara.</p>

<p><strong>EDIT</strong>: The Graph Isomorphism problem for tournaments is not known to be GI-complete.</p>

CC BY-SA 3.0
2013-12-20T13:50:20.543Z
2014-10-08T13:28:31.837Z
2014-10-08T13:28:31.837Z
Mohammad Al-Turkistany
<p>For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open.</p>

<ul>
<li>pathwidth / treewidth (see [2], has been asked <a href="https://cstheory.stackexchange.com/questions/19699/fpt-algorithm-for-partial-k-tree-isomorphism">here</a>), maybe solved: <a href="http://arxiv.org/abs/1404.0818" rel="nofollow noreferrer">http://arxiv.org/abs/1404.0818</a></li>
<li>cutwidth / bandwidth [1]</li>
<li>treewidth-k vertex deletion set size (feedback vertex set number in [7])</li>
<li>tree / path distance width (see [1]), <strike>connected tree distance width (see [3], however you can get quite close to the last one, see section 6.4. of my <a href="http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/mitarbeiter/fuhlbrueck/diplomarbeit-fuhlbrueck-rev1.pdf" rel="nofollow noreferrer">diploma thesis</a> ) </strike>: solved by Y. Otachi  and P. Schweitzer : <a href="http://arxiv.org/abs/1403.7238" rel="nofollow noreferrer">http://arxiv.org/abs/1403.7238</a></li>
<li>clique-width / shrub-depth (or SC-depth) (see [<a href="http://www.fi.muni.cz/~hlineny/res-en.html#recent" rel="nofollow noreferrer">4</a>])</li>
<li>maximum degree [5]</li>
<li>genus [6] / crossing number [8]</li>
</ul>

<p>Note that there is active ongoing research for some them.</p>

<p>[1] : K. Yamazaki, H. L. Bodlaender, B. de Fluiter and D. M. Thilikos. Isomorphism
for graphs of bounded distance width. Algorithmica 24.2 (1999)</p>

<p>[2] : H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chro-
matic index on partialk-trees. Journal of Algorithms 11.4 (1990)</p>

<p>[3] : Y. Otachi. Isomorphism for Graphs of Bounded Connected-Path-Distance-
Width. Algorithms and Computation. Springer, 2012</p>

<p>[<a href="http://www.fi.muni.cz/~hlineny/res-en.html#recent" rel="nofollow noreferrer">4</a>] : <a href="http://www.fi.muni.cz/~hlineny/res-en.html#recent" rel="nofollow noreferrer">http://www.fi.muni.cz/~hlineny/res-en.html#recent</a></p>

<p>[5] : L. Babai and E. M. Luks. Canonical labeling of graphs. STOC '83.</p>

<p>[6] : I. S. Filotti and J. N. Mayer. A polynomial-time algorithm for determining the
isomorphism of graphs of fixed genus. STOC '80 / 
G. Miller. Isomorphism testing for graphs of bounded genus. STOC '80 </p>

<p>[7] : S. Kratsch and P. Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. SWAT 2010 </p>

<p>[8] : <a href="http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf" rel="nofollow noreferrer">http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf</a></p>

CC BY-SA 3.0
2013-12-20T16:48:41.143Z
In terms of active relevant research in this area, there are a few additional references I would suggest. [A] This paper [here](http://people.csail.mit.edu/adam/Papers/tree-depth.pdf) from IPEC 2012, shows graph isomorphism is fixed-parameter tractable in the tree-_depth_ of a graph, which is a parameter related to tree-width. [B] This paper [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6517&rep=rep1&type=pdf) shows that graph isomorphism for chordal graphs is FPT in the size of the largest simplicial component.
Adam Bouland
CC BY-SA 3.0
2013-12-20T17:07:15.633Z
One more reference is [this paper](http://dl.acm.org/citation.cfm?doid=1374376.1374443) from STOC '08, which comes _very close_ to showing that graph isomorphism is FPT in the genus of a graph. More specifically, they show that graph isomorphism is in linear time when restricted to the class of graphs which admit a polyhedral embedding in a fixed surface $S$of genus $g$.
Adam Bouland
CC BY-SA 3.0
2013-12-24T05:24:07.580Z
@Adam Bouland  Is there any FPT or Polynomial time algorithms for Graph isomorphism for bounded band width.
Kumar
CC BY-SA 3.0
2013-12-26T13:53:23.073Z
@Kumar It is poly-time solvable but not known to be FPT. See Yamazaki et al. [1] in the answer of frafl.
Yota Otachi
CC BY-SA 3.0
2013-12-20T13:57:23.217Z
2014-05-05T15:40:37.570Z
2017-04-13T12:32:28.077Z
frafl
<p>Presently I am doing literature survey on Graph isomorphism (GI) problem.</p>

<p>I would like to know some open questions related to the following  </p>

<ol>
<li><p>What are the graph parameters for which fixed parameter tractability of GI is an open problem. </p></li>
<li><p>What are the graph parameters, by fixing them polynomial time solvability of GI is not known.</p></li>
<li><p>Complexity of GI when restricted to many graph classes is equivalent to general GI (GI-Completeness). What are the graph classes for which GI-completeness is not known. </p></li>
</ol>

<p>Thank you.</p>

CC BY-SA 3.0
2013-12-20T13:29:25.570Z
I'm not aware of any definitive answers to your questions.  If you find partial answers (which might require looking at dozens of published research papers), then it would be great if you could link to the summary you create, or give its highlights, as an answer.
András Salamon
CC BY-SA 3.0
2013-12-20T17:08:20.687Z
re 3, question. for the many graph classes $X$ proven GI complete, is the question "are not-$X$ graphs GI complete?" open? does that make any sense? related [cs.se question](http://cs.stackexchange.com/questions/19160/graph-isomorphism-completeness-of-class-x-and-not-x)
vzn
<graph-isomorphism><fixed-parameter-tractable>
Open problems related to Graph isomorphism
Kumar
# Open problems related to Graph isomorphism

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

Presently I am doing literature survey on Graph isomorphism (GI) problem.

I would like to know some open questions related to the following

1. What are the graph parameters for which fixed parameter tractability of GI is an open problem.
2. What are the graph parameters, by fixing them polynomial time solvability of GI is not known.
3. Complexity of GI when restricted to many graph classes is equivalent to general GI (GI-Completeness). What are the graph classes for which GI-completeness is not known.

Thank you.

**Tags:** graph-isomorphism, fixed-parameter-tractable
> **Comments:**
> **username_1**: I'm not aware of any definitive answers to your questions.  If you find partial answers (which might require looking at dozens of published research papers), then it would be great if you could link to the summary you create, or give its highlights, as an answer.  
> **username_2**: re 3, question. for the many graph classes $X$ proven GI complete, is the question "are not-$X$ graphs GI complete?" open? does that make any sense? related [cs.se question](http://cs.stackexchange.com/questions/19160/graph-isomorphism-completeness-of-class-x-and-not-x)  

---

## 4 answers

### Answer by username_6 on 2013-12-20. Score: 13 | Accepted answer

For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open.

* pathwidth / treewidth (see [2], has been asked [here](https://cstheory.stackexchange.com/questions/19699/fpt-algorithm-for-partial-k-tree-isomorphism)), maybe solved: <http://arxiv.org/abs/1404.0818>
* cutwidth / bandwidth [1]
* treewidth-k vertex deletion set size (feedback vertex set number in [7])
* tree / path distance width (see [1]), connected tree distance width (see [3], however you can get quite close to the last one, see section 6.4. of my [diploma thesis](http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/mitarbeiter/fuhlbrueck/diplomarbeit-fuhlbrueck-rev1.pdf) ) : solved by Y. Otachi and P. Schweitzer : <http://arxiv.org/abs/1403.7238>
* clique-width / shrub-depth (or SC-depth) (see [[4](http://www.fi.muni.cz/~hlineny/res-en.html#recent)])
* maximum degree [5]
* genus [6] / crossing number [8]

Note that there is active ongoing research for some them.

[1] : K. Yamazaki, H. L. Bodlaender, B. de Fluiter and D. M. Thilikos. Isomorphism
for graphs of bounded distance width. Algorithmica 24.2 (1999)

[2] : H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chro-
matic index on partialk-trees. Journal of Algorithms 11.4 (1990)

[3] : Y. Otachi. Isomorphism for Graphs of Bounded Connected-Path-Distance-
Width. Algorithms and Computation. Springer, 2012

[[4](http://www.fi.muni.cz/~hlineny/res-en.html#recent)] : <http://www.fi.muni.cz/~hlineny/res-en.html#recent>

[5] : L. Babai and E. M. Luks. Canonical labeling of graphs. STOC '83.

[6] : I. S. Filotti and J. N. Mayer. A polynomial-time algorithm for determining the
isomorphism of graphs of fixed genus. STOC '80 /
G. Miller. Isomorphism testing for graphs of bounded genus. STOC '80

[7] : S. Kratsch and P. Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. SWAT 2010

[8] : <http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf>

> **Comments:**
> **username_7**: In terms of active relevant research in this area, there are a few additional references I would suggest. [A] This paper [here](http://people.csail.mit.edu/adam/Papers/tree-depth.pdf) from IPEC 2012, shows graph isomorphism is fixed-parameter tractable in the tree-_depth_ of a graph, which is a parameter related to tree-width. [B] This paper [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.6517&rep=rep1&type=pdf) shows that graph isomorphism for chordal graphs is FPT in the size of the largest simplicial component.  
> **username_7**: One more reference is [this paper](http://dl.acm.org/citation.cfm?doid=1374376.1374443) from STOC '08, which comes _very close_ to showing that graph isomorphism is FPT in the genus of a graph. More specifically, they show that graph isomorphism is in linear time when restricted to the class of graphs which admit a polyhedral embedding in a fixed surface $S$of genus $g$.  
> **username_0**: @Adam Bouland  Is there any FPT or Polynomial time algorithms for Graph isomorphism for bounded band width.  
> **username_8**: @Kumar It is poly-time solvable but not known to be FPT. See Yamazaki et al. [1] in the answer of frafl.  

---

### Answer by username_3 on 2013-12-25. Score: 13

For the second question: Fixing rank-width (equivalently, fixing clique-width), polynomial time solvability of GI is not known. Recently, [Mamadou Kanté](https://cstheory.stackexchange.com/users/4854/m-kante) posed an open question [if the graph isomorphism problem can be solved in polynomial time for graphs of bounded linear rank-width](http://www.lsi.upc.edu/~sedthilk/grow/Open_Problems_GROW_2013.pdf).


---

### Answer by username_5 on 2013-12-20. Score: 5

For the third question: The survey paper of Brandstadt, Le, and Spinrad, Graph Classes: A Survey, SIAM, 1999, contains several graph classes for which GI-completeness is not known. One such class is [trapezoid graphs](https://dspace.jaist.ac.jp/dspace/bitstream/10119/4896/1/C3941.pdf). Another class is circular arc graphs which is mentioned as open problem in the introduction of the paper, [Tractabilities and Intractabilities on Geometric Intersection Graphs](http://www.mdpi.com/1999-4893/6/1/60) by Uehara.

**EDIT**: The Graph Isomorphism problem for tournaments is not known to be GI-complete.


---

### Answer by username_4 on 2014-10-08. Score: 4

For the third question you can also take a look to [www.graphclasses.org](http://www.graphclasses.org) : launch the java applet and select Problems -> Boundary/Open problems -> Graph isomorphism.

You'll get a huge list of graph classes for which the GI problem status is *unknown to ISGCI* (it could be in P or GI-complete); probably for some of them the GI-completeness has been already settled, or simply they have not been studied, yet; but it is a good starting point to search for papers about them.


---

