Вычислительная сложность подсчета индуцированных подграфов, которые допускают идеальное совпадение

Для заданного неориентированного и невзвешенного графа и четного целого числа , какова вычислительная сложность подсчета множеств вершин таких что и подграф графа ограниченный множеством вершин допускает идеальное совпадение? Является ли сложность # P-полной? Есть ли ссылка на эту проблему? $G=(V,E)$ $k$ $S\subseteq V$ $|S|=k$ $G$ $S$

Обратите внимание, что проблема, конечно, легко для константы потому что тогда все подграфы размера могут быть перечислены во времени . Также обратите внимание, что проблема отличается от подсчета количества идеальных совпадений. Причина в том, что набор вершин, который допускает идеальное совпадение, может иметь множество идеальных совпадений. $k$ $k$ ${|V| \choose k}$

Другой способ сформулировать проблему заключается в следующем. Соответствие называется $k$ если оно совпадает с $k$ вершинами. Два соответствия $M$ и $M'$ являются `` набором вершин-неинвариантных' ', если наборы вершин, совпадающих с $M$ и $M'$ , не идентичны. Мы хотим подсчитать общее количество неинвариантных -соответствий с множеством вершин $k$ .

Когда

k = \log n

$k=\log n$ , число таких подмножеств равно

(\binom{| V |}{\log n}) \leq n^{\log n}

$\binom{|V|}{\log n}\leq n^{\log n}$ , и проверка, имеет ли граф, индуцированный подмножеством, идеальное соответствие, используя Tutte's характеристика занимает время

O (2^{\log n}) = O (n)

$O(2^{\log n})=O(n)$ , поэтому вряд ли она будет даже NP-полной, если только гипотеза об экспоненциальном времени не верна. Следовательно, интересным является случай, когда

k = θ (\frac{n}{\log n})

$k=\theta(\frac{n}{\log n})$ , и в этом случае наивный подход занимает

2^{O (n)}

$2^{O(n)}$ времени, если вы ищете полноту #P.

Саджин Корот

@ Сажин Корот: я не следую последнему предложению в вашем комментарии. Например, если k = √n, наивный подход занимает

2^{n^{Ω (1)}}

$2^{n^{\Omega(1)}}$ времени, и я не думаю, что это дает какие-либо доказательства того, что он # P-завершен.

Цуёси Ито

@TsuyoshiIto: Да, вы правы. Надо было «выбрать

k

$k$ таким, чтобы наивный подход занимал

O (2^{n})

$O(2^n)$ времени».

Саджин Корот

@ Сажин Корот: Почему нужно выбирать значение k таким, чтобы наивный подход занимал времени? Это, вероятно, не повредит, но я не понимаю, почему это нужно делать.

O (2^{n})

$O(2^n)$

Цуёси Ито

Кажется, что большинство проблем типа "как индуцированные человеком подграфы размера k имеют свойство X?" тяжело Даже свойство "имеет ребро" сложно ("Имеет ребро" решает "не имеет ребро", которое в дуэли "является полным графом ... решает МАКС. КЛИК"). Это действительно дает понять, что «иметь идеальное соответствие» также будет сложно, но найти доказательство сейчас сложно.

bbejot

Проблема допускает FPTRAS. Это рандомизированный алгоритм который получает граф , параметр и рациональные числа и качестве входных данных. Если - это количество вершинных наборов, которые вы ищете, то выводит число такое, что и это происходит за время , где некоторая вычислимая функция и $\mathbb{A}$ $G$ $k\in \mathbb{N}$ $\epsilon >0$ $\delta \in (0,1)$ $z$ $k$ $\mathbb{A}$ $z'$

P (z^{'} \in [(1 - ϵ) z, (1 + ϵ) z]) \geq 1 - δ,

$\begin{equation} \mathbb{P}(z' \in [(1-\epsilon)z,(1+\epsilon)z]) \geq 1-\delta, \end{equation}$

f (k) \cdot g (n, ϵ^{- 1}, \log δ^{- 1})

$f(k)\cdot g(n,\epsilon^{-1},\log \delta^{-1})$

f

$f$

g

$g$ это некоторый полином.

Это следует из Thm. 3,1 в (Джеррум, Meeks 13) : учитывая свойство графов, существует FPTRAS, с тем же входом, что и выше, который приближается к размеру набора при условии, что вычислима, монотонна и все ее гранично-минимальные графы имеют ограниченную ширину дерева. Все три условия выполняются, если является свойством графа допуска идеального соответствия. $\Phi$

{S \subseteq V (G) ∣ | S | = k \land Φ (G [S])},

$\begin{equation} \{S \subseteq V(G) \mid |S| =k \wedge \Phi(G[S])\}, \end{equation}$

Φ

$\Phi$

Φ

$\Phi$

Раду Куртиканский
источник

Вычислительная сложность подсчета индуцированных подграфов, которые допускают идеальное совпадение

Ответы: