Computing treewidth on the GPU

Tom C. van der Zanden, Hans L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
30 Downloads (Pure)


We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O∗(2n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77×) compared to running the same algorithm on the CPU.

Original languageEnglish
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-051-4
Publication statusPublished - 1 Feb 2018
Event12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria
Duration: 6 Sep 20178 Sep 2017
Conference number: 12

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)


Conference12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Abbreviated titleIPEC 2017
Internet address


  • Algorithm engineering
  • Exact algorithms
  • GPU
  • Graph algorithms
  • Treewidth


Dive into the research topics of 'Computing treewidth on the GPU'. Together they form a unique fingerprint.

Cite this