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

  • 1
    $\begingroup$ Is it that simple to show that the problem is in NP? Can't the number of moves be exponential on the input size? $\endgroup$ Commented May 5, 2013 at 16:12
  • $\begingroup$ @ViniciusSantos, number of moves cannot be bigger than the number of pebbles (which is also part of the input). $\endgroup$
    – user742
    Commented May 5, 2013 at 20:38
  • 1
    $\begingroup$ But we can assume that the number of pebbles is in binary, right? In this case, the size of the input is logarithmic on the number of pebbles. I still think there is a short certificate for the problem but, as far as I understand, the list of moves is not one. $\endgroup$ Commented May 6, 2013 at 3:22
  • $\begingroup$ @ViniciusdosSantos, May be you did not notice that the whole graph is as input, on the other hand number of pebble for each vertex (p(v)) should be bounded by the size of graph, otherwise checking whether a sequence of moves is valid or not needs exponential. And I think is correct to suppose number of pebbles on each vertex is at most n. $\endgroup$
    – user742
    Commented Jul 18, 2013 at 14:28
  • $\begingroup$ I agree that if the number of pebbles on each vertex is polynomially bounded by the the size of the graph than it is trivially in NP. But I think this assumption is not necessary, although without it the proof gets harder. $\endgroup$ Commented Jul 18, 2013 at 17:02

1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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