Учитывая ДАГ (ориентированный ациклический граф) , с источником S и раковины T . Найдите DAG D ′ с источниками S и приемниками T с минимальным количеством ребер таким образом, чтобы:
Для всех пар существует путь от u до v в D тогда и только тогда, когда существует путь от u до v в D ′ .
Одним из применений этого является представление набора семейства группой DAG. Для такого представления каждый источник является переменной в юниверсе, и каждый приемник является набором из семейства наборов, а элемент u находится в наборе S тогда и только тогда, когда существует путь от вершины, представляющей u, до вершины, представляющей набор S.
Эта проблема хорошо известна? Есть ли полиномиальный алгоритм для этой проблемы?
graph-theory
graph-algorithms
Мартин Ватшелле
источник
источник
Ответы:
Предположим, что содержит только источники и приемники, поскольку входные данные могут быть легко переведены в эквивалентный входной.D
Обратите внимание, что даже если моя гипотеза верна, технически этот аргумент не доказывает NP-сложность вашей проблемы, поскольку сокращение - это не уменьшение Карпа, а уменьшение Кука.
источник