Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-080 | 6th March 2018 12:48

Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games


Authors: Moritz Gobbert
Publication: 25th April 2018 04:06
Downloads: 1340


The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. In addition, the graph has special properties. For instance: Every node can only hold a fixed amount of tokens and the marked token is only allowed to travel once across each edge. We show that the decision question whether the marked token can reach the goal node is NP-complete. For this we construct several gadgets to show a reduction via Directed Hamiltonian cycles. These gadgets can further be used as a framework for complexity analysis of combinatorial puzzles and similar questions. As an example we will show the NP-hardness of Game about Squares and of 2048.

ISSN 1433-8092 | Imprint