Computing treewidth on the GPU

DOI10.4230/LIPICS.IPEC.2017.29zbMATH Open1443.68213arXiv1709.09990OpenAlexW2760148299MaRDI QIDQ5111889FDOQ5111889

Hans L. Bodlaender, Tom C. van der Zanden

Publication date: 27 May 2020

Abstract: 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^{*}(2^n)$-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 $77imes$) compared to running the same algorithm on the CPU.

Full work available at URL: https://arxiv.org/abs/1709.09990

Recommendations

• On Exact Algorithms for Treewidth
• On exact algorithms for treewidth
• scientific article; zbMATH DE number 1107730
• SOFSEM 2005: Theory and Practice of Computer Science
• Parallel algorithms with optimal speedup for bounded treewidth

zbMATH Keywords

treewidthexact algorithmsgraph algorithmsGPGPUGPUalgorithm engineering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• On exact algorithms for treewidth
• A Dynamic Programming Approach to Sequencing Problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Parameterized Algorithms
• Space/time trade-offs in hash coding with allowable errors
• Less Hashing, Same Performance: Building a Better Bloom Filter
• Treewidth computations. II. Lower bounds
• Safe separators for treewidth
• Principles and Practice of Constraint Programming – CP 2004
• Title not available (Why is that?)
• Positive-instance driven dynamic programming for treewidth
• Computing treewidth on the GPU

Cited In (4)

• Computing treewidth on the GPU
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• CUDA
• ComputeTW
• BZTreewidth
• LibTW
• SMHasher
• GPGPU-Treewidth
• GitHub

This page was built for publication: Computing treewidth on the GPU

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111889)