Apakah vertex umpan balik mengatur masalah pada grafik derajat terbatas planar sulit?

Jawaban:

16

Menurut buku Garey dan Johnson Vertex Cover adalah NP-lengkap pada grafik planar maksimum empat derajat. Menggunakan reduksi sederhana dari Penutup Vertex ke Umpan Balik Set Vertex harus memberikan derajat delapan maksimum dan mempertahankan kerataan.

VC ke FVS: Ganti setiap tepi dengan segitiga (atau tepi ganda).

Satu catatan: Garey dan Johnson juga menyatakan bahwa FVS diarahkan adalah NP-lengkap pada planar diggrs dengan tidak ada in-atau out-degree melebihi dua. Mereka tidak secara khusus menyebutkan FVS yang tidak diarahkan berdasarkan pembatasan tersebut.

Stefan Kratsch
sumber
14

4

4

Batasan derajat adalah kemungkinan terbaik, karena FVS adalah polinomial untuk grafik derajat maksimum paling banyak tiga; lihat di sini .

Sunting: Ernst de Ridder's graphclasses.org sekarang berisi semua informasi yang tersedia tentang FVS; termasuk sekitar 550 kasus polinomi yang dapat dipecahkan dan sekitar 250 kasus NP-c.

vb le
sumber
tolong jelaskan lebih lanjut tentang pengurangan, yang jauh dari jelas dari saya. Saya tidak punya tesis Speckenmeyer (bahkan saya punya, saya tidak akan bisa mengerti bahasa Jerman). Tapi saya punya kertas yang Anda sebutkan, yang, bagaimanapun, hanya mengacu pada tesisnya. Di sisi lain, saya tahu bahwa itu NP-keras pada grafik umum tingkat maksimum 4, seperti yang ditunjukkan oleh Romeo Rizzi doi.org/10.1007/s00453-007-9112-8 . Terima kasih!
Yixin Cao
5

Menurut Wikipedia Garey & Johnson juga menunjukkan bahwa "Penutup Vertex tetap NP-lengkap ... bahkan dalam grafik planar derajat paling banyak 3."

Jadi FVS sulit pada grafik planar dengan derajat maksimum 6.

101011
sumber
2

Rupanya, dalam tesis Speckenmeyer PhD, ia menunjukkan bahwa masalah set vertex umpan balik adalah NP-hard untuk grafik tingkat maksimum 4. Klaim ini muncul di sini , misalnya.

n/2−z(G)+1nzz(G)G

Sunting: tidak memeriksa sunting vb le dengan cukup cermat ...

Timothy Sun
sumber