Fixed-Parameter Algorithms for Graph Constraint Logic

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



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.15.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Tatsuhiko Hatanaka
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Felix Hommelsheim
  • Fakultät für Mathematik, TU Dortmund University, Germany
Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yusuke Kobayashi
  • Research Institute for Mathematical Sciences, Kyoto University, Japan
Moritz Mühlenthaler
  • Laboratoire G-SCOP, Grenoble INP, Université Grenoble Alpes, France
Akira Suzuki
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan

Cite AsGet BibTex

Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki. Fixed-Parameter Algorithms for Graph Constraint Logic. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.15

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Graph algorithms
Keywords
  • Combinatorial Reconfiguration
  • Nondeterministic Constraint Logic
  • Fixed Parameter Tractability

Metrics

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

References

  1. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Diameter of colorings under kempe changes. In Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings, pages 52-64, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_5.
  2. Erik D Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, and Yushi Uno. Reconfiguring undirected paths. In Workshop on Algorithms and Data Structures, pages 353-365. Springer, 2019. Google Scholar
  3. 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-2):895-911, 2002. Google Scholar
  4. Arash Haddadan, Takehiro Ito, Amer E Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, and Youcef Tebbal. The complexity of dominating set reconfiguration. Theoretical Computer Science, 651:37-49, 2016. Google Scholar
  5. Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Complexity of reconfiguration problems for constraint satisfaction. CoRR, abs/1812.10629, 2018. URL: http://arxiv.org/abs/1812.10629.
  6. Weihua He, Ziwen Liu, and Chao Yang. Snowman is pspace-complete. Theoretical Computer Science, 677:31-40, 2017. 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-2):72-96, 2005. URL: https://doi.org/10.1016/j.tcs.2005.05.008.
  8. Hendrik Jan Hoogeboom, Walter A Kosters, Jan N van Rijn, and Jonathan K Vis. Acyclic constraint logic and games. ICGA Journal, 37(1):3-16, 2014. Google Scholar
  9. Robin Houston and Willem Heijltjes. Proof equivalence in MLL is PSPACE-complete. Logical Methods in Computer Science, 12, 2016. Google Scholar
  10. 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. Theoretical Computer Science, 412(12–14):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
  11. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theoretical computer science, 439:9-15, 2012. Google Scholar
  12. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. Google Scholar
  13. Alexander Schrijver. Combinatorial Optimization - Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics. Springer Berlin Heidelberg, 2003. Google Scholar
  14. Jan van den Heuvel. The complexity of change. In Simon R Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, volume 409. London Mathematical Society Lectures Note Series, 2013. Google Scholar
  15. Tom C van der Zanden. Parameterized complexity of graph constraint logic. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  16. Tom C van der Zanden and Hans L Bodlaender. PSPACE-completeness of Bloxorz and of games with 2-buttons. In International Conference on Algorithms and Complexity, pages 403-415. Springer, 2015. 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