Back to Search
Start Over
Fixed-parameter algorithms for graph constraint logic.
- Source :
-
Theoretical Computer Science . May2023, Vol. 959, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures PSPACE and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains PSPACE -complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar and/or graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL , the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of and or or vertices of an and/or constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of and vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing PSPACE. [ABSTRACT FROM AUTHOR]
- Subjects :
- *CONSTRAINT algorithms
*GRAPH algorithms
*LOGIC
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 959
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 163657334
- Full Text :
- https://doi.org/10.1016/j.tcs.2023.113863