Deterministic Properties for Algorithm Efficiency: Distances, Separators, and Cliques

Classical worst-case analysis of algorithms derives strong theoretical guarantees by assuming minimal constraints on the problem instance and considering any instance of a given size. Unfortunately, such running time bounds are often pessimistic and do not carry over to practice. For example, many problems appearing in practical applications are NP-hard, which makes the existence of algorithms that efficiently solve every possible instance unlikely. Despite this, practically occurring instances can often be solved efficiently.

Several methods have been developed to resolve this discrepancy between benign real-world instances and pessimistic worst-case bounds, each having individual limitations. Average-case analysis highly depends on the assumed probability distribution and the plausibility of the distribution's connection to real-world instances. Furthermore, average-case analysis only makes statements about the chosen probability distribution and not about individual problem instances. Parameterized analysis requires small, sufficiently powerful, and ideally efficiently computable parameters. For many practically relevant problems at least one of these three criteria fails. ... mehrAdditionally, it can be challenging to express the structure and complexity of practical instances with a single numerical parameter.

In this thesis we propose a complementary approach for the analysis of algorithms using deterministic structural properties, which subsume parameters but extend to richer combinations of parameters and other structural assumptions. We demonstrate the usefulness of this framework through multiple case studies considering different problems and algorithms, across both hard and efficiently solvable settings. We find that deterministic properties are a broadly applicable tool that addresses disadvantages of both average-case and parameterized analysis. Deterministic properties can be more flexible than univariate numerical parameters, while giving more tangible results than average-case analysis. More concretely, we find that our approach is useful to explain empirically observed algorithm efficiency, to develop new algorithms for specific types of instances, and to complement previously established parameterized as well as probabilistic input models. Overall, deterministic properties are a pragmatic approach that offers both theoretical insights and practical algorithmic improvements, thus contributing towards bridging the gap between the theoretical analysis of algorithms and practical algorithm performance.