Back to search

University of Leeds

Parameterized complexity in graph theory, logic and machine learning

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Leeds
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rychlicki, Mateusz Karol
Advisors dc:contributor.advisor
  • Ordyniak, Sebastian
  • Muller, Haiko
ORCID person:identifier.orcid

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Dc Identifier Grantnumber
EP/V00252X/1

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Rychlicki, Mateusz Karol. Parameterized complexity in graph theory, logic and machine learning. doctoral thesis, University of Leeds, 2026.