Computing treewidth on the GPU

DOI10.4230/LIPICS.IPEC.2017.29MaRDI QIDQ5111889zbMATH OpenOpenAlexFDO

Authors Tom C. van der Zanden, Hans L. Bodlaender

Publication date 27 May 2020

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

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)

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^{\ast }(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.

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

Cites work

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

Cited in

(4)

• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Computing treewidth on the GPU
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• scientific article; zbMATH DE number 7378698 (Why is no real title available?)

Describes a project that uses

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)