Pebbling is a solitaire game played on an undirected graph $G$ , where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex $v$ and adding one pebble to an arbitrary neighbor of $v$ . (Obviously, the vertex v must have at least two pebbles before the move.) The PebbleDestruction problem asks, given a graph $G = ( V; E )$ and a pebble count $p ( v )$ for each vertex $v$ , whether there is a sequence of pebbling moves that removes all but one pebble. Prove that PebbleDestruction is NP-complete.

First I want to show that it is in NP - I assume we can do this by showing we can verify the solution in polynomial time.

However, what are some ideas on which algorithm to show is polynomial time reducible. I imaine something like a vertex cover but not sure how to handle the varying number of pebble on each move, any ideas?

Thank You.

From: http://courses.engr.illinois.edu/cs473/sp2011/hw/disc/disc_14.pdf