2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your response, that makes me clearer now, but I have question about the reduction. What if we have a Ham cycle such s-o-t, t -s, and by choosing any node say s, we set s to 2, o and t to 1, then remove node s will increase either o or t to 2. Now , say o has 2 token and what if we remove o, then it added 1 token back to s. Then we left s and t both have 1 token. Do we have to get rid of this or we can assume it always add to an none 0 token? $\endgroup$ – hh vh Dec 8 '19 at 3:51
  • $\begingroup$ It seems we have to do reduction from directed ham cycle to directed graph last token and to undirected graph last token? $\endgroup$ – hh vh Dec 8 '19 at 7:19
  • 1
    $\begingroup$ The graph you described is a yes instance for the last token you only have to choose the next token cleverly (that is the point of the problem), just as in ham cycle you have to choose the next vertex cleverly. That means it is enough to find one good seq. of ops, for example Take s and put in t t take t and put in o take o and put ins s. However, in both problems there is no efficient algorithm to make a clever choice since we just proved last token is also Np hard (unless P=NP) $\endgroup$ – narek Bojikian Dec 8 '19 at 10:56
  • $\begingroup$ I'm stuck on writing the proof formally, as you mentioned I only have to choose the next toke cleverly, should I argue this at the step of my problem has solution if and only if Ham cycle has solution? But it also sounds like I'm proving directed ham cycle to directed graph last token. $\endgroup$ – hh vh Dec 8 '19 at 17:38
  • $\begingroup$ I change the answer a bit and added an answer. Sorry I wrote it in hurry at first and only thought out the main idea. $\endgroup$ – narek Bojikian Dec 8 '19 at 22:44
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.