> 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 show that it is in NP since I can verify the solution in polynomial time, tracing back the pebble count from just one pebble.

Next, what are some ideas on which problems to use as the basis for a polynomial-time reduction?

Would something like vertex cover work? Or a vertex cover of different sizes? 

If so, how can it handle the varying number of pebbles on each move?

Thank You.



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