Restricted optimal pebbling is NP-hard

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 π∗(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 πt∗(G) is the size of the smallest solvable t-restricted pebble distribution. We show that deciding whether π2∗(G)≤k is NP-complete. We prove that πt∗(G)=π∗(G) if δ(G)≥[Formula presented]−1 and we show infinitely many graphs which satisfies δ(H)≈[Formula presented]|V(H)| but πt∗(H)≠π∗(H), where δ denotes the minimum degree. © 2024 The Author