Kompleksitas k-klik untuk hypergraphs

Masalah Klasik:

Biarkan nomor diberikan. Masalah -clique adalah sebagai berikut. $k$ $k$

Diberikan grafik , apakah ada subset dari simpul sehingga setiap dua simpul berdekatan? $G$ $S$ $k$ $S$

Masalah Hypergraph:

Biarkan angka dan diberikan. Masalah -hyperclique adalah sebagai berikut. $c$ $k$ $(c,k)$

Mengingat -uniform hipergraf , apakah di sana ada satu set dari simpul sehingga setiap bagian dari simpul dari membentuk hyperedge a. $c$ $H$ $S$ $k$ $c$ $S$

Pertanyaan:

(1) Apa algoritma yang paling dikenal untuk memecahkan -perclique? $(c,k)$

(2) Apa kompleksitas waktunya?

(3) Apakah ada hubungan antara -hperclique dan multiplikasi matriks? $(c,k)$

Yang saya tahu, ini mungkin masalah yang dipelajari dengan baik. Referensi apa pun yang menyelidiki masalah ini sangat dihargai.

cc.complexity-theory graph-theory matrices clique fixed-parameter-tractable Michael Wehar
sumber

Mungkin layak untuk menunjukkan yang jelas: Karena kita memahami kasus , masalahnya adalah NP-lengkap dan bukan FPT dalam hal (tetapi FPT dalam hal ). Lebih lanjut (masih jelas), Anda dapat menguraikan kembali masalah sebagai pemilihan baris dari matriks kejadian sedemikian sehingga dalam submatrix pada baris ini, kolom memiliki jumlah .

c = 2

$c=2$

c

$c$

k

$k$

k

$k$

(\binom{k}{c})

$k\choose c$

c

$c$

Andrew D. King

Ini biasanya diutarakan dalam hal menemukan himpunan independen- dalam hypergraph seragam. Lihat kertas 2006 Yuster ini research.haifa.ac.il/~raphy/papers/counthyper.pdf untuk beberapa petunjuk yang berguna (termasuk hubungan dengan perkalian matriks).

k

$k$

c

$c$

András Salamon

@ AndrewD.King, saya tidak mengerti apa yang Anda maksud dengan "tetapi adalah FPT dalam hal k", k-klik adalah W [1] -begit dalam hal k. Dan OP: K-Clique sudah sulit, tetapi pertanyaan Anda bukanlah pertanyaan tingkat penelitian yang baik, seperti membandingkannya dengan masalah polinomial.

Saeed

Terima kasih untuk informasi. Saya paling tertarik pada apakah ada beberapa dan sehingga -hperclique ada di . Kita tahu bahwa untuk , -clique dapat diselesaikan di .

c > 2

$c>2$

k > 2

$k>2$

(c, k)

$(c,k)$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

k > 2

$k>2$

k

$k$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

Michael Wehar

Jadi Anda tahu tidak ada n ^ o (k) untuk klik dan terkait dengan multiplikasi matriks yang Anda maksud bukan pengurangan ap tetapi hanya mengurangi waktu berjalan, sekarang lebih jelas bagi saya, saya tidak tahu tentang itu tetapi mungkin Anda perlu untuk memasukkan c ke dalam eksponen juga.

Saeed

Jawaban:

Tidak diketahui apakah ada , , dan sedemikian rupa sehingga hyperclique berada dalam waktu . Perhatikan bahwa kasus sepele. Selama bertahun-tahun saya telah mengomunikasikan masalah ini kepada banyak orang, dan mengajarkannya di cs266 di Stanford, karena hubungannya dengan pemecahan -Sat. (Beberapa sesi masalah terbuka di lokakarya mungkin mencatat ini.) Berikut adalah beberapa hal yang saya tahu: $\varepsilon > 0$ $c > 2$ $k > c$ $(c,k)$ $n^{k-\varepsilon}$ $k \leq c$ $k$

Saya membuktikan beberapa tahun yang lalu bahwa menyelesaikan pada grafik node dalam waktu menyiratkan hyperclique dalam waktu . Belum menerbitkannya. $4-cycle$ $n$ $n^{2-\varepsilon}$ $(3,4)$ $n^{4-\varepsilon}$

UPDATE (Agustus 2019) hasil yang disebutkan di atas dan beberapa generalisasi sekarang muncul di koran

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams: Kekerasan Ketat untuk Siklus dan Jalur Terpendek dalam Grafik Jarang . SODA 2018: 1236-1252

Jika Anda dapat menyelesaikan hyperclique seperti yang ditunjukkan di atas, maka Max-3-Sat dapat diselesaikan dalam waktu kurang dari kali. Demikian pula, pemecahan hyperclique akan menghasilkan algoritma -Sat yang lebih cepat . Jadi jika Anda percaya Strong ETH maka ada batas yang jelas di sini. Pengurangan adalah generalisasi alami dari pengurangan dari Max-2-Sat ke temuan segitiga ( klik) dari ICALP'04 dan tesis PhD saya. $(3,4)$ $2^n$ $(k,k+1)$ $k$ $(2,3)$

Anda dapat menyelesaikan hyperclique dalam waktu waktu dengan menggeneralisasi kertas Algoritma Efisien untuk Masalah Klik . $(c,k)$ $n^k/(\log n)^{\Omega(k)}$

Ryan Williams
sumber

Ryan terima kasih! Saya menghargai jawaban Anda dan membagikan makalah tentang masalah klik. :)

Michael Wehar

Apakah 5 siklus lebih sulit daripada 4 siklus?

Michael Wehar

Sejauh yang kami tahu, 3-siklus lebih sulit. Kasing ganjil secara umum membutuhkan waktu O (n ^ {2.373}), kasing membutuhkan waktu O (n ^ 2) untuk siklus panjang tetap. Lihat misalnya, Yuster dan Zwick, Menemukan siklus bahkan lebih cepat.

Ryan Williams

Oh wow! Cukup menarik. Oke terima kasih. :)

Michael Wehar

Keren! Terima kasih atas referensi yang diperbarui.

Michael Wehar