Dalam masalah Max-Cut , seseorang mencari subset S dari simpul dari grafik sederhana yang tidak diarahkan sedemikian rupa sehingga jumlah tepi antara S dan komplemen S adalah sebesar mungkin.
Max-Cut adalah APX-lengkap pada grafik derajat-terikat [PY91], dan pada kenyataannya APX-lengkap pada grafik kubik (yaitu grafik derajat 3) [AK00].
Max-Cut adalah NP-lengkap pada grafik bebas segitiga paling banyak 3 [LY80] (bebas segitiga berarti bahwa grafik input tidak mengandung K_3, grafik lengkap pada 3 simpul, sebagai subgraf).
Pertanyaan: Apakah Max-Cut APX-lengkap pada grafik bebas segitiga? (Catatan: derajat sewenang-wenang diizinkan)
Terima kasih.
UPDATE: Sebuah jawaban telah ditemukan, tetapi saya masih akan tertarik pada referensi untuk hasil ini, jika ada.
Referensi:
[AK00] P. Alimonti dan V. Kann: Beberapa hasil kelengkapan APX untuk grafik kubik. Teor Komputasi. Sci. 237 (1-2): 123-134, 2000. doi: 10.1016 / S0304-3975 (98) 00158-3
[LY80] JM Lewis dan M. Yannakakis: Masalah Penghapusan Node untuk Properti Turunan adalah NP-Lengkap. J. Comput. Syst. Sci. 20 (2): 219-230, 1980. doi: 10.1016 / 0022-0000 (80) 90060-4
[PY91] CH Papadimitriou dan M. Yannakakis: Kelas Optimasi, Perkiraan, dan Kompleksitas, J. Comput. System Sci., 43 (3): 425-440, 1991. doi: 10.1016 / 0022-0000 (91) 90023-X
Jawaban:
Ya, dengan pengurangan dari MaxCut ke MaxCut bebas segitiga. Inilah yang oleh Wikipedia disebut pengurangan-L
Diberikan instance dari Max-Cut, buat 3-stretch dengan membagi setiap sisi menjadi tiga sisi. Kemudian urutan pemotongan maksimum adalah urutan pemotongan maksimum ditambah dua kali jumlah tepi di . Karena ukuran pemotongan maksimum selalu setidaknya setengah dari jumlah tepi, rasio kesalahan hanya bertambah buruk dengan faktor konstan.G G′ G′ G G
sumber