Restricted optimal pebbling is NP-hard

Abstract

Consider a distribution of pebbles on a graph. A pebbling move removes two pebbles from a vertex and place one at an adjacent vertex. A vertex is reachable under a pebble distribution if it has a pebble after the application of a sequence of pebbling moves. A pebble distribution is solvable if each vertex is reachable under it. The size of a pebble distribution is the total number of pebbles. The optimal pebbling number ${\pi }^{\ast }(G)$ is the size of the smallest solvable distribution. A $t$-restricted pebble distribution places at most $t$ pebbles at each vertex. The $t$-restricted optimal pebbling number ${\pi }_t^{\ast }(G)$ is the size of the smallest solvable $t$-restricted pebble distribution. We show that deciding whether ${\pi }_2^{\ast }(G)\le k$ is NP-complete. We prove that ${\pi }_t^{\ast }(G)={\pi }^{\ast }(G)$ if $\delta (G)\ge \frac{2|V(G)|}{3}-1$ and we show infinitely many graphs which satisfies $\delta (H)\approx \frac{1}{2}|V(H)|$ but ${\pi }_t^{\ast }(H)\ne {\pi }^{\ast }(H)$, where $\delta$ denotes the minimum degree.