Problème de galets

Le galet est un jeu de solitaire joué sur un graphe non orienté , où chaque sommet a zéro ou plusieurs galets. Un mouvement de caillou unique consiste à retirer deux cailloux d'un sommet v et à ajouter un caillou à un voisin arbitraire de v . (Évidemment, le sommet v doit avoir au moins deux cailloux avant le déplacement.) Le problème PebbleDestruction demande, étant donné un graphique G = ( V ; E ) et un nombre de cailloux p ( v ) pour chaque sommet v , s'il y a une séquence de mouvements de galets qui enlèvent tous les galets sauf un. Prouver que PebbleDestruction est NP-complet.$G$$v$$v$$G = ( V; E )$$p ( v )$$v$

Tout d'abord, je montre qu'il est en NP car je peux vérifier la solution en temps polynomial, en remontant le nombre de cailloux à partir d'un seul caillou.

Ensuite, quelles sont les idées sur les problèmes à utiliser comme base pour une réduction du temps polynomial?

Est-ce que quelque chose comme la couverture vertex fonctionnerait? Ou une couverture vertex de différentes tailles?

Si oui, comment peut-il gérer le nombre variable de cailloux à chaque mouvement?

Merci.

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

$G$$v$$p(v) = 2$$G \space iff \space G$$G$$v$$u$$u$$G$$u$$u$$u$$p(u) = 1$$u=v$$v$