Implikasi dari masalah berada di XP ketika parameter oleh diameter

8

Biarkan menjadi masalah grafik NP-complete. Misalkan X dapat dipecahkan dalam waktu polinomial pada grafik dengan diameter terikat. Dengan kata lain, X yang diparameterisasi dengan diameter ada di XP. (Ingat masalah ada di XP jika bisa diselesaikan dalam waktu n f ( k ) ). Apakah ini menyiratkan solvabilitas di waktu XP untuk parameter menarik lainnya?XXXnf(k)

Jika ya, apakah mungkin ada beberapa atau lebih "daftar" standar atau web parameter dan bagaimana mereka berhubungan didokumentasikan di suatu tempat?

graph-theory parameterized-complexity fixed-parameter-tractable Juho
sumber

Jawaban:

10

Saya pikir Gambar 1 (halaman 4) dari makalah " Races Baru di Algoritma Parameterized " dari Komusiewicz dan Niedermeier adalah apa yang Anda cari.

Secara khusus, berada di XP untuk diameter parameter menyiratkan berada di XP untuk parameter: set dominasi min, set independen max, penutup clique minimum, jarak ke cograph, jarak ke co-cluster, jarak ke klik, jarak ke cluster, tutup vertex, dan pengeditan klaster.

Edouard Bonnet
sumber
Terima kasih banyak! Saya punya perasaan saya telah melihat sosok seperti ini sebelumnya, tetapi tidak dapat menemukannya. Orang mungkin ingin memperhatikan bahwa "derajat rata-rata" dapat ditambahkan pada gambar, dan dihubungkan dengan garis ke "degenerasi".
Juho
1

ISGCI baru saja menambahkan parameter. Mereka masih dalam versi beta pada saat penulisan, tetapi orang mungkin melihat diameter : set dominasi minimum adalah batas atas minimal, dan dengan mengikuti jejak ke atas, kita menemukan set independen maksimum, dan sebagainya.

Mereka merujuk misalnya naskah 2013 Sorge dan Weller, tersedia di sini (lihat Gambar 1).

Juho
sumber