TY - GEN

T1 - Fixed-parameter algorithms for graph constraint logic

AU - Hatanaka, Tatsuhiko

AU - Hommelsheim, Felix

AU - Ito, Takehiro

AU - Kobayashi, Yusuke

AU - Mühlenthaler, Moritz

AU - Suzuki, Akira

N1 - Funding Information:
Yusuke Kobayashi: Partially supported by JSPS KAKENHI Grant Numbers 17K19960, 18H05291, and JP20K11692, Japan. Akira Suzuki: Partially supported by JSPS KAKENHI Grant Numbers JP18H04091 and JP20K11666, Japan.
Funding Information:
Funding Tatsuhiko Hatanaka: Partially supported by JSPS KAKENHI Grant Number JP16J02175, Japan. Takehiro Ito: Partially supported by JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan.
Publisher Copyright:
© Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki;

PY - 2020/12

Y1 - 2020/12

N2 - 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.

AB - 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.

KW - Combinatorial Reconfiguration

KW - Fixed Parameter Tractability

KW - Nondeterministic Constraint Logic

UR - http://www.scopus.com/inward/record.url?scp=85101467653&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85101467653&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2020.15

DO - 10.4230/LIPIcs.IPEC.2020.15

M3 - Conference contribution

AN - SCOPUS:85101467653

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 15th International Symposium on Parameterized and Exact Computation, IPEC 2020

A2 - Cao, Yixin

A2 - Pilipczuk, Marcin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 15th International Symposium on Parameterized and Exact Computation, IPEC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -