Gagasan utama jawabannya: jika kita mengurangi instance Independent Set yang diparameterisasi menjadi Vertex Cover yang diparameterisasi, maka parameter yang kita dapatkan tergantung pada ukuran grafik, dan tidak hanya bergantung pada parameter input. Sekarang untuk lebih detail.
Seperti yang Anda ketahui, masalah parameterized berada dalam (seragam) FPT jika ada algoritma yang memutuskan apakah input ( x , k ) terkandung dalam Q dalam waktu f ( k ) | x | O ( 1 ) untuk beberapa fungsi f .Q(x,k)Qf(k)|x|O(1)f
Karena Anda dapat memutuskan apakah grafik memiliki penutup sudut ukuran k dengan memilih tepi, dan bercabang di mana dari dua titik akhir untuk dimasukkan ke dalam penutup simpul, percabangan ini hanya berjalan dalam k (jika Anda sudah meletakkan lebih dari k simpul dalam penutup), dan mudah berjalan dalam waktu O ( 2 k n 2 ) ; karena itu k -Vertex Cover ada di FPT.GkkkO(2kn2)k
Sekarang misalkan kita ingin mencoba menggunakan algoritme ini untuk menunjukkan bahwa Independent Set yang diparameterisasi ada di FPT; anggap kita diberi grafik pada n simpul dan ingin memutuskan apakah ia memiliki seperangkat ukuran independen ℓ . Ini sama dengan menanyakan apakah G memiliki penutup simpul ukuran n - ℓ . Jadi kita menggunakan algoritma di atas kami untuk menghitung jawaban di O ( 2 n - ℓ n 2 ) waktu. Untuk algoritma FPT kami, fungsi eksponensial dalam waktu berjalan mungkin tergantung pada parameter, yaitu ℓ , tetapi mungkin TIDAK tergantung pada ukuran input, yang merupakan nGnℓGn−ℓO(2n−ℓn2)ℓn; tetapi pendekatan yang kami sketsa menggunakan eksponensial waktu dalam dan karenanya bukan merupakan parameter FPT berkenaan dengan parameter ℓ . Inilah sebabnya mengapa Vertex Cover berada di FPT tidak menyiratkan bahwa Independent Set berada di FPT.n−ℓℓ
Saya tidak akan mengatakan bahwa 'sifat' dari masalah itu berubah, apa pun maksudnya. Semua yang berubah adalah parameter, yaitu cara Anda mengukur tingkat kesulitan masalah.
Grafik yang memiliki ukuran penutup simpul paling banyak adalah sangat terstruktur sehingga memungkinkan untuk secara efisien menguranginya dalam ukuran: Kita dengan rakus dapat menemukan pencocokan ukuran maksimal paling banyak k dan sisa grafik adalah seperangkat ukuran independen setidaknya n - 2 k . Menggunakan aturan reduksi seperti reduksi mahkota, jumlah simpul dapat dikurangi hingga paling banyak 2 k .k k n−2k 2k
Di sisi lain, grafik yang memiliki ukuran simpul puncak paling banyak (atau ekuivalen, independen maksimum memiliki ukuran setidaknya k ) tampaknya tidak memiliki struktur yang sederhana. Ini bisa dibuat tepat, seperti yang Anda tunjukkan: strukturnya memungkinkan kita untuk menyandikan masalah W [ 1 ] apa pun .n−k k W[1]
sumber
Berikut ini mungkin memberikan intuisi untuk perbedaannya. Subset dari simpul S adalah penutup simpul G = (V, E) jika dan hanya jika VS adalah set independen, jadi jika MVC adalah ukuran penutup simpul minimum maka MIS = | V | -MVC adalah ukuran set independen maksimum. Algoritma FPT yang diparameterisasi oleh X memungkinkan runtime eksponensial sebagai fungsi X. Grafik acak pada n simpul dengan probabilitas tepi setengahnya memiliki MIS probabilitas tinggi tentang ukuran 2logn dan MVC ukuran tentang n-2logn. Jadi, setidaknya untuk grafik ini, algoritma FPT yang diparameterisasi oleh MVC hanya memungkinkan lebih banyak waktu daripada satu yang diparameterisasi oleh MIS.
sumber
Meskipun saya setuju dengan apa yang dikatakan orang lain, cara lain yang saya temukan bermanfaat ketika memikirkan hal-hal ini adalah menyusun kembali masalah sebagai masalah pengenalan, yaitu "Apakah grafik input termasuk dalam keluarga grafik yang paling banyak memiliki penutup simpul paling banyak k?" / "Apakah grafik input termasuk dalam kelompok grafik yang memiliki set independen paling tidak k?".
Secara intuitif, kelompok grafik yang lebih terbatas harus lebih mudah dikenali daripada grafik yang lebih kaya dan lebih umum. Kelompok grafik penutup vertex paling banyak k sangat terbatas, pada kenyataannya setiap grafik tersebut dapat digambarkan hanya dengan menggunakan bit , yang jauh lebih sedikit dari biasanya O ( n 2 ) bit yang dibutuhkan , dengan asumsi bahwa k secara signifikan lebih kecil dari n. Kelompok grafik set independen setidaknya k di sisi lain sangat kaya: grafik apa pun dapat diedit menjadi miliknya dengan menghapus paling banyak k 2 edge.O(k2+2klogn) O(n2) k2
Jadi bagi saya ini adalah salah satu penjelasan intuitif mengapa saya berharap akan lebih mudah untuk mengenali tutup vertex kecil daripada set independen kecil. Tentu saja harus jelas bahwa pemikiran di atas tidak mendekati argumen formal dan saya kira pada akhirnya bukti yang paling meyakinkan bahwa memang lebih sulit untuk mengenali seperangkat ukuran independen k sama persis dengan kekerasan independen set!
sumber
Ini adalah jawaban yang sangat tidak langsung, dan mungkin tidak cukup menjawab kekhawatiran Anda. Tetapi FPT dan hirarki W terkait erat dengan aproksibilitas (masalah FPT sering memiliki PTASs dll). Dalam konteks itu, perhatikan bahwa untuk grafik apa pun, VC = n - MIS, dan perkiraan untuk VC tidak memberikan perkiraan untuk MIS. Inilah sebabnya mengapa Anda perlu pengurangan L untuk perkiraan. Saya menduga ada gagasan "pengurangan pelestarian kernel" yang setara untuk kompleksitas parameterisasi juga.
sumber