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

25

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

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

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

ха
источник
Когда k=logn , число таких подмножеств равно (|V|logn)nlogn , и проверка, имеет ли граф, индуцированный подмножеством, идеальное соответствие, используя Tutte's характеристика занимает время O(2logn)=O(n) , поэтому вряд ли она будет даже NP-полной, если только гипотеза об экспоненциальном времени не верна. Следовательно, интересным является случай, когда k=θ(nlogn) , и в этом случае наивный подход занимает 2O(n) времени, если вы ищете полноту #P.
Саджин Корот
@ Сажин Корот: я не следую последнему предложению в вашем комментарии. Например, если k = √n, наивный подход занимает 2nΩ(1) времени, и я не думаю, что это дает какие-либо доказательства того, что он # P-завершен.
Цуёси Ито
@TsuyoshiIto: Да, вы правы. Надо было «выбрать k таким, чтобы наивный подход занимал O(2n) времени».
Саджин Корот
@ Сажин Корот: Почему нужно выбирать значение k таким, чтобы наивный подход занимал времени? Это, вероятно, не повредит, но я не понимаю, почему это нужно делать. O(2n)
Цуёси Ито
4
Кажется, что большинство проблем типа "как индуцированные человеком подграфы размера k имеют свойство X?" тяжело Даже свойство "имеет ребро" сложно ("Имеет ребро" решает "не имеет ребро", которое в дуэли "является полным графом ... решает МАКС. КЛИК"). Это действительно дает понять, что «иметь идеальное соответствие» также будет сложно, но найти доказательство сейчас сложно.
bbejot

Ответы:

6

Проблема # P-полная. Это следует из последнего абзаца страницы 2 следующего документа:

CJ Colbourn, JS Provan, D. Vertigan, Сложность вычисления полинома Тутте на трансверсальных матроидах, Combinatorica 15 (1995), no. 1, 1–10.

http://www.springerlink.com/content/wk55t6873054232q/

ха
источник
6

Проблема допускает FPTRAS. Это рандомизированный алгоритм который получает граф , параметр и рациональные числа и качестве входных данных. Если - это количество вершинных наборов, которые вы ищете, то выводит число такое, что и это происходит за время , где некоторая вычислимая функция и G k N ϵ > 0 δ ( 0 , 1 ) z k A z P ( z ′)AGkNϵ>0δ(0,1)zkAzf ( k ) g ( n , ϵ - 1 , log δ

P(z[(1ϵ)z,(1+ϵ)z])1δ,
егf(k)g(n,ϵ1,logδ1)fg это некоторый полином.

Это следует из Thm. 3,1 в (Джеррум, Meeks 13) : учитывая свойство графов, существует FPTRAS, с тем же входом, что и выше, который приближается к размеру набора при условии, что вычислима, монотонна и все ее гранично-минимальные графы имеют ограниченную ширину дерева. Все три условия выполняются, если является свойством графа допуска идеального соответствия.{ S V ( G ) | S | = k Φ ( G [ S ] ) } , Φ ΦΦ

{SV(G)|S|=kΦ(G[S])},
ΦΦ
Раду Куртиканский
источник