Experimental Research and Algorithmic Improvements involving the Graph Parameter Boolean-width

Abstract

In this thesis, we investigate numerous algorithms that make use of boolean decompositions. We provide a new algorithm for computing the representatives of linear decompositions. These representatives are the indices for a table storing partial solutions, which is used by dynamic programming algorithms. These algorithms are parameterized by the width of the boolean decomposition that is used as an input.

We present a new heuristic to compute linear boolean decompositions and experimentally evaluate it by comparing it to existing heuristics. The experimental evaluation shows that significant improvements can be made with respect to running time without increasing the width of the generated decompositions. Moreover, we consider reduction rules in order to reduce the running time needed to generate linear boolean decompositions. However, these reduction rules seem to describe degenerate graph classes that will not occur often in practical settings, meaning that the benefit of reducing vertices will be very marginal.

Boolean decompositions can be used to solve the class of locally checkable vertex subset problems. We evaluate an algorithm for solving these problems, showing that the algorithm is often up to several orders of magnitude faster compared to theoretical worst case bounds.