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 i dodaniu jednego kamyka do dowolnego sąsiada . (Oczywiście, wierzchołek v musi mieć co najmniej dwa kamyki przed ruchem). Problem PebbleDestruction pyta, biorąc pod uwagę wykres i liczbę kamyków dla każdego wierzchołka , 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

algorithms graph-theory np-complete

— TT
źródło

Czy łatwo jest wykazać, że problem dotyczy NP? Czy liczba ruchów nie może być wykładnicza w stosunku do wielkości wejściowej?

— Vinicius dos Santos

@ ViniciusSantos, liczba ruchów nie może być większa niż liczba kamyków (która jest również częścią danych wejściowych).

Ale możemy założyć, że liczba kamyków jest dwójkowa, prawda? W takim przypadku wielkość danych wejściowych jest logarytmiczna w stosunku do liczby kamyków. Nadal uważam, że istnieje krótki certyfikat problemu, ale o ile rozumiem, lista ruchów nie jest jedna.

— Vinicius dos Santos

@ ViniciusdosSantos, być może nie zauważyłeś, że cały wykres jest jako dane wejściowe, z drugiej strony liczba otoczaków dla każdego wierzchołka (p (v)) powinna być ograniczona rozmiarem wykresu, w przeciwnym razie sprawdzając, czy sekwencja ruchów jest ważne lub nie wymaga wykładniczego. I myślę, że słuszne jest przypuszczenie, że liczba kamyków na każdym wierzchołku wynosi co najwyżej n.

Zgadzam się, że jeśli liczba otoczaków na każdym wierzchołku jest wielomianowo ograniczona przez rozmiar wykresu, to jest to trywialnie w NP. Myślę jednak, że to założenie nie jest konieczne, choć bez niego dowód staje się trudniejszy.

— Vinicius dos Santos

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