DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.103

Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth

Authors: Daniel Wiebking

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

We extend Babai’s quasipolynomial-time graph isomorphism test (STOC 2016) and develop a quasipolynomial-time algorithm for the multiple-coset isomorphism problem. The algorithm for the multiple-coset isomorphism problem allows to exploit graph decompositions of the given input graphs within Babai’s group-theoretic framework. We use it to develop a graph isomorphism test that runs in time n^polylog(k) where n is the number of vertices and k is the minimum treewidth of the given graphs and polylog(k) is some polynomial in log(k). Our result generalizes Babai’s quasipolynomial-time graph isomorphism test.

Cite as

Daniel Wiebking. Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 103:1-103:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wiebking:LIPIcs.ICALP.2020.103,
  author =	{Wiebking, Daniel},
  title =	{{Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{103:1--103:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.103},
  URN =		{urn:nbn:de:0030-drops-125106},
  doi =		{10.4230/LIPIcs.ICALP.2020.103},
  annote =	{Keywords: Graph isomorphism, canonization, treewidth, hypergraphs}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.67

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Authors: Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.

Cite as

Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An Improved Isomorphism Test for Bounded-Tree-Width Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.ICALP.2018.67,
  author =	{Grohe, Martin and Neuen, Daniel and Schweitzer, Pascal and Wiebking, Daniel},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.67},
  URN =		{urn:nbn:de:0030-drops-90714},
  doi =		{10.4230/LIPIcs.ICALP.2018.67},
  annote =	{Keywords: graph isomorphism, graph canonization, tree width, decompositions}
}

Search Results

Documents authored by Wiebking, Daniel

Graph Isomorphism in Quasipolynomial Time Parameterized by Treewidth

Abstract

Cite as

An Improved Isomorphism Test for Bounded-Tree-Width Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message