Parameterized complexity in graph theory, logic and machine learning

This thesis extends the scope of Parameterized Complexity beyond its traditional boundaries, demonstrating its ability to manage computational intractability in diverse settings. While structural parameters like treewidth are typically associated with graph algorithms, we expand their application to solve hard problems in three distinct domains: Graph Drawing, Explainable AI (XAI), and Logic.

First, the thesis addresses the Two-Page Book Embedding problem within the classical domain of Graph Theory. By parameterizing the problem by treewidth, a standard graph property, a single-exponential Fixed-Parameter Tractable (FPT) algorithm has been developed. Exploiting the property that the treewidth of planar graphs is at most the square-root of the number of vertices, this approach yields a deterministic algorithm running in subexponential time. This result is shown to be asymptotically tight under standard complexity assumptions regarding the Exponential Time Hypothesis.

Next, the investigation shifts to Machine Learning, a field where the theoretical foundations for ``interpretability'' remain nascent compared to the volume of practical research. Analysing symbolic models such as Decision Trees, Sets, and Lists, alongside various variants of Binary Decision Diagrams and their ensembles, the work seeks structural properties governing the complexity of generating explanations. The analysis reveals a landscape often dominated by computational intractability, challenging the assumption that simple models are inherently transparent. However, by identifying specific structural parameters, such as explanation size and model width, novel FPT algorithms are established for specific tractable cases.

Finally, the thesis tackles the PSpace-complete Quantified Boolean Formula (QBF) problem. Moving beyond standard graph parameters, this work utilises ``backdoors'', which are sets of variables whose removal yields tractable classes like Quantified 2-CNF. By introducing ``Enhanced Backdoors'', the research bridges the gap between syntactic restrictions and structural graph properties, significantly extending the boundaries of QBF tractability.

Collectively, this body of work illustrates that intractability in Graph Drawing, Machine Learning, and Logic is not absolute, but it is a function of hidden structures that can be exploited through parameterized complexity analysis.