Se nos da un dirigido acíclico gráfico con un número asociado con cada vértice ( g : V → N ), y un número de destino T ∈ N .
El problema de la suma DAG subconjunto (podría existir con un nombre diferente, una referencia será grande) pregunta si hay vértices , tal que Σ v i g ( v i ) = T , y v 1 → . . → v k es un camino en G .
Este problema es trivialmente NP-completo, ya que el gráfico transitivo completo produce el problema clásico de suma de subconjuntos.
Un algoritmo de aproximación para el problema de suma de subconjuntos DAG es un algoritmo con las siguientes propiedades:
- Si existe una ruta con suma T, el algoritmo devuelve VERDADERO.
- Si no hay una ruta que sume un número entre y T para alguna c ∈ ( 0 , 1 ) , el algoritmo devuelve FALSO.
- Si hay una ruta que suma un número entre y T , el algoritmo puede generar cualquier respuesta.
Se sabe que la suma de subconjuntos es aproximable en tiempo polinómico para todo .
¿Lo mismo vale para DAG-Subset-Sum?