A Practical Evaluation of Kernelisation Algorithms for the Multicut in Trees Problem

Abstract

In this thesis, we consider the parameterised version of Multicut in Trees. The problem consists of a tree T = (V, E), a set P of pairs of distinct nodes in V called demand pairs, and a non-negative integer k. We want to find a set E' ⊆ E, with |E'| ≤ k, such that there is no path between the two nodes of every demand pair when we remove every edge e ∈ E' from T. The problem is closely related to Vertex Cover. Finding a new or improved algorithm for either problem could yield the same improvement for the other. In this research, we evaluated two kernelisation algorithms for Multicut in Trees. The first is by Guo and Niedermeier and computes a kernel of size O(k^(3k)). The second algorithm is by Bousquet et al. and results in a kernel of size O(k^6). We tested these algorithms on different instances, using various methods to generate the input tree and the set of demand pairs. We introduced some of these methods in this research. This research partially fills a gap in the area of kernelisation algorithms. It is one of the first studies to practically evaluates these algorithms. We aimed to answer five questions. We wondered what instances are easy or difficult to compute a small kernel on for the algorithms, how the kernel size and the running time scale with the size of the instance, and how usable the newly introduced ways to generate demand pairs are. Then, we wanted to know which reduction rules in the algorithms take the most time. Finally, we answered how the two algorithms compare in terms of both kernel size and running time. To measure the running time, we counted the number of operations that the algorithms perform. Instances with a caterpillar tree generally resulted in smaller kernels than instances with a tree based on a Prüfer sequence. The newly introduced Degree3 trees were present in the most challenging instances. The algorithms could easily compute a small kernel on instances with long paths between every demand pair's two nodes or a tiny solution. When the instance contained demand pairs such that the path between the nodes of most pairs is short, the algorithms computed a large kernel on these instances. In most cases, the size of the kernel depended on the size of the instance, and the running time did as well. The first newly introduced demand pair generation method generates demand pairs such that the length of the path between the two nodes in the pair can be influenced. This method resulted in excellent instances and is quite usable. The other newly introduced method generates demand pairs such that the solution of the instance is known beforehand. This method, however, is not very usable in its current state. Each algorithm had one reduction rule that took the majority of the time. This rule was not the same between the two algorithms. The rules were the Dominated Edge, and Disjoint Paths rule, respectively. We also saw that the sizes of the kernels obtained by the two algorithms only differed in a few cases. Both algorithms had instances on which they computed a smaller kernel than the other algorithm. The algorithm by Guo and Niedermeier was in our implementation faster than the algorithm by Bousquet et al.