Apakah masalah k-klik NP-complete?

Dalam artikel Wikipedia ini tentang masalah Clique dalam teori graph, ia menyatakan di awal bahwa masalah menemukan klik ukuran K, dalam grafik G adalah NP-complete:

Klik juga telah dipelajari dalam ilmu komputer: menemukan apakah ada klik ukuran yang diberikan dalam grafik (masalah klik) adalah NP-lengkap, tetapi meskipun ini hasil kekerasan banyak algoritma untuk menemukan klik telah dipelajari.

Tetapi dalam artikel Wikipedia lainnya tentang masalah Clique di CS dikatakannya menyelesaikan masalah karena ukuran tetap k adalah masalah di P, bisa jadi kekerasan di masa polinomial.

Algoritma brute force untuk menguji apakah grafik G berisi k-vertex clique, dan untuk menemukan klik yang dikandungnya, adalah untuk memeriksa setiap subgraph dengan setidaknya k simpul dan memeriksa untuk melihat apakah itu membentuk klik. Algoritma ini membutuhkan waktu O (n ^ kk ^ 2): ada subgraph O (n ^ k) untuk diperiksa, yang masing-masing memiliki O (k ^ 2) tepi yang keberadaannya dalam G perlu diperiksa. Dengan demikian, masalah dapat diselesaikan dalam waktu polinomial setiap kali k adalah konstanta tetap. Ketika k adalah bagian dari input ke masalah, waktu adalah eksponensial.

Apakah ada sesuatu yang saya lewatkan di sini? Mungkin perbedaan dalam kata-kata masalah? Dan apa arti kalimat terakhir, bahwa "Ketika k adalah bagian dari input untuk masalah, bagaimanapun, waktunya eksponensial."? Mengapa ada perbedaan ketika k merupakan bagian dari input untuk masalah?

Ide saya adalah untuk menemukan klik ukuran k dalam grafik G, adalah bahwa kita pertama-tama memilih subset ukuran k dari node dari G, dan menguji apakah mereka semua terkait dengan node k lainnya, yang dapat dilakukan dalam konstanta waktu. Dan ulangi ini sampai kita memiliki klik ukuran k. Jumlah set k node yang dapat kita pilih dari G adalah n! / k! * (nk) !.

Hanya menguraikan apa yang ditunjukkan @Lamine: Ketika adalah bagian dari input, k dapat sebesar $k$$k$ , dalam hal jumlah potensi klik setyang setidaknya. Karenanya algoritma naif Anda akan membutuhkan waktuyang jelas eksponensial dalam panjang input. Versi parameterizedmana kita mencari-cliques dalamgrafik-vertex menangkap kekerasan masalah dalam bentuk yang paling umum karenaadalah bagian dari input. Karenanya algoritma poli-waktu untukjuga akan menyiratkan algoritma poli-waktu untuk setiaptertentu.$\frac{n}{2}$$\binom{n}{\frac{n}{2}}$$\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$$2^{\frac{n}{2}}$$|x|+|k|=n+\log n$$G(n,k)$$k$$n$$k$$G(n,k)$$k$