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.

$\endgroup$
  • 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 Dec 20 '13 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 Dec 20 '13 at 17:08
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

$\endgroup$
  • 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 Dec 20 '13 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 Dec 20 '13 at 17:07
  • $\begingroup$ @Adam Bouland Is there any FPT or Polynomial time algorithms for Graph isomorphism for bounded band width. $\endgroup$ – Kumar Dec 24 '13 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 Dec 26 '13 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.

$\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.

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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