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.2015.282
URN: urn:nbn:de:0030-drops-55906
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5590/
Go to the corresponding LIPIcs Volume Portal

van der Zanden, Tom C.

Parameterized Complexity of Graph Constraint Logic

pdf-format:
27.pdf (0.5 MB)

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 k*n boards, is PSPACE-complete even when k is at most a constant.

BibTeX - Entry

@InProceedings{vanderzanden:LIPIcs:2015:5590,
  author =	{Tom C. van der Zanden},
  title =	{{Parameterized Complexity of Graph Constraint Logic}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{282--293},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5590},
  URN =		{urn:nbn:de:0030-drops-55906},
  doi =		{10.4230/LIPIcs.IPEC.2015.282},
  annote =	{Keywords: Nondeterministic Constraint Logic, Reconfiguration Problems, Parameterized Complexity, Treewidth, Bandwidth}
}

Keywords: Nondeterministic Constraint Logic, Reconfiguration Problems, Parameterized Complexity, Treewidth, Bandwidth
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

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