On the complexity of enumerating solution parts

In an increasingly digitalized world, where interactions with IT systems are ubiquitous, minimizing waiting times caused by computations is essential. From the perspective of algorithm engineering, this implies a need for efficient algorithms that deliver solutions quickly. However, there are barriers to how quickly an algorithm can finish its work, rooted in the inherent complexity of the computational task at hand. This thesis explores an approach to circumvent waiting time caused by such barriers: Designing algorithms that emit meaningful parts of their final solution incrementally during execution. These algorithms can provide actionable progress to the recipient of the output, whether human or machine, enabling earlier interaction or continued data processing long before completion. We introduce a general framework for formalizing this approach as enumerating solution parts. Our model builds on concepts from enumeration complexity and characterizes the complexity of problems in terms of preprocessing time (to emit the first solution part) and delay (the worst-case time between consecutive outputs). For a selection of classical computational problems – including computing shortest distances, finding spanning trees, and job scheduling – we identify possible tradeoffs between preprocessing and delay. We adapt well-known algorithms to the enumeration setting to improve performance under our model and establish upper bounds, often exploiting easy-to-compute solution parts to amortize the computational effort for others. With adversary arguments and reductions, we prove lower bounds on preprocessing and/or delay, several of which are unconditional and match the presented upper bounds. For graph problems, these bounds are typically due to densely connected subgraphs, with the maximum degree often dominating the complexity. This thesis primarily focuses on the theoretical analysis of the presented problems and algorithms. However, because enumerating solution parts can introduce complexity that asymptotic analysis may not reveal, we complement our theoretical results with an experimental evaluation of our enumeration strategies on both generated and real-world data. The experiments show that the asymptotic improvements carry over into practice and that our techniques do, indeed, reduce waiting times.