Подсчет количества покрытий вершин: когда это сложно?

Рассмотрим # P-полную задачу подсчета числа покрытий вершин данного графа .$G = (V, E)$

Я хотел бы знать, есть ли какой-либо результат, показывающий, как сложность такой проблемы изменяется с некоторым параметром (например, d = | E $G$).$d = \frac{|E|}{|V|}$

У меня такое ощущение, что проблема должна быть легче, когда разрежена, а когда G плотная, в то время как это должно быть трудно, когда G «посередине». Это действительно так?$G$$G$$G$

Проблема #VC вычисления количества вершинных покрытий данного графа остается # P-трудной для 3-регулярных графов; см. например [Greenhill, 2000].

Чтобы показать, что проблема #VC остается # P-трудной для графов с не более чем $c\cdot n$ ребрами, где $n$ - количество вершин и $0<c<3/2$ , уменьшить от 3-регулярном случае путем добавления достаточно большой независимый набор (линейного размера). Количество покрытий вершин остается неизменным, если вы добавляете независимый набор.

Кроме того , чтобы показать , что проблема остается #VC # Р-трудно для графов с по меньшей мере $c\cdot n^2$ ребер, где $n$ есть число вершин и $0<c<1/2$ , сократить с #VC путем добавления большого достаточно Клика компонент (линейного размера). Количество покрытий вершин умножается на $p+1$ если вы добавляете клику размера $p$ к графу.

Кэтрин С. Гринхилл: Сложность подсчета раскрасок и независимых множеств в разреженных графах и гиперграфах . Вычислительная сложность 9 (1): 52-72 (2000)

Следуя ответу Ярослава, Луби и Вигода были первыми, кто показал FPRAS для #IS в условиях плотности (максимальная степень 4, которая, я полагаю, слабее результата Вейца), в то время как Дайер, Фриз и Джеррум показали, что для FPRAS нет #IS, если максимальная степень графа равна 25, если RP = NP.

Ссылки:

Мартин Дайер, Алан Фриз и Марк Джеррум. О подсчете независимых множеств в разреженных графах. FOCS 1999.

Майкл Луби и Эрик Вигода. Примерно считая до четырех. STOC 1997.

См. Также лекционные заметки Джеррума ETH «Подсчет, выборка и интеграция: алгоритмы и сложность».

Что касается экспоненциальной сложности времени, общие случаи и экземпляры с постоянной максимальной степенью одинаково трудны: лемма о разборе Impagliazzo, Paturi, Zane (2002) показывает, что переменные экземпляры d -Sat могут быть сведены к экземплярам d -Sat не более f ( d , ϵ ) ⋅ n предложений во времени exp ( ϵ n ) . Как отмечалось в совместной работе с Хусфельдом и Вахленом, лемма о спарсификации работает и для счетных версий d- Sat, и особенно для случая подсчета$n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (что эквивалентно подсчету независимых множеств и подсчету вершин).

Более того, подсчет независимых множеств в вершинном графе не может быть выполнен за время exp ( o ( n ) ), если гипотеза экспоненциального времени не удалась. Это еще неопубликованное наблюдение, о котором было объявлено в докладе во время вычислительного счета на семинаре в Дагштуле .$n$$\exp(o(n))$

Множество является покрытием вершин, если его дополнение является независимым множеством, поэтому эта задача эквивалентна подсчету независимых множеств.

Алгебраический подсчет независимых множеств является FPT для графов ограниченной ограниченной клики-ширины. Например, см. Courcelle «Многомерный чередующийся полином и его вычисление для графов ограниченной ширины клика», где они вычисляют обобщение полинома независимости. Сложение коэффициентов полинома независимости дает количество независимых множеств.

Графики с максимальной степенью 3 могут иметь неограниченную ширину клика.

Численный подсчет независимых множеств прослеживается, когда в задаче наблюдается «затухание корреляции». Дрор Вейц ( STOC'06 ) дает детерминированный FPTAS для подсчета взвешенных независимых множеств на графах максимальной степени$d$ когда вес $\lambda$ является

_{(источник: yaroslavvb.com )}

Регулярный (невзвешенный) независимый подсчет набора соответствует $\lambda=1$ поэтому его алгоритм дает FPTAS для числа покрытий вершин на графах максимальной степени 5.

Его алгоритм основан на построении самоходного дерева обхода в каждой вершине и усечении этого дерева на глубине $d$, Фактор ветвления уклоняющихся от прогулок деревьев определяет диапазон$\lambda$ для которого небольшая глубина $d$ дает хорошее приближение, и приведенная выше формула выводится с использованием максимальной степени графа для верхней границы этого фактора ветвления.