Pengujian Properti untuk Set Independen

Misalkan kita diberi grafik dan parameter k , ϵ . Apakah ada rentang nilai untuk k (atau itu bisa dilakukan untuk semua k ) yang dimungkinkan untuk menguji apakah G adalah ε -far dari memiliki set independen ukuran setidaknya k dalam waktu O ( n + poly ( 1 / ε ) ) ?$G$$k,\epsilon$$k$$k$$G$$\epsilon$$k$$O(n + \text{poly}(1/\epsilon))$

Jika kita menggunakan gagasan umum -far (yaitu paling banyak ϵ n 2 tepi perlu diubah untuk mendapatkan himpunan tersebut), maka masalahnya sepele untuk k = O ( n $\epsilon$$\epsilon n^2$. Begitu$k = O(n\sqrt{\epsilon})$

• Tampaknya jika lebih besar, beberapa ide pengambilan sampel harus bekerja untuk menyelesaikan masalah. Benarkah ?$k$
• Apakah ada pengertian lain tentang -far (yaitu mungkin ϵ | E | edge sebagai gantinya) di mana ada hasil tidak trivial?$\epsilon$$\epsilon |E|$

Saya pada dasarnya mencari referensi pada saat ini.

Masalah ini memang sudah dipelajari. Goldreich, Goldwasser dan Ron mempelajarinya dalam makalah seminal mereka yang memulai pengujian properti grafik, dan kemudian, Feige, Langberg, dan Schechtman juga memiliki hasil di dalamnya dalam makalah FOCS '02 mereka "Grafik dengan angka kromatik vektor kecil dan angka kromatik besar" .

Secara khusus, [FLS '02] menunjukkan bahwa seseorang dapat membedakan antara grafik dengan ukuran bebas dari grafik ϵ- jauh agar tidak begitu (artinya, setidaknya ϵ n 2 tepi perlu dihilangkan untuk membuat set independen tersebut) dengan memilih subgraph acak yang diinduksi oleh s = ˜ O ( ρ 4 / ϵ 3 ) simpul acak dalam grafik dan memeriksa apakah subgraph acak memiliki seperangkat ukuran independen ρ s atau tidak. ([GGR '98] menunjukkan lemah terikat pada s of ~ O ( ρ $\rho n$$\epsilon$$\epsilon n^2$$s = \tilde{O}(\rho^4/\epsilon^3)$$\rho s$$s$ .) [FLS '02] juga menunjukkan batas bawah pada s dari Ω ( ρ 3 / ε 2 ) .$\tilde{O}(\rho/\epsilon^4)$$s$$\Omega(\rho^3/\epsilon^2)$

Definisi alami lain dari -close ke set independen adalah mengubah ϵ k 2 edge. Sayangnya dengan pengujian properti definisi ini tampaknya tidak bisa dipecahkan waktu polinomial. Alasannya adalah bahwa tidak ada yang tahu bagaimana menemukan klik yang ditanam (dan set independen yang sama) dari o ( $\epsilon$$\epsilon k^2$simpul dalam grafik acaknsimpul lebih cepat darin O ( log n ) waktu. Orang dapat menunjukkan bahwa subgraf yang hanya sedikit lebih padat daripada rata-rata dapat digunakan untuk menemukan klik yang ditanam dalam waktu polinomial. Ini adalah bukti terhadap adanya algoritma waktu polinomial untuk varian masalah Anda untukkantaralogndan$o(\sqrt{n})$$n$$n^{O(\log n)}$$k$$\log n$ .$\sqrt{n}$

Referensi: Feige dan Krauthgamer. Menemukan dan mensertifikasi klik tersembunyi yang besar dalam grafik semi acak, 1999.