Apakah masalah set vertex umpan balik dapat dipecahkan dalam waktu polinomial untuk grafik terikat 3 derajat?

19

Umpan Balik Vertex Set adalah NP-complete untuk grafik umum. Ini dikenal sebagai NP-lengkap untuk grafik terikat derajat-8 karena pengurangan dari penutup simpul. The artikel Wikipedia mengatakan bahwa itu adalah poli-waktu dipecahkan untuk gelar-3 grafik dibatasi dan NP-lengkap untuk gelar-4 grafik dibatasi. Tetapi saya belum dapat menemukan bukti untuk ini di mana saja. Apakah itu benar

Berapakah nilai minimum d sehingga FVS dalam grafik terikat derajat-d adalah lengkap-NP?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Davis Issac
sumber
1
Adakah yang tahu jika masalahnya sulit pada grafik 4 biasa tanpa diarahkan?

Jawaban:

10

Algoritma Li dan Liu tidak benar (diterbitkan di Cina, meskipun dalam bahasa Inggris). Algoritme Ueno et al. Benar, dan algoritma yang serupa dapat ditemukan di Furst et al. 1 . Kedua algoritma mengurangi masalah untuk masalah paritas matroid polinomial-solvable [3].

Pengurangannya dari VC memastikan NP-hardness untuk grafik terikat derajat-6! Karena VC sudah NP-hard pada grafik kubik. Speckenmeyer telah mengklaim bahwa tesisnya [4] berisi bukti NP-hardness FVS pada grafik planar tingkat maksimum empat, tetapi sangat sulit untuk menemukan (saya akan sangat menghargai jika siapa yang memiliki akses ke tesisnya dapat mengirim saya salinannya) ). Untungnya, bukti baru dari kekerasan NP dari derajat-empat grafik terikat dapat ditemukan di 2 :

Keterangan pada 2 : - Faktanya, dia membuktikan bahwa masalahnya adalah APX-hard, tetapi mudah untuk memverifikasi bahwa pengurangannya juga berlaku untuk bukti NP-hardness masalah. - Pengurangannya TIDAK berlaku untuk grafik planar.

  1. Merrick L. Furst, Jonathan L. Gross, dan Lyle A. McGeoch, "Menemukan grafik gen-maksimum yang tertanam," Journal of ACM, vol. 35, tidak. 3, hlm. 523–534, 1988. 10.1145 / 44483.44485
  2. Rizzi, R .: Basis siklus dasar yang lemah sulit ditemukan. Algorithmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
  3. László Lovász, "Masalah pencocokan matroid," dalam Metode Aljabar dalam Teori Grafik, ser. Colloquia Mathematica Societatis János Bolyai, vol. 25, Szeged, Hungaria, 1980, hlm. 495–517.
  4. Ewald Speckenmeyer, "Untersuchungen zum umpan balik mengatur masalah dalam ungerichteten graphen," tesis PhD, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.
Yixin Cao
sumber
9
Apakah ada alasan sederhana mengapa itu "jelas salah"?
Suresh Venkat
2
@ SureshVenkat Maaf atas jawaban yang terlambat: Saya baru saja memperhatikan pertanyaan ini. Kesalahan kritis adalah dalam Teorema 4.2, yang merupakan teorema utama dari makalah ini. Mengklaim bahwa diberi kedekatan pencocokan dan sepasang tepi { e 1 , e 2 } dalam adjacency cocok lebih besar M ' tapi tidak di M , mereka dapat meningkatkan M dengan menambahkan { e 1 , e 2 } untuk M . Ini jelas salah, karena definisi pencocokan adjacency membutuhkan penghapusan semua tepi pencocokan adjacency TIDAK memutus grafik.M{e1,e2}M′MM{e1,e2}M
Yixin Cao
terus ... Satu dapat dengan mudah mendapatkan yang cocok dengan hanya satu pasangan yang bertemu di titik v , dan pencocokan lain M ' dari dua pasang, salah satu yang menggunakan insiden tepi lain untuk v . Pasangan ini tidak dapat digunakan untuk meningkatkan M . Selain itu, Lemma 4.1 juga mengandung kesalahan kritis, tapi saya tidak ingat detailnya di lantai ini. (Saya mendeteksi mereka pada awal 2009, dan saya mencoba untuk menghubungi penulis segera, tetapi sayangnya saya tidak pernah mendapat jawaban.)MvM′vM
Yixin Cao
9

Referensi yang relevan tampaknya adalah:

Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya. Pada set masalah independen dan umpan balik mengatur masalah untuk grafik tanpa derajat simpul melebihi tiga. Prosiding Konferensi Jepang Pertama tentang Teori Grafik dan Aplikasi (Hakone, 1986). Matematika Terpisah. 72 (1988), no. 1-3, 355–360 .

Li, Deming; Liu, Yanpei. Algoritma polinomial untuk menemukan set simpul umpan balik minimum dari grafik sederhana 3-reguler. Acta Math. Sci. 19 (1999), no. 4, 375–381.

(Peringatan: Saya belum membaca keduanya tetapi mereka berdua mengklaim dapat menyelesaikan masalah dalam waktu polinomial. Saya tidak berpikir perbedaan antara 3-reguler dan maks tiga adalah penting untuk masalah ini.)

David Eppstein
sumber