Masalah partisi tepi pada grafik kubik

Sudahkah kompleksitas masalah berikut dipelajari?

Input : grafik kubik (atau reguler) , batas atas alami$3$$G=(V,E)$$t$

Pertanyaan : apakah ada partisi menjadi bagian dari ukuran sehingga jumlah pesanan dari subgraph yang sesuai (belum terhubung) paling banyak ?$E$$|E|/3$$3$$t$

Pekerjaan terkait Saya menemukan beberapa makalah dalam literatur yang membuktikan kondisi yang diperlukan dan / atau cukup untuk keberadaan partisi ke dalam beberapa grafik yang mengandung tiga sisi, yang entah bagaimana terkait, dan beberapa yang lain tentang kompleksitas komputasi masalah masalah yang bersinggungan dengan di atas (misal, partisi harus menghasilkan subgraf isomorfik ke atau , dan tidak ada bobot yang dikaitkan dengan partisi yang diberikan), tetapi tidak ada yang benar-benar menangani masalah di atas.$K_{1,3}$$P_4$

Mendaftar semua makalah di sini akan sedikit membosankan, tetapi kebanyakan dari mereka mengutip atau dikutip oleh Dor dan Tarsi .

20101024: Saya menemukan makalah ini oleh Goldschmidt et al. , yang membuktikan bahwa masalah pemartisian tepi grafik menjadi bagian-bagian yang mengandung AT PALING edge, sedemikian rupa sehingga jumlah pesanan dari subgraph yang diinduksi paling banyak , adalah NP-lengkap, bahkan ketika . Apakah jelas bahwa masalahnya tetap NP-lengkap pada grafik kubik, ketika kita membutuhkan kesetaraan yang ketat ?$k$$t$$k=3$$k$

Informasi tambahan

Saya sudah mencoba beberapa strategi yang gagal. Lebih tepatnya, saya menemukan beberapa contoh tandingan yang membuktikan bahwa:

• memaksimalkan jumlah segitiga tidak mengarah pada solusi optimal; yang saya temukan entah bagaimana kontra-intuitif, karena segitiga adalah subgraph dengan urutan terendah di antara semua grafik yang mungkin pada tiga tepi;

• mempartisi grafik menjadi komponen-komponen yang terhubung tidak selalu menghasilkan solusi yang optimal. Alasan mengapa hal itu tampak menjanjikan mungkin kurang jelas, tetapi dalam banyak kasus orang dapat melihat bahwa menukar tepi untuk menghubungkan subgraph tertentu mengarah ke solusi dengan bobot yang lebih kecil (contoh: coba pada segitiga dengan satu tepi tambahan yang terhubung ke masing-masing vertex; segitiga adalah satu bagian, sisanya adalah kedua, dengan berat total 3 + 6 = 9. Kemudian bertukar dua sisi memberikan jalur dan bintang, dengan berat total 4 + 4 = 8.)

Berikut adalah saran untuk cara menunjukkan NP itu sulit. Saya tidak tahu apakah ini berhasil atau tidak. Pertama, pertimbangkan masalah yang sama pada multigraf. Kekerasan NP mungkin lebih mudah dibuktikan di sana. Coba kurangi dari CUT MAX kubik yang NP sulit bahkan untuk perkiraan (Berman dan Karpinski "Pada Beberapa Hasil Ketidakpastian Lebih Ketat"). Bagilah setiap sisi menjadi dua dan pada masing-masing simpul derajat-2 yang baru pasang simpul dengan loop-diri. Apakah partisi maksimum Anda sesuai dengan pemotongan maksimum?

-

Ini sedikit penjelasan.

(1) Masalah memaksimalkan (jumlah sumber + jumlah sink) atas semua orientasi grafik kubik terkait dengan MAXCUT oleh beberapa fungsi linier. Ini membutuhkan menunjukkan beberapa korersspondence antara pemotongan maksimum dan sumber-dan-tenggelam-orientasi maksimal Dalam satu arah, dalam pemotongan maksimum (U, V), kita dapat mengorientasikan semua tepi dari U ke V. Tepi internal E (U) membentuk pencocokan, sehingga ini dapat berorientasi secara sewenang-wenang dan serupa untuk E (V), dan jumlah total sumber dan bak cuci adalah beberapa fungsi linier dari ukuran potongan. Di arah lain, diberi orientasi sumber-dan-tenggelam-maksimal, partisi U = simpul dalam derajat 0 atau 1, V = simpul dalam derajat 2 atau 3 memberikan potongan.

(2) Dalam transformasi pembelahan-tepi yang saya jelaskan di atas, dalam konfigurasi optimal setiap loop diwarnai sama dengan tepi di sebelahnya, dan wlog tepi itu diwarnai sama dengan beberapa tepi (non-loop) lainnya di sebelah bahwa. Jadi setiap tepi yang terbelah memiliki satu warna yang berasal dari loop terlampir dan satu warna lainnya. Ini sesuai dengan orientasi dan (1) berlaku.