# Finding Optimal Tree Decompositions

 dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta fi dc.contributor University of Helsinki, Faculty of Science en dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten sv dc.contributor.author Korhonen, Tuukka dc.date.issued 2020 dc.identifier.uri URN:NBN:fi:hulib-202006173010 dc.identifier.uri http://hdl.handle.net/10138/316589 dc.description.abstract The task of organizing a given graph into a structure called a tree decomposition is relevant in multiple areas of computer science. In particular, many NP-hard problems can be solved in polynomial time if a suitable tree decomposition of a graph describing the problem instance is given as a part of the input. This motivates the task of finding as good tree decompositions as possible, or ideally, optimal tree decompositions. en This thesis is about finding optimal tree decompositions of graphs with respect to several notions of optimality. Each of the considered notions measures the quality of a tree decomposition in the context of an application. In particular, we consider a total of seven problems that are formulated as finding optimal tree decompositions: treewidth, minimum fill-in, generalized and fractional hypertreewidth, total table size, phylogenetic character compatibility, and treelength. For each of these problems we consider the BT algorithm of Bouchitté and Todinca as the method of finding optimal tree decompositions. The BT algorithm is well-known on the theoretical side, but to our knowledge the first time it was implemented was only recently for the 2nd Parameterized Algorithms and Computational Experiments Challenge (PACE 2017). The author’s implementation of the BT algorithm took the second place in the minimum fill-in track of PACE 2017. In this thesis we review and extend the BT algorithm and our implementation. In particular, we improve the eciency of the algorithm in terms of both theory and practice. We also implement the algorithm for each of the seven problems considered, introducing a novel adaptation of the algorithm for the maximum compatibility problem of phylogenetic characters. Our implementation outperforms alternative state-of-the-art approaches in terms of numbers of test instances solved on well-known benchmarks on minimum fill-in, generalized hypertreewidth, fractional hypertreewidth, total table size, and the maximum compatibility problem of phylogenetic characters. Furthermore, to our understanding the implementation is the first exact approach for the treelength problem. dc.language.iso en dc.publisher Helsingin yliopisto fi dc.publisher University of Helsinki en dc.publisher Helsingfors universitet sv dc.subject tree decompositions dc.subject triangulations dc.subject Bouchitté-Todinca algorithm dc.subject potential maximal cliques dc.title Finding Optimal Tree Decompositions en dc.type.ontasot pro gradu -tutkielmat fi dc.type.ontasot master's thesis en dc.type.ontasot pro gradu-avhandlingar sv dc.subject.discipline Tietojenkäsittelytiede und dct.identifier.urn URN:NBN:fi:hulib-202006173010