Это смущает меня.
Один простой случай подсчета - это когда проблема решения находится в а решений нет.
Лекция показывает, что проблема подсчета числа совершенных совпадений в двудольном графе (эквивалентно подсчету числа циклов в ориентированном графе) является -полной.
Они дают сокращение от подсчета покрытий вершин размера до подсчета покрытий циклов в орграфе с использованием гаджетов.
Теорема 27,1 Число хороших чехлов цикла в является ( к ! ) 2 раза числа вершин обложек G размера к .
Используя гаджет они оставляют только «хорошие» циклы.
Мое понимание лекции состоит в том, что не имеет покрытия вершин размера k, если преобразованный орграф G ′ не имеет покрытия циклов. Проверка того, имеет ли G ′ покрытие циклом, может быть выполнена за полиномиальное время, подразумевая, что P = N P, поскольку мы можем преобразовать проблему решения в поиск решения.
Что я недопонимаю?
Перманент матрицы смежности орграфа считает циклические покрытия и является -завершенным.
Проблема Решение «Является ли перманент (0,1) матрицы нуля» в Р , так как найти крышку цикла в .
подразумевает, что не существует редукции подсчета N P- полных задач до счета ( 0 , 1 ) -перманента, который отображает 0 ↦ 0 .
Изменить связанный вопрос МО
добавленной
Markus Bläser
указывает, что плохой цикл все еще "там", но сумма их весов исчезает.
Как мне кажется, вес плохого цикла в виджете равен нулю.
Со страницы 148 (11 из pdf):
Полная матрица смежности B с подматрицами A, соответствующими этим четырем узлам виджетов, имеет значение 1 для каждого покрытия хорошего цикла в H и 0 для каждого покрытия плохого цикла
Другой вопрос:
Разве покрытие максимального цикла веса не будет содержать только хорошие циклы, соответствующие покрытию вершин в исходном графе?
В CC каждая вершина должна быть ровно в одном цикле.
Ответы:
Похоже, недоразумение заключается в следующем:
В окончательном сокращении до (0,1) -перманентности они используют модульную арифметику, что нарушает мой аргумент.
Не нашли изъяна в вопросе о максимальном покрытии взвешенного цикла, который, по-видимому, не затронут вышеуказанным.
источник