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,showing 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 algorithm to use showing it is polynomial time reducible to.

Would something like a vertex cover work? 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

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

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 want to show that it is in NP - I assume we can do this by showing we can verify the solution in polynomial time.

However, what are some ideas on which algorithm to show is polynomial time reducible. I imaine something like a vertex cover but not sure how to handle the varying number of pebble on each move, any ideas?

Thank You.

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

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,showing 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 algorithm to use showing it is polynomial time reducible to.

Would something like a vertex cover work? 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