Problem z kamykami

Pebbling to gra w pasjansa rozgrywana na niekierowanym grafie , gdzie każdy wierzchołek ma zero lub więcej kamyków. Pojedynczy ruch kamyka polega na usunięciu dwóch kamyków z wierzchołka v i dodaniu jednego kamyka do dowolnego sąsiada v . (Oczywiście, wierzchołek v musi mieć co najmniej dwa kamyki przed ruchem). Problem PebbleDestruction pyta, biorąc pod uwagę wykres G = ( V ; E ) i liczbę kamyków p ( v ) dla każdego wierzchołka v , czy istnieje sekwencja ruchów kamieni, które usuwają wszystkie kamienie oprócz jednego. Udowodnij, że PebbleDestruction jest NP-kompletny.$G$$v$$v$$G = ( V; E )$$p ( v )$$v$

Po pierwsze, pokazuję, że jest w NP, ponieważ mogę zweryfikować rozwiązanie w czasie wielomianowym, śledząc liczbę kamyków z tylko jednego kamyka.

Następnie, jakie są pomysły, na podstawie których problemów można użyć jako podstawy skrócenia czasu wielomianowego?

Czy coś w stylu pokrycia wierzchołków działałoby? A może okładka wierzchołka o różnych rozmiarach?

Jeśli tak, to jak poradzi sobie z różną liczbą kamyków w każdym ruchu?

Dziękuję Ci.

Od: 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$