Parallel Algorithms on Tree Decompositions

Abstract

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.