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

        Parameterized Complexity of Graph Constraint Logic

        Thumbnail
        View/Open
        thesis_zanden.pdf (394.0Kb)
        Publication date
        2015
        Author
        Zanden, T.C. van der
        Metadata
        Show full item record
        Summary
        Graph constraint logic is a framework introduced by Hearn and Demaine, which provides several problems that are often a convenient starting point for reductions. We study the parameterized complexity of Constraint Graph Satisfiability and both bounded and unbounded versions of Nondeterministic Constraint Logic (NCL) with respect to solution length, treewidth and maximum degree of the underlying constraint graph as parameters. As a main result we show that restricted NCL remains PSPACE-complete on graphs of bounded bandwidth, strengthening Hearn and Demaine's framework. This allows us to improve upon existing results obtained by reduction from NCL, and we show that reconfiguration versions of several classical graph problems (including independent set, feedback vertex set and dominating set) are PSPACE-complete on planar graphs of bounded bandwidth.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/20457
        Collections
        • Theses
        Utrecht university logo