Parameterized complexity of graph constraint logic
From MaRDI portal
Abstract: 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. 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 and that Rush Hour, generalized to boards, is PSPACE-complete even when is at most a constant.
Recommendations
- scientific article; zbMATH DE number 2086639
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
- Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
- Parameterized complexity of constraint satisfaction problems
Cited in
(34)- The complexity of Snake and undirected NCL variants
- Reconfiguration in bounded bandwidth and tree-depth
- Invitation to combinatorial reconfiguration
- Using contracted solution graphs for solving reconfiguration problems
- Introduction to reconfiguration
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Computational complexity of jumping block puzzles
- Reconfiguration of cliques in a graph
- On the Complexity of Insertion Propagation with Functional Dependency Constraints
- Reconfiguration of Steiner trees in an unweighted graph
- The complexity of (list) edge-coloring reconfiguration problem
- scientific article; zbMATH DE number 2086639 (Why is no real title available?)
- Games, Puzzles and Treewidth
- The Perfect Matching Reconfiguration Problem
- The complexity of dominating set reconfiguration
- Diameter of colorings under Kempe changes
- Fixed-parameter algorithms for graph constraint logic
- Feedback vertex set reconfiguration in planar graphs
- Fixed-parameter algorithms for graph constraint logic
- On the complexity of distance-\(d\) independent set reconfiguration
- Computational complexity of jumping block puzzles
- On the complexity of distance-\(d\) independent set reconfiguration
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- On finding short reconfiguration sequences between independent sets
- Reconfiguring planar perfect matchings via bounded length alternating cycles
- Independent set reconfiguration under bounded-hop token jumping
- Rerouting planar curves and disjoint paths
- The complexity of distance-r dominating set reconfiguration
- Independent set reconfiguration under bounded-hop token jumping
- A survey on the parameterized complexity of reconfiguration problems
- The complexity of distance-\(r\) dominating set reconfiguration
- A simple quadratic kernel for token jumping on surfaces
- The tape reconfiguration problem and its consequences for dominating set reconfiguration
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
This page was built for publication: Parameterized complexity of graph constraint logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363782)
