Klik masalah pada grafik tetap

Seperti kita ketahui, fungsi -clique C L I Q U E ( n , k ) mengambil subgraph ( spanning ) G ⊆ K n dari grafik n -vertex lengkap K n , dan menghasilkan 1 iff G berisi k -clique . Variabel dalam hal ini sesuai dengan tepi dari K n . Sudah diketahui (Razborov, Alon-Boppana) bahwa, selama 3 ≤ k ≤ n /$k$$CLIQUE(n,k)$$G\subseteq K_n$$n$$K_n$$1$$G$$k$$K_n$$3\leq k\leq n/2$, Fungsi ini membutuhkan sirkuit monoton ukuran sekitar . $n^k$

Tetapi bagaimana jika kita mengambil satu grafik tetap , dan mempertimbangkan fungsi boolean monoton C L I Q U E ( G , k ) , yang mengambil subset S ⊆ [ n ] dari simpul, dan menghasilkan 1 iff beberapa k simpul di S membentuk kelompok di G . Variabel dalam hal ini sesuai dengan simpul dari K n , dan fungsi ini hanya fungsi klik standar tetapi terbatas pada spanning$G\subseteq K_n$$CLIQUE(G,k)$$S\subseteq [n]$$1$$k$$S$$G$$K_n$subgraphs satu tetap graf .$G$

1. Apakah ada grafik -vertex G yang C L I Q U E ( G , k ) membutuhkan sirkuit monoton dengan ukuran lebih besar dari n O ( log n ) ? Saya rasa tidak. $n$$G$$CLIQUE(G,k)$$n^{O(\log n)}$

2. Apakah merupakan masalah NP-hard untuk beberapa urutan grafik ( G n : n = 1 , 2 ... ) ? Saya rasa tidak. $CLIQUE(G_n,k)$$(G_n\colon n=1,2\ldots)$

Perhatikan bahwa jika adalah semua klik maksimal dalam G , maka C L I Q U E ( G , k ) dapat dihitung sebagai OR dari fungsi r threshold- k , yang ke- i menguji apakah | S a ∩ C i | ≥ k . Jadi, jika r = p o l y ( n $C_1,\ldots,C_r$$G$$CLIQUE(G,k)$$r$$k$$i$$|S_a\cap C_i|\geq k$$r=poly(n)$, maka seluruh rangkaian berukuran polinomial. Tetapi bagaimana dengan grafik dengan jumlah eksponensial dari klik-klik maksimal? (Klik maksimal, tidak ada titik yang dapat ditambahkan.)

Dimungkinkan untuk "menanamkan" ke dalam C L I Q U E ( H , k ) untuk grafik H tertentu pada n = 2 m simpul. Secara khusus, Bollobas dan Thomason (1981) telah menunjukkan bahwa, jika H adalah grafik Hadamard yang simpulnya adalah himpunan himpunan bagian dari [ m ] , dan dua simpul u dan v berbatasan iff $CLIQUE(m,k)$$CLIQUE(H,k)$$H$$n=2^m$$H$$[m]$$u$$v$genap, maka H berisi salinan isomorfik dari setiap grafik G pada m simpul. Dapatkah fakta ini digabungkan dengan batas bawah Razborov (sekitar m k ) untuk C L I Q U E ( m , k ) untuk menyimpulkan bahwa C L I Q U E ( H , k ) memerlukan sirkuit monoton dengan ukuran sekitar m k ? Masalah potensial di sini adalah bahwa, meskipun grafik$|u\cap v|$$H$$G$$m$$m^k$$CLIQUE(m,k)$$CLIQUE(H,k)$$m^k$$H$"berisi" semua -vertex grafik, grafik ini tidak pada yang sama set simpul. Dan rquires argumen Razborov bahwa masukan positif dan negatif ( k -cliques dan melengkapi lengkap ( k - 1 ) grafik -partite) adalah grafik pada yang sama set simpul. Selain itu, semua input positif ( k -cliques) hanyalah salinan isomorfik dari satu dan k -clique tetap yang sama .$m$$k$$(k-1)$$k$ $k$

3. Ada ide? Adakah yang melihat jenis masalah seperti itu dipertimbangkan? Maksudku, masalah keputusan untuk subgraph dari grafik tetap . Atau, katakanlah, masalah SAT untuk sub-CNF dari satu CNF tetap (memuaskan) (diperoleh dengan menghapus beberapa literal)?

Motivasi: Masalah semacam ini berkaitan dengan kompleksitas algoritma optimasi kombinatorial. Tetapi mereka tampaknya menarik dalam diri mereka sendiri. Mengapa kita harus mencari algoritma yang efisien pada semua grafik? Pada kenyataannya, kita biasanya tertarik pada properti potongan kecil satu (besar) grafik (jaringan jalan-jalan di suatu negara, atau facebook, atau sejenisnya).

Catatan 1: Jika grafik adalah bipartit , maka matriks insiden vertex-edge dari ketidaksetaraan x u + x v ≤ 1 untuk semua ( u , v ) ∉ E benar-benar unimodular, dan satu dapat memecahkan masalah klik pada subgraph yang diinduksi G melalui pemrograman linier. Dengan demikian, untuk grafik bipartit G , C L I Q U E ( G , $G=(L\cup R,E)$$x_u+x_v\leq 1$$(u,v)\not\in E$$G$$G$ memilikisirkuit kecil (walaupun non-monoton). $CLIQUE(G,k)$

Komentar 2: Sebuah indikasi, bahwa dalam kasus grafik bipartit , jawaban atas Pertanyaan 1 "harus" memang TIDAK adalah bahwa permainan Karotmer-Wigderson monoton berikut pada G hanya membutuhkan O ( log n ) bit komunikasi. Misalkan k adalah jumlah terbesar dari simpul dalam subgraf bipartit G lengkap . Alice mendapat satu set A dari simpul merah, Bob satu set B dari simpul biru sedemikian rupa | A | + | B | > k . Tujuannya adalah untuk menemukan non-edge antara $G$$G$$O(\log n)$$k$$G$$A$$B$$|A|+|B|>k$$A$dan .$B$

$G$$k$$k$$n^{\Omega(k)}$

Anda dapat menemukan kertas Parameterized Complexity dari Prosedur Pencarian DPLL di tautan ini .

Saya yakin makalah ini dapat menjawab pertanyaan Anda: http://arxiv.org/abs/1204.6484

Makalah ini mendefinisikan keluarga masalah NP 3SAT keras, sehingga struktur formula ditetapkan untuk setiap n, dan input adalah polaritas formula.

Menggunakan reduksi standar dari 3SAT ke CLIQUE (masing-masing klausa 3CNF mendefinisikan satu set 8 kemungkinan penugasan (atau 7 penugasan yang memuaskan), dengan tepi di antara penugasan yang tidak bertentangan), terdapat grafik sehingga setelah menghapus satu simpul untuk setiap klausa, itu adalah NP sulit untuk menemukan klik maksimal (atau bahkan untuk memperkirakan ukurannya, menggunakan produk grafik atau produk grafik derandomized)

kembali Q3, ada beberapa pekerjaan empiris pada "backbone" dan kemungkinan "backdoors" dari masalah SAT. tulang punggung adalah himpunan literal yang benar dalam setiap tugas yang memuaskan. Backdoor ke masalah SAT adalah seperangkat variabel (mudah-mudahan kecil) yang menyediakan "jalan pintas" untuk memecahkan masalah. dua struktur ini mungkin akan membantu dan / atau kunci dalam memahami apa yang Anda sebut sebagai "sub-CNF" atau CNF dengan beberapa variabel dihapus. tetapi juga DP, algoritma davis putnam dapat dilihat secara sistematis mengeksplorasi banyak "sub-CNF" dari CNF untuk menyelesaikannya.

[1] Tulang Belakang dan Pintu Belakang dalam Kepuasan oleh Kilby et al