Мы дали направленный ациклический граф с номером , связанным с каждой вершиной ( г : V → N ), и целевым числом Т ∈ N .
Проблема DAG подмножества суммы (может существовать под другим именем, ссылка будет большой) спрашивает , есть ли вершины , таким образом, что Σ v я г ( v я ) = Т и v 1 → . , → v K представляет собой путь в G .
Эта задача тривиально NP-полная, так как полный транзитивный граф дает классическую задачу о сумме подмножеств.
Алгоритм аппроксимации для задачи о сумме подмножеств DAG представляет собой алгоритм со следующими свойствами:
- Если существует путь с суммой T, алгоритм возвращает TRUE.
- Если для некоторого c ∈ ( 0 , 1 ) нет пути, суммирующего до числа между и T , алгоритм возвращает FALSE.
- Если есть путь, суммирующий число между и T , алгоритм может вывести любой ответ.
Известно, что сумма подмножеств аппроксимируется за полиномиальное время для всех .
То же самое относится и к DAG-Subset-Sum?