Путаница в том, что сокращение числа вершин охватывает количество циклов

11

Это смущает меня.

Один простой случай подсчета - это когда проблема решения находится в а решений нет.P

Лекция показывает, что проблема подсчета числа совершенных совпадений в двудольном графе (эквивалентно подсчету числа циклов в ориентированном графе) является -полной.#P

Они дают сокращение от подсчета покрытий вершин размера до подсчета покрытий циклов в орграфе с использованием гаджетов.k

Теорема 27,1 Число хороших чехлов цикла в является ( к ! ) 2 раза числа вершин обложек G размера к .H(k!)2Gk

Используя гаджет они оставляют только «хорошие» циклы.

Мое понимание лекции состоит в том, что не имеет покрытия вершин размера k, если преобразованный орграф G не имеет покрытия циклов. Проверка того, имеет ли G покрытие циклом, может быть выполнена за полиномиальное время, подразумевая, что P = N P, поскольку мы можем преобразовать проблему решения в поиск решения.GkGGP=NP

Что я недопонимаю?


Перманент матрицы смежности орграфа считает циклические покрытия и является -завершенным.#P

Проблема Решение «Является ли перманент (0,1) матрицы нуля» в Р , так как найти крышку цикла в .P

подразумевает, что не существует редукции подсчета N P- полных задач до счета ( 0 , 1 ) -перманента, который отображает 0 0 .PNPNP(0,1)00

Изменить связанный вопрос МО


добавленной

Markus Bläser указывает, что плохой цикл все еще "там", но сумма их весов исчезает.

Как мне кажется, вес плохого цикла в виджете равен нулю.

Со страницы 148 (11 из pdf):

Полная матрица смежности B с подматрицами A, соответствующими этим четырем узлам виджетов, имеет значение 1 для каждого покрытия хорошего цикла в H и 0 для каждого покрытия плохого цикла

Другой вопрос:

Разве покрытие максимального цикла веса не будет содержать только хорошие циклы, соответствующие покрытию вершин в исходном графе?k

В CC каждая вершина должна быть ровно в одном цикле.

Joro
источник
Они не оставили только хорошие циклы. В своих аргументах о подсчете они исключили плохие циклы. Проблема в том, что вы должны считать хорошие обложки циклов. Поэтому, если вы найдете покрытие цикла, которое не является хорошим покрытием цикла, вы не сможете получить покрытие k-вершины. Но если вы найдете хорошее покрытие цикла да, график имеет k-VC. Это ничего не нарушает.
Саид
k
@ Seed Разве они не считают все покрытия циклов в преобразованном G '?
Джоро
1
Сокращение присваивает веса ребрам. Покрытия для плохих циклов могут иметь положительный или отрицательный вес, там общий вклад равен нулю. Но эти циклы все еще «там» и могут быть обнаружены алгоритмом обнаружения покрытия цикла, и в этом случае вы не знаете, есть ли хорошее покрытие цикла или нет.
Маркус Блезер
1
@ MarkusBläser Спасибо, это имеет смысл :). Почему бы не ответить?
Joro

Ответы:

1

Похоже, недоразумение заключается в следующем:

В окончательном сокращении до (0,1) -перманентности они используют модульную арифметику, что нарушает мой аргумент.

AB

nperm(A)=0perm(B)=mn

nB


Не нашли изъяна в вопросе о максимальном покрытии взвешенного цикла, который, по-видимому, не затронут вышеуказанным.

Joro
источник