M.Sc. Janne H. Korhonen will defend his doctoral thesis Graph and Hypergraph Decompositions for Exact Algorithms on Thursday 16th of January 2014 at 12 o'clock in the Arppeanum Building, Snellmaninkatu 3, Main Lecture Hall. His opponent is Professor Dieter Kratsch (University of Lorraine, France)  and custos Professor Esko Ukkonen (University of Helsinki). The defense will be held in English.

Graph and Hypergraph Decompositions for Exact Algorithms

This thesis studies exact exponential and fixed-parameter algorithms for hard graph and hypergraph problems. Specifically, we study two techniques that can be used in the development of such algorithms: (i) combinatorial decompositions of both the input instance and the solution, and (ii) evaluation of multilinear forms over semirings. 

In the first part of the thesis we develop new algorithms for graph and hypergraph problems based on techniques (i) and (ii). While these techniques are independently both useful, the work presented in this part is largely characterised by their joint application. That is, combining results from different pieces of the decompositions often takes the from of multilinear form evaluation task, and on the other hand, decompositions offer the basic structure for dynamic-programming-style algorithms for the evaluation of multilinear forms.

As main positive results of the first part, we give algorithms for three different problem families. First, we give a fast evaluation algorithm for linear forms defined by a disjointness matrix of small sets. This can be applied to obtain faster algorithms for counting maximum-weight objects of small size, such as k-paths in graphs. Second, we give a general framework for exponential-time algorithms for finding maximum-weight subgraphs of bounded tree-width, based on the theory of tree decompositions. Besides basic combinatorial problems, this framework has applications in learning Bayesian network structures. Third, we give a fixed-parameter algorithm for finding unbalanced vertex cuts, that is, vertex cuts that separate a small number of vertices from the rest of the graph.

In the second part of the thesis we consider aspects of the complexity theory of linear forms over semirings, in order to better understand technique (ii). Specifically, we study how the presence of different algebraic catalysts in the ground semiring affects the complexity. As the main result, we show that there are linear forms that are easy to compute over semirings with idempotent addition, but difficult to compute over rings, unless the strong exponential time hypothesis fails.

Availability of the dissertation

An electronic version of the doctoral dissertation is available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-952-10-9639-6.

Printed copies are available on request from Janne H. Korhonen: +358 9 191 51177 or janne.h.korhonen@helsinki.fi.