License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.67
URN: urn:nbn:de:0030-drops-90714
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9071/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin ; Neuen, Daniel ; Schweitzer, Pascal ; Wiebking, Daniel

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

pdf-format:
LIPIcs-ICALP-2018-67.pdf (0.4 MB)

Abstract

We give a new fpt algorithm testing isomorphism of n-vertex graphs of tree width k in time 2^{k polylog(k)} poly n, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2^{O(k^5 log k)}poly n. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place. We give a second algorithm which, at the price of a slightly worse run time 2^{O(k^2 log k)}poly n, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.

BibTeX - Entry

@InProceedings{grohe_et_al:LIPIcs:2018:9071,
  author =	{Martin Grohe and Daniel Neuen and Pascal Schweitzer and Daniel Wiebking},
  title =	{{An Improved Isomorphism Test for Bounded-Tree-Width Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9071},
  URN =		{urn:nbn:de:0030-drops-90714},
  doi =		{10.4230/LIPIcs.ICALP.2018.67},
  annote =	{Keywords: graph isomorphism, graph canonization, tree width, decompositions}
}

Keywords: graph isomorphism, graph canonization, tree width, decompositions
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI