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

摘要

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.