How to prove LastToken problem is NP-complete

Question

Consider the following game played on a graph $G$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $G$ and an initial number of tokens $t(v) \ge 0$ for each vertex $v$, there is a sequence of moves that results in only one token being left in $G$. Prove that LastToken is NP-complete.

I'm learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it's in NP and choose a NP-complete problem that can be reduced from. I'm stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I'm guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don't see any connection between them so far. How should I start a good approach?

Answer 1

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$.

Claim. The previous reduction is correct. Try to prove it formally as an exercise.

Edit. Here is a brief proof of correctness. We have to prove that the created instance is a yes-instance of your problem, if and only if the given instance is a yes-instance of the Hamiltonian path problem. First, let $G$ be a yes instance of the Hamiltonian path. Let $v_1, \dots v_n$ be a Hamiltonian cycle in the graph. Now we describe a winning strategy for the last-token, where in the step $i$ we take two tokens from the vertex $v_{i-1}$ and add one to the vertex $v_{i}$. It is easy to prove by induction, that in step $i+1$ all vertices $v_0, \dots v_{i-1}$ have no tokens in them, the vertex $v_i$ has two and all vertices $v_{i+1}, \dots v_n$ have exactly one token. In the $n-th$ step we take the two tokens left in $c_n$ and put one token in $v_0$ and we are done. Note that $v_i$ has always a common edge with $v_{i+1}$ since the are consecutive in a Hamiltonian path.

On the other hand, assuming the reduced instance is a yes-instance, we prove that the given graph is Hamiltonian. Since all but one vertex have exactly one token. We have only one choice for the first vertex. In each step we take two tokens from a vertex and add a token to another one. It is easy to prove inductively that in each step all but at most one vertex have at most one token in them. One vertex can have two tokens wich is the only choice for the next step. Using this claim, it is also easy to prove that to vertex can be chosen twice. Hence, if we were able to choose $n+1$ vertices, we must have a permutation of the $n$ vertices with $v_0$ starting in $v_0$ and this permutation must be a Hamiltonian path since we always have an edge between two consecutive choices in the game.

Answer 2

The Above answer works in its entirety to add to it, think of a situation where we have a no instance of the hamiltonian path problem. Then some node must be visited more than once, this collides with the inductive step of our yes instance as we must eventually give a value 1 to a node with 0. we then will have nodes with all 0's and 1's and will not be able to take from any node on the graph we, therefore, will have to claim no on our last token problem.