Apa kompleksitas dari masalah peliputan ini?

Sunting: Saya pertama kali salah mengartikan kendala saya (2), sekarang sudah diperbaiki. Saya juga menambahkan lebih banyak informasi dan contoh.

Dengan beberapa rekan, mempelajari beberapa pertanyaan algoritmik lainnya, kami dapat mengurangi masalah kami menjadi masalah menarik berikut, tetapi kami tidak dapat menyelesaikan pertanyaan tentang kompleksitasnya. Masalahnya adalah sebagai berikut.

Instance: Integer $n$ , integer $k<n$ , dan himpunan $S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$ dari $n$ pasangan dari set $\{1,\ldots,n\}$ .

Pertanyaan: Apakah ada himpunan $S'\subseteq S$ dengan ukuran $k$ sedemikian sehingga untuk setiap elemen $i$ dari $\{1,\ldots,n\}$ :
(1) jika $i<n$ , interval $[i,i+1]$ dimasukkan dalam beberapa interval $[s_i,t_i]$ didefinisikan oleh pasangan di , dan (2) setidaknya satu dari , milik beberapa pasangi$S'$
$i$$i+1$$S'$?
(2) milik sepasang .$i$$S'$

Contoh
Himpunan adalah solusi yang layak (dengan asumsi adalah genap): pasangan memastikan kondisi (1), sedangkan semua pasangan lain memastikan kondisi (2).$\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$$n$$\{1,n\}$

Keterangan
(I) Karena setiap pasangan mengandung tepat dua elemen, untuk memenuhi kondisi (2), kita memerlukan setidaknya pasangan. BTW ini menyiratkan pendekatan 2 sepele dengan mengembalikan seluruh , karena kita menganggap .$\frac{n}{2}$$S$$|S|\leq n$

(II) Cara lain untuk melihat masalah adalah dengan mempertimbangkan tangga dengan langkah (seperti yang di bawah ), bersama dengan himpunan dari siklus tangga. Setiap langkah tangga sesuai dengan beberapa elemen, dan setiap tepi sisi adalah interval . Sebuah siklus termasuk langkah sesuai persis dengan pasangan : ia mencakup semua interval berturut-turut antara dan , dan berhenti di kedua dan . Pertanyaannya kemudian apakah ada himpunan dari$n$$S$$n$$[i,i+1]$$s,t$$\{s,t\}$$s$$t$$s$$t$
$S'\subseteq S$$k$siklus yang penyatuannya mencakup semua tepi tangga (termasuk tepi step dan tepi samping).

(III) Jika seseorang hanya meminta kondisi (1), masalahnya akan sesuai dengan masalah himpunan mendominasi dalam beberapa grafik interval yang ditentukan dari interval diberikan oleh pasangan bersama-sama dengan interval kecil tambahan untuk setiap di . Masalah ini dapat dipecahkan secara klasik dalam waktu linier (lihat misalnya di sini ). Demikian pula, jika seseorang hanya meminta kondisi (2), ini dapat dikurangi menjadi masalah penutup tepi (simpul adalah elemen, tepi adalah pasangan), yang juga waktu polinomial dipecahkan dengan pendekatan pencocokan maksimum.$[s_i,t_i]$[ i + ϵ , i + 1 - ϵ ] i { 1 , … , n - 1 $S$$[i+\epsilon,i+1-\epsilon]$$i$$\{1,\ldots, n-1\}$

Jadi pertanyaan saya ada pada judul:

Apakah masalah ini dalam P? Apakah ini NP-lengkap?

Referensi apa pun untuk masalah yang serupa dipersilahkan.

Meskipun ini tidak menyelesaikan pertanyaan yang Anda ajukan, beberapa komentar sebelumnya mempertimbangkan algoritma perkiraan. FWIW, saya pikir PTAS (skema pendekatan poli-waktu) dimungkinkan menggunakan pemrograman dinamis. Inilah idenya.

Diberikan contoh apa saja dan , buat solusi sebagai berikut. Tandai setiap simpul ( 1 / ϵ ) . Untuk setiap simpul bertanda i , dari semua tepi ( j , k $\epsilon > 0$$(1/\epsilon)$$i$$(j,k)$ yang "span" (yaitu, yang memenuhi kendala (1) untuk i ), pilih satu tepi yang meminimalkan j dan yang meminimalkan memaksimalkan k . Tambahkan 2 ε n tepi untuk solusi.$i$$i$$j$$k$$2 \epsilon n$

Tepi-tepi ini memenuhi batasan tipe (1) untuk banyak simpul. Sementara itu mereka berkontribusi edge ke solusi, yang hanya O ( ϵ OPT ) . Untuk menyelesaikannya, kami akan menemukan solusi optimal untuk masalah yang tersisa dalam menemukan serangkaian tepi yang memenuhi semua batasan tipe (1) dan tipe (2) yang tersisa.$2n\epsilon$$O(\epsilon \mbox{OPT})$

Tentukan "blok" simpul menjadi satu set simpul berturut-turut yang tipe (1) batasannya dipenuhi oleh tepi yang ditambahkan sejauh ini. Di antara dua blok berturut-turut, ada urutan simpul yang tipe (1) batasannya tidak terpenuhi. (Setiap urutan seperti itu memiliki panjang paling banyak , karena simpul yang ditandai memiliki jenis mereka (1) kendala bertemu dengan tepi sudah ditambahkan.) Panggil urutan seperti itu "lingkungan" dari dua blok yang berdekatan (sehingga setiap blok memiliki lingkungan di sebelah kiri dan lingkungan di sebelah kanan).$1/\epsilon$

Di dalam setiap lingkungan, untuk setiap simpul di lingkungan tersebut, setiap tepi yang meninggalkan puncak memiliki jarak paling banyak (karena tepi tidak menjangkau titik yang ditandai). Dengan demikian, simpul memiliki derajat paling banyak 1 / ϵ . Dengan demikian, setiap lingkungan memiliki paling banyak 1 / ϵ simpul dan menyentuh paling banyak 1 / ϵ 2 tepi. Panggil subset dari tepi tersebut sebagai "konfigurasi" lingkungan. Jika konfigurasi memenuhi semua batasan tipe (1) dan tipe (2) untuk simpul di lingkungan, panggil konfigurasi "valid".$1/\epsilon$$1/\epsilon$$1/\epsilon$$1/\epsilon^2$

Untuk setiap blok , untuk setiap pasangan ( C i , C i + 1 ) konfigurasi yang valid dari dua lingkungan blok, menghitung (dalam waktu polinomial, menggunakan pencocokan maksimum dll), ukuran minimum F i ( C i , C i + 1 ) dari setiap himpunan S dari tepi (jika ada) sehingga tepi dalam C i ∪ S ∪ C i + 1 memenuhi jenis (2) kendala untuk simpul dalam blok. Karena ada paling banyak 2 $i$$(C_i, C_{i+1})$$F_i(C_i,C_{i+1})$$S$$C_i\cup S \cup C_{i+1}$konfigurasi, ini dapat dilakukan dalam waktu polinomial (untuk eps tetap). $2^{1/\epsilon^2} = O(1)$

Sekarang Anda dapat memecahkan contoh asli dengan menemukan urutan konfigurasi berlaku, satu untuk setiap lingkungan, yang meminimalkan Σ i | D i | + F i ( D i , D i + $D_1, D_2, .., D_k$ , di mana F i adalah seperti yang didefinisikan dalam paragraf sebelumnya. Ini dapat dilakukan dengan menemukan jalur terpendek dalam grafik yang dibentuk oleh semua konfigurasi yang valid, dengan keunggulan biaya | D i | $\sum_i |D_i| + F_i(D_i, D_{i+1})$$F_i$ dari setiap konfigurasi D i untuk lingkungan i ke setiap konfigurasi D i + 1 untuk lingkungan i + 1 . (Grafik ini memiliki ukuran O ( 2 1 / ϵ 2 n ) , yaitu O ( n ) untuk diperbaiki ϵ .)$|D_i| + F_i(D_i, D_{i+1})$$D_i$$i$$D_{i+1}$$i+1$$O(2^{1/\epsilon^2} n)$$O(n)$$\epsilon$