10
$\begingroup$

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

$\endgroup$
  • 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$ – Vinicius dos Santos May 5 '13 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 May 5 '13 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$ – Vinicius dos Santos May 6 '13 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 Jul 18 '13 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$ – Vinicius dos Santos Jul 18 '13 at 17:02
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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