Document Open Access Logo

Parameterized Complexity of Graph Constraint Logic

Author Tom C. van der Zanden

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.282.pdf
  • Filesize: 482 kB
  • 12 pages

Document Identifiers

Author Details

Tom C. van der Zanden

Cite As Get BibTex

Tom C. van der Zanden. Parameterized Complexity of Graph Constraint Logic. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 282-293, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.282

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.

Subject Classification

Keywords
  • Nondeterministic Constraint Logic
  • Reconfiguration Problems
  • Parameterized Complexity
  • Treewidth
  • Bandwidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1):1-45, 1998. Google Scholar
  2. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: Pspace-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. Google Scholar
  3. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Polynomial-time algorithm for sliding tokens on trees. In Algorithms and Computation, pages 389-400. Springer, 2014. Google Scholar
  4. Gary William Flake and Eric B. Baum. Rush hour is pspace-complete, or "why you should generously tip parking lot attendants". Theoretical Computer Science, 270(1):895-911, 2002. Google Scholar
  5. Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, and Youcef Tebbal. The complexity of dominating set reconfiguration. arXiv preprint arXiv:1503.00833, 2015. Google Scholar
  6. Robert A. Hearn and Erik D. Demaine. The nondeterministic constraint logic model of computation: Reductions and applications. In Automata, Languages and Programming, pages 401-413. Springer, 2002. Google Scholar
  7. Robert A. Hearn and Erik D. Demaine. Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1):72-96, 2005. Google Scholar
  8. Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009. Google Scholar
  9. Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. In Algorithms and Computation, pages 28-39. Springer, 2008. Google Scholar
  10. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical computer science, 439:9-15, 2012. Google Scholar
  11. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Marcin Wrochna. Reconfiguration over tree decompositions. In Parameterized and Exact Computation, pages 246-257. Springer, 2014. Google Scholar
  12. Bala Ravikumar. Peg-solitaire, string rewriting systems and finite automata. In Algorithms and Computation, pages 233-242. Springer, 1997. Google Scholar
  13. Tom C. van der Zanden. Parameterized complexity of graph constraint logic. arXiv preprint:1509.02683, 2015. Google Scholar
  14. Marcin Wrochna. Reconfiguration in bounded bandwidth and treedepth. arXiv preprint arXiv:1405.0847, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact