Exponential time algorithms: Structures, measures, and bounds

Abstract

This thesis studies exponential time algorithms, more precisely, algorithms exactly solving problems for which no polynomial time algorithm is known and likely to exist. Interested in worst–case upper bounds on the running times, several known techniques to design and analyze such algorithms are surveyed. A detailed presentation of the design and especially the analysis of branching algorithms is given. Then, the branching paradigm is used to design faster algorithms for various problems, including the Feedback Vertex Set problem, #Maximal Independent Sets, Max 2-Sat, Max 2-CSP, and mixed instances of the latter two problems. The analysis of these algorithms heavily relies on problem–specific measures of the instances. These measures capture the structure of the instances, not merely their size. This makes them more appropriate to quantify the progress an algorithm makes in the process of solving a problem for an instance. Upper bounds on mathematical objects are also proved in this thesis. A bound on the maximum number of minimal feedback vertex sets is derived via the same methodology as the one used to upper bound the running time of branching algorithms. For the maximum number of maximal bicliques, a simple reduction is used to bound it in terms of the maximum number of maximal independent sets in a graph. Finally, bounds for the treewidth of a graph are proved using inductive and geometric arguments. Expanding the methodology to design exponential time algorithms, new techniques are presented. Two of them combine treewidth based algorithms with branching or enumeration algorithms. Another one is the well known technique of Iterative Compression, prominent in the design of parameterized algorithms, and adapted here to the design of exponential time algorithms.