Restricted optimal pebbling is NP-hard

Le résumé fourni par la source

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)≥2|V(G)|3−1 and we show infinitely many graphs which satisfies δ(H)≈12|V(H)| but πt∗(H)≠π∗(H), where δ denotes the minimum degree.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.