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?