Алгоритм редукции - Пересчет любой проблемы SGI как суммы подмножеств

Question

Возможно ли преобразовать любую проблему изоморфизма подграфа в проблему суммы подмножеств, чтобы можно было использовать методы динамического программирования, доступные для решения проблемы суммы подмножеств, для решения проблемы SGI?

Answer 1

Да, вы могли бы сделать это, но каждое известное сокращение привело бы к проблеме подмножества с экспоненциально большими числами.

(Кроме того, ваш домашний детектор сломан.)

Answer 2

Я не понимаю, как это можно сделать.Не существует четкого отображения между весами задачи о сумме подмножеств и структурой графа.Единственное отношение между этими двумя проблемами - это подмножество графа и подмножество множества в задаче суммы подмножеств.Алгоритм псевдополимеального (динамического программирования) для подмножества суммы работает с набором цифр и ограниченной суммой - я серьезно сомневаюсь, что есть какой-либо способ кодирования структуры графа в этом формате.Но, учитывая, что это домашнее задание, я могу ошибаться:)