Существует ли прямое / естественное сокращение для подсчета двойных совершенных совпадений с использованием перманента?

Подсчет количества совершенных совпадений в двудольном графе сразу сводится к вычислению перманента. Поскольку поиск идеального соответствия в двудольном графе есть в NP, существует некоторое сокращение от двудольных графов к перманенту, но это может привести к неприятному полиномиальному взрыву, используя приведение Кука к SAT, а затем теорему Валианта, чтобы свести к постоянны.

Эффективное и естественное сокращение от двудольного графа до матрицы где было бы полезно для фактической реализации для подсчета идеальных совпадений с использованием существующих, сильно оптимизированных библиотеки, которые вычисляют перманент. $f$ $G$ $A = f(G)$ $\operatorname{perm}(A) = \Phi(G)$

Обновлено: я добавил вознаграждение за ответ, включающий в себя эффективно вычисляемую функцию для переноса произвольного графа в двудольный граф с тем же числом совершенных совпадений и не более вершин. $G$ $H$ $O(n^2)$

graph-theory counting-complexity reductions permanent Деррик Стоули
источник

Текущий заголовок звучит как домашнее задание, но реальный вопрос гораздо интереснее. Я почти даже не открывал вопрос, потому что думал, что это домашнее задание, и скоро его закроют, пока я не увидел, что у него уже было 9 голосов, и мне стало любопытно ... Может быть, изменить название на что-то вроде: " Есть ли прямое / естественное сокращение для подсчета двойных совершенных совпадений с использованием перманента? "

Джошуа Грохов

Отличная идея. Я даже не думал об этом. Спасибо.

Деррик Столи

Nitpicking: «Так как поиск идеального совпадения в недвойственном графе находится в NP» → «Поскольку подсчет идеальных совпадений в недвойственном графе находится в #P»

Tsuyoshi Ito

Ваша придирка верна, и я подумал о том, чтобы написать это, но то, как я это написал, намекает на то, что сокращение применяет сокращения Кука ТОГДА Валианта. Я ищу прямое, эффективное сокращение.

Деррик Столи

Существует снижение, которое избегает Кука: сначала напишите формулу VNP для идеальных соответствий (я могу вспомнить одну, которая очень похожа на формулу для перманента и имеет размер

). Тогда в силу универсальности перманента это можно записать как перманент матрицы размером

. При этом используется тот факт, что формула размера

может быть записана как перманент матрицы размера

. Более прямой, чем проходящий через Кука, но все же не такой прямой / естественный, как метод perm считает идеальные совпадения в двудольном графе.

\leq 4 n^{4}

$\leq 4n^4$

4 n^{4} + 1

$4n^4 +1$

S

$S$

S + 1

$S+1$

Джошуа Грохов

Ответы:

Я бы сказал, что «простое» приведение к двустороннему сопоставлению крайне маловероятно. Во-первых, это дало бы алгоритм для нахождения идеального соответствия в общем графе с использованием венгерского метода. Следовательно, сокращение должно содержать всю сложность алгоритма цветения Эдмонда. Во-вторых, это даст компактный LP для идеально подходящего многогранника, и, следовательно, сокращение не должно быть симметричным (что исключено результатом Yannakakis) и по своей природе очень сложным.

Мохит Сингх
источник

Это все веские причины, почему это вряд ли существует. Я должен был попросить опровержения в этом вопросе. Вероятно, я дам некоторую награду за этот ответ, если кто-то не докажет, что вы ошибаетесь.

Деррик Стоули

Несмотря на то, что это не тот ответ, который я хотел, я нашел этот ответ очень удовлетворительным.

Деррик Столи

@MohitSingh Не могли бы вы уточнить «несуществование венгерского метода для двудольных графов», «что содержит всю сложность алгоритма расцвета» и почему это дало бы «компактный LP для идеального соответствия и поэтому должно быть несимметричным» ?

Т ....

Это, очевидно, комментарий, а не ответ, но у меня пока нет никаких точек репутации, так что извините за это.

Для двудольных кубических безмостных графов существует экспоненциально много совершенных совпадений, как предположили Ловас и Пламмер в 70-х годах. Статья находится в стадии подготовки. Это может быть очень актуально для вашего вопроса, а может быть и вовсе.

Эндрю Д. Кинг
источник