Varian menarik dari masalah pencocokan maksimum

Diberikan grafik , masalah pencocokan maksimum klasik adalah memilih subset maksimum tepi st, untuk setiap tepi , .M ( u , v ) ∈ M d ( u ) = d ( v ) = $G(V,E)$$M$$(u,v) \in M$$d(u)=d(v)=1$

Adakah yang mempelajari varian berikut? Untuk setiap tepi , memegang, di mana c adalah a konstan. Kami menyebut batasan ini sebagai batasan derajat.( ( d ( u ) < c ) ∨ ( d ( v ) < c )$(u,v) \in M$$\left( \left(d(u) < c\right) \lor \left(d(v) < c\right) \right)$

Batasan klasik adalah konjungsi pada derajat dengan konstanta 1. Varian baru adalah disjungsi pada derajat dengan konstanta .$c$

Masalah pada $c=2$ sudah $NP-complete$ seperti yang ditunjukkan oleh Jukka Suomela. Saya tertarik pada algoritma perkiraan potensial. Algoritma serakah yang sederhana adalah memilih subgraph bintang maksimum secara iteratif hingga tidak ada subgraph bintang (yaitu, tidak ada tepi (bintang khusus)) yang dapat dipilih. Tetapi algoritma ini berkinerja buruk bahkan ketika $G$ adalah pohon ketika $c=3$ . Ada bintang dalam yang pusatnya memiliki derajat $x$ , dan ada $x$ bintang luar setiap pusat memiliki derajat $x$dan terhubung ke pusat bintang dalam. Nilai optimumnya adalah $2*x+(x-2)*(x-1)$ dengan memilih tepi $x-2$ dari masing-masing bintang terluar $x-2$ dan 2 bintang terluar lengkap. Nilai yang dihasilkan oleh algoritma greeedy adalah $x+1*x$ dengan memilih bintang dalam dan satu sisi dari setiap bintang luar.

Algoritma serakah di atas adalah $2\sqrt{n-1}$pendekatan n - 1 , di mana$n=|V|$. Saya ingin mencari algoritma aproksimasi yang lebih baik dari algoritma ini atau membuktikan kekerasan aproksimasi.

Selanjutnya, saya ingin tahu kelas kompleksitas masalah ini dalam kerangka kompleksitas parameterisasi. Mungkin dikenakan algoritma parameter tetap yang masuk akal.

Terima kasih banyak atas komentar dan jawaban Anda sebelumnya. :-)

(Sepertinya koneksi tidak sepenuhnya jelas, saya akan menulis versi panjang dari komentar di atas sebagai jawaban.)

Saya akan fokus pada kasus . Dalam hal ini, masalahnya dapat diulangi sebagai berikut:$c = 2$

• Biarkan menjadi grafik. Tugasnya adalah untuk menemukan ukuran maksimum M ⊆ E sedemikian rupa sehingga batasan berikut terpenuhi: untuk setiap { u , v } ∈ M , salah satu u adalah paling banyak 1 sisi dalam M , atau v adalah paling banyak 1 tepi dalam M , atau keduanya.$G = (V,E)$$M \subseteq E$$\{u,v\} \in M$$u$$1$$M$$v$$1$$M$

Setara:

• Subgraph yang diinduksi oleh harus memiliki properti yang semua tetangga dari simpul non-daun (derajat> 1) adalah simpul daun (derajat = 1).$M$

Setara:

• Subgraf yang diinduksi oleh terdiri dari bintang-bintang yang saling terpisah.$M$

Dalam apa yang berikut saya akan menginterpretasikan node yang tidak cocok (node ​​tidak terjadi pada setiap edge di ) sebagai bintang dengan 0 edge. Oleh karena itu solusi yang layak memecah sekumpulan node menjadi bintang-bintang yang saling terpisah.$M$

Sekarang jika jumlah bintang tersebut adalah , maka jumlah tepi dalam M persis n - k : ada simpul daun n - k yang terhubung ke pusat bintang. Oleh karena itu memaksimalkan jumlah tepi dalam M sama dengan meminimalkan kemudian jumlah bintang.$k$$M$$n-k$$n-k$$M$

Sekarang sangat mudah untuk melihat bahwa kita memiliki solusi dengan seperti bintang-bintang jika kita memiliki seperangkat ukuran yang mendominasi k :$k$$k$

1. Anggaplah kita diberi seperti bintang. Kemudian kita dapat menemukan kumpulan ukuran k yang mendominasi : cukup ambil pusat bintang-bintang (dalam bintang dengan 1 tepi Anda dapat memilih sebuah simpul secara sewenang-wenang).$k$$k$
2. Anggaplah kita diberi himpunan mendominasi dengan | D | = k . Maka kita hanya dapat menghubungkan setiap node dalam V ∖ D ke satu simpul di D . Tepi ini membentuk keluarga bintang k .$D$$|D| = k$$V \setminus D$$D$$k$

Oleh karena itu pemecahan masalah secara optimal dalam keluarga grafik tertentu adalah persis sekeras menemukan mendominasi set minimum dalam grafik keluarga yang sama F . Secara khusus, masalahnya adalah NP-hard bahkan dalam kasus grafik bipartit.$F$$F$

(Namun, hasil perkiraan (dalam) yang berhubungan dengan set yang mendominasi tidak dapat diterapkan secara langsung di sini. Pada dasarnya, kami telah mengubah fungsi tujuan dari ke max n - | D | .)$\min |D|$$\max n-|D|$