Pebbling Problem

Question

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

Answer 1

Suppose in a graph $G$ there is one pebble on each vertex except one vertex $v$ with $p(v) = 2$, then above pebbling problem has solution on $G \space iff \space G$ has a Hamiltonian circuit. It's easy to check if there is a Hamiltonian circuit, then there is a solution for pebbling on $G$. On the other hand, in any solution to the pebbling, we should start from vertex $v$. Suppose that we visit some vertex $u$ twice such that this $u$ is the first vertex which visited twice in $G$ by pebbling algorithm, then we have a loop which starts from $u$ and ends in $u$ and finally because $u$ is the first for making loop then we have $p(u) = 1$ so we cannot continue pebbling algorithm. Indeed if the algorithm has a solution then we have $u=v$ which means we found a Hamiltonian circuit which starts in $v$.