Nos é dado um gráfico acíclico direcionado com um número associado a cada vértice ( ) e um número alvo .g : V → N T ∈ N
O problema de soma de subconjuntos do DAG (pode existir com um nome diferente, uma referência será ótima) pergunta se existem vértices , de modo que e é um caminho em .Σ v i g ( v i ) = T v 1 → . . → v k G
Esse problema é trivialmente NP-Completo, pois o gráfico transitivo completo gera o problema clássico de soma de subconjuntos.
Um algoritmo de aproximação para o problema de soma de subconjuntos do DAG é um algoritmo com as seguintes propriedades:
- Se existir um caminho com a soma T, o algoritmo retornará TRUE.
- Se não houver um caminho que resuma um número entre e para alguns c \ in (0,1) , o algoritmo retornará FALSE.T c ∈ ( 0 , 1 )
- Se houver um caminho que se soma a um número entre e , o algoritmo pode gerar qualquer resposta.
Sabe-se que a soma do subconjunto é aproximada em tempo polinomial para todos os .
O mesmo vale para DAG-Subset-Sum?