Algoritma

15

Masalah klik adalah masalah lengkap terkenal di mana ukuran klik yang diperlukan adalah bagian dari input. Namun, masalah k-clique memiliki algoritma waktu polinomial sepele ( ketika adalah konstan). Saya tertarik pada batas atas yang paling dikenal ketika k adalah konstan.NPO(nk)k

Apakah ada algoritma dengan run time ? Sebuah -waktu algoritma juga diterima. Juga, apakah ada konsekuensi kompleksitas-teoretis untuk keberadaan algoritma seperti itu?O(nk1)o(nk)

Mohammad Al-Turkistany
sumber

Jawaban:

20

Sebuah 3-klik dapat ditemukan dalam grafik -vertex G dalam waktu O ( n ω ) , di mana ω < 2.376 adalah eksponen perkalian matriks, dan dalam ruang O ( n 2 ) oleh hasil dari Itai dan Rodeh [1] . Pada dasarnya, mereka menunjukkan bahwa G mengandung segitiga jika dan hanya jika ( A ( G ) ) 3 memiliki entri tidak nol pada diagonal utamanya. Karena segitiga juga merupakan siklus C 3nGO(nω)ω<2.376O(n2)G(A(G))3C3, seseorang dapat menggunakan metode pencarian siklus umum untuk mendeteksi segitiga. Alon, Yuster dan Zwick menunjukkan bagaimana segitiga dapat dideteksi pada grafik -edge pada O ( m 2 ω / ( ω + 1 ) ) = O ( m 1,41 ) waktu [6].mO(m2ω/(ω+1))=O(m1.41)

Untuk waktu yang lama, hasil dari Nesetril dan Poljak [2] adalah yang paling dikenal; mereka menunjukkan jumlah klik ukuran dapat ditemukan dalam ruang O ( n ω k ) dan O ( n 2 k ) . Akhirnya, Eisenbrand dan Grandoni [3] meningkat pada hasil Nesetril dan Poljak untuk ( 3 k + 1 ) -clique dan a ( 3 k + 2 ) -clique untuk nilai kecil k . Secara khusus, mereka memberikan algoritma untuk menemukan klik ukuran 4, 5, dan 7 dalam waktu O3kO(nωk)O(n2k)(3k+1)(3k+2)k , O ( n 4.220 ) , dan O ( n 5.714 ) , masing-masing.O(n3.334)O(n4.220)O(n5.714)

kkkW[1]W[1]kklogn

GO(n+m)kO(n)


[1] Itai, Alon, dan Michael Rodeh. "Menemukan sirkuit minimum dalam grafik." Jurnal SIAM tentang Komputasi 7.4 (1978): 413-423.

[2] Nešetřil, Jaroslav, dan Svatopluk Poljak. "Tentang kerumitan masalah subgraph." Komentar Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

[3] Eisenbrand, Friedrich, dan Fabrizio Grandoni. "Pada kompleksitas klik parameter tetap dan set yang mendominasi." Ilmu Komputer Teoritis 326.1 (2004): 57-67.

[4] Downey, RG, dan Michael R. Fellows. "Fundamental kompleksitas Parameterized." Teks Tidak Lulusan dalam Ilmu Komputer, Springer-Verlag (2012).

[5] Feige, Uriel, dan Kilian, Joe. "On Limited versus Polinomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster, dan Uri Zwick. "Mencari dan menghitung siklus panjang yang diberikan." Algorithmica 17.3 (1997): 209-223.

Juho
sumber