18
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Dec 20, 2013 at 13:29
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Dec 20, 2013 at 17:08

4 Answers 4

Reset to default
13
$\begingroup$

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), 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 ) : solved by Y. Otachi and P. Schweitzer : http://arxiv.org/abs/1403.7238
  • clique-width / shrub-depth (or SC-depth) (see [4])
  • 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

[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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ In terms of active relevant research in this area, there are a few additional references I would suggest. [A] This paper here 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 shows that graph isomorphism for chordal graphs is FPT in the size of the largest simplicial component. $\endgroup$
    – Adam Bouland
    Commented Dec 20, 2013 at 16:48
  • 3
    $\begingroup$ One more reference is this paper 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$. $\endgroup$
    – Adam Bouland
    Commented Dec 20, 2013 at 17:07
  • $\begingroup$ @Adam Bouland Is there any FPT or Polynomial time algorithms for Graph isomorphism for bounded band width. $\endgroup$
    – Kumar
    Commented Dec 24, 2013 at 5:24
  • 1
    $\begingroup$ @Kumar It is poly-time solvable but not known to be FPT. See Yamazaki et al. [1] in the answer of frafl. $\endgroup$
    – Yota Otachi
    Commented Dec 26, 2013 at 13:53
13
$\begingroup$

For the second question: Fixing rank-width (equivalently, fixing clique-width), polynomial time solvability of GI is not known. Recently, Mamadou Kanté posed an open question if the graph isomorphism problem can be solved in polynomial time for graphs of bounded linear rank-width.

Improve this answer
$\endgroup$
5
$\begingroup$

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. 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 by Uehara.

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

Improve this answer
$\endgroup$
4
$\begingroup$

For the third question you can also take a look to 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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