View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Analysing flow-like problems parameterised by tree-depth

        Thumbnail
        View/Open
        thesis_final.pdf (762.4Kb)
        Publication date
        2024
        Author
        Jong, Jack de
        Metadata
        Show full item record
        Summary
        In the field of parameterised complexity, there has been a significant amount of research into the parameters treewidth and pathwidth, but not a comparable amount of research into the related tree-depth parameter. In this paper, we try to expand our knowledge about the hardness of a set of ‘flow-like’ graph problems when parameterised by tree-depth, similar to work done in [1] and [2] where the same set of problems was considered for pathwidth and treewidth respectively. We also provide hardness proofs for the class XSLP, which was defined in [3] by Bodlaender et al., and is intended to serve as a ‘natural home’ for problems parameterised by tree-depth, similar to how XALP and XNLP are intended as ‘natural homes’ for problems parameterised by treewidth and foor pathwidth respectively. Furthermore, by showing that a parameterised reduction exists between any two problems in the set of flow-like problems we consider when using the tree-depth parameter, we support a conjecture that this set of problems is in a different complexity class that is distinct from XSLP.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/46106
        Collections
        • Theses
        Utrecht university logo