Czy suma podzbioru DAG jest przybliżona?

Dana jest skierowany acykliczny wykres o numer przypisany do każdego wierzchołka ( g : V → N ), i docelową liczbą T ∈ N .$G=(V,E)$$g:V\to \mathbb{N}$$T\in \mathbb{N}$

Problem sumy podzbioru DAG (może występować pod inną nazwą, odniesienie będzie wielki) pyta, czy istnieją wierzchołki , tak że Σ V I g ( V I ) = T , i V 1 → . . → v k jest ścieżka w G .$v_1,v_2,...,v_k$$\Sigma_{v_i}g(v_i) = T$$v_1\to..\to v_k$$G$

Ten problem jest trywialnie NP-Complete, ponieważ pełny wykres przechodni daje klasyczny problem sumy podzbiorów.

Algorytm aproksymacyjny dla problemu sumy podzbiorów DAG jest algorytmem o następujących właściwościach:

1. Jeśli istnieje ścieżka z sumą T, algorytm zwraca PRAWDA.
2. Jeśli nie ma ścieżki sumującej się do liczby pomiędzy i T dla niektórych c ∈ ( 0 , 1 ) , algorytm zwraca FALSE.$(1 − c)T$$T$$c\in (0,1)$
3. Jeśli istnieje ścieżka sumująca się do liczby między i T , algorytm może wygenerować dowolną odpowiedź.$(1 − c)T$$T$

Suma podzbiorów jest znana jako przybliżona w czasie wielomianowym dla wszystkich .$c>0$

Czy to samo dotyczy DAG-Subset-Sum?

$v_i$$L_i$$v_i$$L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in prec(i)} L_j\}$$L_i$$O(Km)$$K$$m$

Myślę, że standardowe skalowanie i zaokrąglanie można również zastosować do uzyskania FPTAS.