Сложность подсчета количества краевых покрытий графа

16

Край крышки представляет собой подмножество ребер графа, что каждая вершина графа смежна по крайней мере , одного края крышки. В следующих двух статьях говорится, что подсчет краевых покрытий является # P- полным: Простая FPTAS для подсчета краевых покрытий и генерации краевых покрытий для графов путей . Однако, если я что-то пропустил, они не предоставят ссылку на это утверждение или доказательство. (Ссылка 3 первой статьи казалась многообещающей, но я тоже не нашел там того, что хотел).

Где я могу найти ссылку или доказательство того факта, что подсчет числа краевых покрытий графа является # P-полным?

a3nm
источник

Ответы:

11

Я не знаю, где это было впервые доказано, но, поскольку 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 ] содержит kkk3kHolant([0,1,,1])[0,1,,1]k1 - х. И, кроме того, это эквивалентно . Теперь мы применяем голографическое преобразование с помощью T = [ 1 e π i / k 1 0 ]Holant([1,0,1]|[0,1,,1])T=[1eπi/k10](или наоборот, в зависимости от вашей точки зрения). По теореме Холанта Валианта (4,5) это не меняет сложности проблемы (на самом деле обе проблемы на самом деле являются одной и той же проблемой, потому что они согласуются с выводом каждого входа ... изменилось только выражение проблемы) ). Альтернативное выражение для этой проблемы

где = k - функция равенства на

Holant([1,0,1]T2|(T1)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=2k1k3kk3

Примечание: можно также увидеть эту теорему и доказательство в диссертации Майкла Ковальчика .

Я продолжу поиск литературы, чтобы увидеть, что EdgeCover был показан как # P-hard раньше (1).

(1) Голографическое сокращение, интерполяция и твердость по Jin-Yi Cai, Pinyan Lu и Mingji Xia ( журнал , препринт ).

k{0,1}

k{0,1}

(4) Голографические алгоритмы Лесли Г. Валианта

(5) Теорема Холанта Валианта и тензоры вратных ворот Джин-Йи Цая и Винай Чоудхари

Tyson Williams
источник
Wow, thanks for pointing me to this and for taking the time to explain the vocabulary and connection to edge cover! I agree with you that (1) implicitly proves that EdgeCover is hard (and is hard even for 3-regular planar graphs). I'm also interested to know if anyone proved the #P-hardness of EdgeCover before (1), though I'm already quite happy that I have something to cite if I need to use this result (which was my main concern when asking). Thanks again for your answer!
a3nm
2
@Tyson Williams: if you start from a 2-3-regular graph and contract the nodes of the partition of degree 2 then you could end up with a 3-regular multigraph, i.e., with parallel edges. Can this be fixed to show hardness on 3-regular simple graphs? More generally, this question could be asked for all the results on Holant problems, so I created a new question here cstheory.stackexchange.com/q/43912/38111, because I think the issue is not restricted to this particular problem (counting edge covers). I'd be glad if you could take a look :)
M.Monet
О да. Хорошее наблюдение. Я не могу сейчас вспомнить, какие результаты есть для простых графиков.
Тайсон Уильямс
1
@TysonWilliams: Спасибо за подтверждение, и не беспокойтесь! В моем сообществе «график» всегда означает «простой график», если не указано иное, поэтому я не указал это явно в вопросе.
a3nm
1
@TysonWilliams: в конце концов, мы нашли, как получить результат твердости при подсчете краевых покрытий для простых графиков (2-3 регулярных двудольных и плоских) с помощью голографических средств. Подробности в последней версии моего ответа ниже и в Приложении D к arxiv.org/abs/1703.03201 . Мы используем жесткость подсчета покрытий вершин на 3-правильных двудольных плоских графах из xia2006regular: у этих графов нет самоконтролей, мы подразделяем каждое ребро, которое удаляет параллельные ребра, и голография cai2008 не создает проблем. (Что касается 3-регулярных графиков, как в вашем ответе, мы не знаем.)
a3nm
4

После еще нескольких литературных поисков оказалось, что сложность подсчета краевых покрытий на графике была показана как # 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, и именно это побудило меня написать этот ответ.

a3nm
источник