Я не знаю, где это было впервые доказано, но, поскольку EdgeCover имеет выражение в виде проблемы Холанта в булевой области, оно включено во многие теоремы о дихотомии Холанта.
EdgeCover включен в теорему дихотомии в (1). Теорема 6.2 (в журнальной версии или теорема 6.1 в препринте) показывает, что EdgeCover является # P-сложным по сравнению с плоскими 3-регулярными графами. Чтобы увидеть это, выражение для EdgeCover как задачи Холанта над 3-регулярными графами является Holant([0,1,1,1]) (или замените [0,1,1,1] на [0,1,…,1] содержащий 1 для той же задачи надкkkрегулярные графы). Эта нотация перечисляет выходные данные симметричной функции в порядке входного веса Хэмминга. Для некоторого подмножества ребер набора (которое мы считаем назначенным 1, а набору дополнений - 0), ограничение в каждой вершине состоит в том, что по крайней мере одному ребру присваивается 1, что в точности соответствует функции [ 0 , 1 , 1 , 1 ] . Для фиксированного подмножества ребер его вес является произведением выходных данных [ 0 , 1 , 1 , 1 ][0,1,1,1][0,1,1,1][0,1,1,1]в каждой вершине. Если какая-либо вершина не покрыта, она дает коэффициент . Если все вершины покрыты, то все вершины дают множитель 1 , поэтому вес также равен 1 . Затем Holant суммирует все возможные подмножества ребер и прибавляет вес, соответствующий каждому подмножеству. Это значение Холанта является точно таким же, если мы подразделяем каждое ребро и накладываем ограничение на то, что оба падающих ребра должны быть равны этим новым вершинам. Используя обозначение симметричной функции, эта функция двоичного равенства равна [ 1 , 0 , 1 ] . Этот график является двудольным. Вершины в одной части имеют [ 0 , 1 ,011[1,0,1] то время как вершины в другой части имеютограничение [ 1 , 0 , 1 ] . Выражение для этой проблемы Холанта - это Холант ( [ 0 , 1 , 1 , 1 ] | [ 1 , 0 , 1 ] ) . Затем вы можете проверить для себя эту строку " [ 0 , 1 , 1 , 1 ] " и столбец " [ 1 , 0[0,1,1,1][1,0,1]Holant([0,1,1,1]|[1,0,1])[0,1,1,1] "таблицы рядом с приведенной выше теоремой содержит" H ", что означает, что задача # P-трудная, даже входной граф должен быть плоским.[1,0,1]
Примечание: обратите внимание, что Пиньян Лу является автором как этой, так и первой статьи, которую вы цитируете. Я предполагаю, что, когда в их статье говорится, что «подсчет краевых покрытий является проблемой # P-завершения, даже когда мы ограничиваем ввод 3 регулярными графами», они неявно ссылались на (1). Они, вероятно, не упомянули, что твердость также сохраняется, когда дополнительно ограничивается плоскими графами, поскольку их FPTAS не нуждается в этом ограничении.
Более поздние теоремы дихотомии Холанта, такие как те, что в (2,3) - конференции и журнальные версии той же работы - доказали больше. Теорема 1 (в обеих версиях) говорит, что EdgeCover является # P-сложным над плоскими регулярными графами при k ≥ 3 . Чтобы увидеть это, нам нужно применить голографическое преобразование. Как описано выше, выражение для EdgeCover как задачи Холанта над k -регулярными графами имеет вид Холанта ( [ 0 , 1 , … , 1 ] ) , где [ 0 , 1 , … , 1 ] содержит kkk≥3kHolant([0,1,…,1])[0,1,…,1]k1 - х. И, кроме того, это эквивалентно . Теперь мы применяем голографическое преобразование с помощью T = [ 1 e π i / k 1 0 ]Holant([1,0,1]|[0,1,…,1])T=[11eπi/k0](или наоборот, в зависимости от вашей точки зрения). По теореме Холанта Валианта (4,5) это не меняет сложности проблемы (на самом деле обе проблемы на самом деле являются одной и той же проблемой, потому что они согласуются с выводом каждого входа ... изменилось только выражение проблемы) ). Альтернативное выражение для этой проблемы
где = k - функция равенства на
Holant([1,0,1]T⊗2|(T−1)⊗k[0,1,…,1])=Holant([2,eπi/k,e2πi/k]|=k),
=k входам. Чтобы применить теорему 1, мы должны нормализовать
[ 2 , e π i / k , e 2 π i / k ] к
[ 2 e - π i / k , 1 , e π i / k ] путем деления исходной функции на
e π i / k , что не меняет сложности задачи, поскольку это значение отлично от нуля. Тогда значения
X и
Yk[2,eπi/k,e2πi/k][2e−πi/k,1,eπi/k]eπi/kXYв формулировке теоремы
и
Y = - 2 k - 1 . При
k ≥ 3 можно проверить, что эта проблема, поэтому, таким образом, EdgeCover также является # P-жесткой над планарными
k -регулярными графами при
k ≥ 3 .
X=2Y=−2k−1k≥3kk≥3
Примечание: можно также увидеть эту теорему и доказательство в диссертации Майкла Ковальчика .
Я продолжу поиск литературы, чтобы увидеть, что EdgeCover был показан как # P-hard раньше (1).
(1) Голографическое сокращение, интерполяция и твердость по Jin-Yi Cai, Pinyan Lu и Mingji Xia ( журнал , препринт ).
k{0,1}
k{0,1}
(4) Голографические алгоритмы Лесли Г. Валианта
(5) Теорема Холанта Валианта и тензоры вратных ворот Джин-Йи Цая и Винай Чоудхари
После еще нескольких литературных поисков оказалось, что сложность подсчета краевых покрытий на графике была показана как # P-полная в bordewich2008path, Приложение A.1 . (Это предполагает произвольные графы в качестве входных данных, т. Е. Они не могут применять какие-либо предположения к входному графу, за исключением того, что они отмечают, что минимальная степень может быть сделана произвольно большой). (bordewich2008path далее указывает, что результат заявлен без доказательства в графе bubley1997.) Этот результат предшествует результатам Cai, Lu и Xia, на которые ссылается как (1) в ответе Тайсона Уильямса, и он не опирается на голографическую теорию.
В частности, результат опирается на # P-сложность подсчета независимых множеств в 3-регулярных графах, показанных в комплексе greenhill2000 (улучшая аналогичный результат для графов степени не более 4, показанных в сложности vadhan1997), и подтверждает результат, используя технику bubley1997graph ,
Более сильный результат, а именно, твердость подсчета краевых покрытий в двудольном графе степени не более четырех (далее подразумевается, что набор краев может быть разбит на четыре соответствия), была изучена независимо в khanna2011queries, Приложение B.1, снова без голографических инструментов. , Они полагаются на сложность подсчета независимых множеств в 3-регулярных двудольных графах (показанных в xia2006regular путем уточнения метода интерполяции сложности vadhan1997), а затем применяют уточнение метода bordewich2008path.
Еще более сильный результат (твердость подсчета краевых покрытий в двудольном 2-3 регулярном графе, т. Е. Двудольном графе, где все вершины на одной стороне имеют степень 2, а все вершины на другой стороне имеют степень 3, которая является дополнительно плоской), могут быть показаны с использованием результатов xia2006regular и cai2008holographic. Объяснения для этого приведены в Приложении D к последней версии нашей статьи PODS'17 . В этом случае мы достаточно тщательно проверили, что результат верен для простых графов, т. Е. Для графов, которые не имеют ни самоконтроля, ни многоугольников (см. Комментарии к ответу Тайсона Уильямса).
Что касается жесткости на плоских 3-регулярных графах, то в ответе Тайсона Уильямса приведен аргумент, но может показаться, что он допускает многоугольники и самопетли в графах.
Ссылки:
Diclaimer: я только поверхностно посмотрел на эти документы, и я не эксперт в этой области, поэтому могут быть ошибки в моем резюме выше.
Спасибо анонимному судье PODS'17 за то, что он указал мне на khanna2011queries, и именно это побудило меня написать этот ответ.
источник