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

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

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| \choose 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 . $k$ $k$ $M$ $M'$ $M$ $M'$ $k$

cc.complexity-theory co.combinatorics counting-complexity

— 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

czasu, jeśli szukasz kompletności #P.

k = \log n

$k=\log n$

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

$\binom{|V|}{\log n}\leq n^{\log n}$

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

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

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

$k=\theta(\frac{n}{\log n})$

2^{O (n)}

$2^{O(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

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

$2^{n^{\Omega(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

$k$ takie, że naiwne podejście zajmuje

O (2^{n})

$O(2^n)$ 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 (2^{n})

$O(2^n)$

— Tsuyoshi Ito

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:

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

Problem przyznaje FPTRAS. Jest to randomizowany algorytm który otrzymuje wykres , parametr oraz liczby wymierne i $\mathbb{A}$ $G$ $k\in \mathbb{N}$ $\epsilon >0$ jako dane wejściowe . Jeśli jest liczbązestawów -vertex, których szukasz, to wypisuje liczbę taką, że $\delta \in (0,1)$ $z$ $k$ $\mathbb{A}$ $z'$ i czyni to w czasie , gdzie jest nieco obliczeniowy funkcji i jest około wielomianu.

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$

Wynika to z Thm. 3.1 w (Jerrum, Meeks 13) : Biorąc pod uwagę właściwość $\Phi$ 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. \subseteq V. (sol) ∣ | S. | = k \land Φ (sol [S.])},

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

Φ

$\Phi$

Φ

$\Phi$

— Radu Curticapean
źródło