Kompleksitas komputasi dari penghitungan subgraph yang diinduksi memiliki kecocokan sempurna

Mengingat sebuah grafik diarahkan dan tertimbang dan integer bahkan , apa yang kompleksitas komputasi penghitungan set simpul sehingga dan subgraf dari terbatas himpunan titik mengakui pasangan yang cocok? Apakah kompleksitas # P-selesai? Apakah ada referensi untuk masalah ini? $G=(V,E)$ $k$ $S\subseteq V$ $|S|=k$ $G$ $S$

Perhatikan bahwa masalahnya tentu saja mudah untuk konstanta karena dengan demikian semua subgraf dengan ukuran dapat disebutkan dalam waktu . Perhatikan juga bahwa masalahnya berbeda dengan menghitung jumlah pencocokan sempurna. Alasannya adalah bahwa satu set simpul yang mengakui pencocokan sempurna mungkin memiliki beberapa pencocokan sempurna. $k$ $k$ ${|V| \choose k}$

Cara lain untuk menyatakan masalahnya adalah sebagai berikut. Pencocokan disebut pencocokan $k$ jika cocok dengan $k$ . Dua pencocokan $M$ dan $M'$ adalah `` vertex-set-non-invariant' 'jika set simpul yang cocok dengan $M$ dan $M'$ tidak identik. Kami ingin menghitung jumlah total $k$ matching -vertex-set-non-invarian .

Ketika

k = \log n

$k=\log n$ , jumlah himpunan bagian tersebut adalah

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

$\binom{|V|}{\log n}\leq n^{\log n}$ , dan memeriksa apakah grafik yang diinduksi oleh subset memiliki pencocokan sempurna menggunakan Tutte's karakterisasi membutuhkan

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

$O(2^{\log n})=O(n)$ waktu, oleh karena itu tidak mungkin untuk itu bahkan NP-lengkap kecuali hipotesis waktu eksponensial salah. Karenanya kasus yang menarik adalah ketika

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

$k=\theta(\frac{n}{\log n})$ , dalam hal ini pendekatan naif membutuhkan waktu

2^{O (n)}

$2^{O(n)}$ waktu, jika Anda mencari kelengkapan #P.

Sajin Koroth

@Sajin Koroth: Saya tidak mengikuti kalimat terakhir dalam komentar Anda. Misalnya, jika k = √n, pendekatan naif membutuhkan waktu

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

$2^{n^{\Omega(1)}}$ waktu, dan saya tidak berpikir bahwa ini memberikan bukti bahwa itu # P-complete.

Tsuyoshi Ito

@ TsuyoshiIto: Ya Anda benar. Seharusnya "memilih

k

$k$ sedemikian rupa sehingga, pendekatan naif membutuhkan waktu

O (2^{n})

$O(2^n)$ ".

Sajin Koroth

@Sajin Koroth: Mengapa kita harus memilih nilai k sedemikian rupa sehingga pendekatan naif membutuhkan waktu ? Melakukan hal itu mungkin tidak menyakitkan, tetapi saya tidak mengerti mengapa seseorang harus melakukan itu.

O (2^{n})

$O(2^n)$

Tsuyoshi Ito

Tampaknya sebagian besar masalah semacam itu "bagaimana manusia menginduksi subgraf berukuran k memiliki properti X?" sulit. Bahkan properti "memiliki tepi" sulit ("Memiliki tepi" memecahkan "tidak memiliki tepi" yaitu "adalah grafik lengkap" dalam duel ... memecahkan MAX CLIQUE). Ini benar-benar membuatnya merasa bahwa "memiliki kecocokan yang sempurna" juga akan sulit, tetapi menemukan bukti saat ini sulit.

bbejot

Jawaban:

Masalahnya adalah # P-selesai. Ini mengikuti dari paragraf terakhir dari halaman 2 makalah berikut:

CJ Colbourn, JS Provan, dan D. Vertigan, Kompleksitas menghitung polinomial Tutte pada matroid transversal, Combinatorica 15 (1995), no. 1, 1–10.

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

Ha
sumber

Masalahnya mengakui FPTRAS. Ini adalah algoritma acak yang mendapat grafik , parameter , dan bilangan rasional dan sebagai input. Jika adalah jumlah set -vertex yang Anda cari, maka menghasilkan angka sehingga dan melakukannya dalam waktu , di mana adalah beberapa fungsi yang dapat dihitung dan $\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$ adalah polinomial.

Ini mengikuti dari Thm. 3.1 in (Jerrum, Meeks 13) : Diberikan properti grafik, ada FPTRAS, dengan input yang sama seperti di atas, yang mendekati ukuran himpunan asalkan dapat dikomputasi, monoton, dan semua grafik tepi-minimalnya telah terikat dengan treewidth. Ketiga kondisi tersebut berlaku jika adalah properti grafik untuk mengakui pencocokan sempurna. $\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$

Radu Curticapean
sumber