License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.15
URN: urn:nbn:de:0030-drops-133182
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13318/
Go to the corresponding LIPIcs Volume Portal


Hatanaka, Tatsuhiko ; Hommelsheim, Felix ; Ito, Takehiro ; Kobayashi, Yusuke ; M├╝hlenthaler, Moritz ; Suzuki, Akira

Fixed-Parameter Algorithms for Graph Constraint Logic

pdf-format:
LIPIcs-IPEC-2020-15.pdf (0.6 MB)


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.

BibTeX - Entry

@InProceedings{hatanaka_et_al:LIPIcs:2020:13318,
  author =	{Tatsuhiko Hatanaka and Felix Hommelsheim and Takehiro Ito and Yusuke Kobayashi and Moritz M{\"u}hlenthaler and Akira Suzuki},
  title =	{{Fixed-Parameter Algorithms for Graph Constraint Logic}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13318},
  URN =		{urn:nbn:de:0030-drops-133182},
  doi =		{10.4230/LIPIcs.IPEC.2020.15},
  annote =	{Keywords: Combinatorial Reconfiguration, Nondeterministic Constraint Logic, Fixed Parameter Tractability}
}

Keywords: Combinatorial Reconfiguration, Nondeterministic Constraint Logic, Fixed Parameter Tractability
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI