Parallel Algorithms on Tree Decompositions
Summary
Several problems including finding the maximum independent set
and the minimum size dominating set of a graph are NP-hard problems that can be solved in linear time on graphs given with a tree
decomposition whose width is bounded by a constant. So far, about
all work on implementation of these algorithms was restricted to sequential algorithms, running on a CPU. A recent study showed that a
GPU implementation of algorithms running on a path decomposition
of a graph showed a significant speedup when compared to the CPU
implementation.
Both the GPU implementation for maximum independent set and
minimum dominating set show a significant increase in speed on a
subset of all tested tree decompositions, but do have an equal or a
decreased performance on other trees. The tree decomposition the
algorithm is ran on has a large influence on the performance of the
algorithms.