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

        On the parameterized complexity of the Perfect Phylogeny problem

        Thumbnail
        View/Open
        perfectphylogeny-xalp.pdf (483.7Kb)
        Publication date
        2023
        Author
        Vlas, Jorke de
        Metadata
        Show full item record
        Summary
        This thesis categorizes the parameterized complexity of the algorithmic problems Perfect Phylogeny and Triangulating Colored Graphs. We show that they are complete for the parameterized complexity class XALP using a reduction from Tree-chained Multicolor Independent Set and a proof of membership. We introduce the problem Triangulating Multicolored Graphs as a stepping stone and prove XALP-completeness for this problem as well. We also show that, assuming the Exponential Time Hypothesis, there exists no algorithm that solves any of these problems in time f(k)n^{o(k)}, where n is the input size, k the parameter, and f any computable function.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/44574
        Collections
        • Theses
        Utrecht university logo