Fixed-parameter algorithms for graph constraint logic

DOI10.1016/J.TCS.2023.113863MaRDI QIDQ6041672zbMATH OpenOpenAlexFDO

Authors Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki

Publication date 12 May 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10385

zbMATH Keywords

fixed-parameter algorithmscombinatorial reconfigurationnon-deterministic constraint logic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 PSPACExspace 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 extsc{and/or}xspace 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 extsc{and}xspace or extsc{or}xspace vertices of an extsc{and/or}xspace 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 extsc{and}xspace 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.

Recommendations

• Fixed-parameter algorithms for graph constraint logic
• Parameterized complexity of graph constraint logic
• scientific article; zbMATH DE number 2086639
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of independent set reconfigurability problems
• Diameter of colorings under Kempe changes
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized algorithms
• Parameterized complexity of graph constraint logic
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Proof equivalence in MLL is PSPACE-complete
• Reconfiguring undirected paths
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• The complexity of change
• The complexity of dominating set reconfiguration
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

Cited in

(2)

• scientific article; zbMATH DE number 1523001 (Why is no real title available?)
• Fixed-parameter algorithms for graph constraint logic

This page was built for publication: Fixed-parameter algorithms for graph constraint logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041672)