Złożoność obliczeniowa liczników indukowanych liczeniem, które dopuszczają idealne dopasowanie

25

Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje odniesienie do tego problemu?G=(V,E)kSV|S|=kGS

Zauważ, że problem jest oczywiście łatwy dla stałego k ponieważ wówczas wszystkie podgrupy wielkości k można wyliczyć w czasie . Zauważ też, że problem różni się od zliczania liczby idealnych dopasowań. Powodem jest to, że zestaw wierzchołków, który dopuszcza idealne dopasowanie, może mieć wiele idealnych dopasowań.(|V|k)

Inny sposób stwierdzenia problemu jest następujący. Dopasowanie nazywane jest dopasowaniem jeśli pasuje do wierzchołków. Dwa dopasowania i są `` zestawem wierzchołków-niezmiennikiem '', jeśli zbiory wierzchołków pasujące do i nie są identyczne. Chcemy policzyć całkowitą liczbę dopasowań zestawu wierzchołków bez niezmienności .kkMMMMk

ha
źródło
Gdy , liczba takich podzbiorów wynosi i sprawdzanie, czy wykres indukowany przez podzbiór ma idealne dopasowanie za pomocą Tutte'a charakteryzacja zajmuje czas , dlatego jest mało prawdopodobne, aby była ona nawet NP-zupełna, chyba że hipoteza wykładniczego czasu jest błędna. Dlatego interesującym przypadkiem jest , w którym to przypadku podejście naiwne zajmuje 2 ^ {O (n)} czasu, jeśli szukasz kompletności #P. k=logn(|V|logn)nlognO(2logn)=O(n)k=θ(nlogn)2O(n)
Sajin Koroth
@Sajin Koroth: Nie podążam za ostatnim zdaniem w twoim komentarzu. Na przykład, jeśli k = √n, naiwne podejście zajmuje 2nΩ(1) czasu i nie sądzę, że daje to dowód na to, że jest on # P-ukończony.
Tsuyoshi Ito
@TsuyoshiIto: Tak, masz rację. Powinno być „wybrać k takie, że naiwne podejście zajmuje O(2n) czasu”.
Sajin Koroth
@Sajin Koroth: Dlaczego warto wybrać wartość k, aby naiwne podejście trwało ? Takie postępowanie prawdopodobnie nie zaszkodzi, ale nie rozumiem, dlaczego należy to robić. O(2n)
Tsuyoshi Ito
4
Wydaje się, że większość problemów tego rodzaju „jak indukowane przez człowieka podgrupy wielkości k mają właściwość X?” są trudne. Nawet właściwość „ma krawędź” jest trudna („Ma krawędź„ rozwiązuje ”nie ma krawędzi„ która jest ”jest kompletnym wykresem” w pojedynku ... rozwiązuje MAX CLIQUE). To naprawdę sprawia wrażenie, że „idealnie pasuje” będzie również trudne, ale znalezienie dowodu jest obecnie trudne.
bbejot

Odpowiedzi:

6

Problem jest # P-ukończony. Wynika z ostatniego akapitu strony 2 następującego artykułu:

CJ Colbourn, JS Provan i D. Vertigan, Złożoność obliczania wielomianu Tutte na matroidach poprzecznych, Combinatorica 15 (1995), no. 1, 1–10.

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

ha
źródło
6

Problem przyznaje FPTRAS. Jest to randomizowany algorytm który otrzymuje wykres G , parametr k N oraz liczby wymierne ϵ > 0 i δ ( ϵ ) z ] )AGkNϵ>0jako dane wejściowe 0 , 1 ) . Jeśli z jest liczbązestawów k -vertex, których szukasz, to A wypisuje liczbę z taką, że P ( z [ ( 1 - ϵ ) z , ( 1 +δ(0,1)zkAz i czyni to w czasie F ( k ) g ( n , ε - 1 , log δ - 1 ) , gdzie F jest nieco obliczeniowy funkcji i g jest około wielomianu.

P(z[(1ϵ)z,(1+ϵ)z])1δ,
f(k)g(n,ϵ1,logδ1)fg

Wynika to z Thm. 3.1 w (Jerrum, Meeks 13) : Biorąc pod uwagę właściwość Φ grafów, istnieje FPTRAS, z takim samym wejściem jak powyżej, który jest zbliżony do wielkości zbioru pod warunkiem, że Φ jest obliczalny, monotoniczny, a wszystkie jego minimalne krawędzie wykresy mają ograniczoną szerokość. Wszystkie trzy warunki są spełnione, jeśli Φ jest właściwością graficzną dopuszczenia idealnego dopasowania.

{S.V.(sol)|S.|=kΦ(sol[S.])},
ΦΦ
Radu Curticapean
źródło