Biopsi monoton antara daftar interval

10

Saya memiliki masalah berikut:

Input: dua set interval dan T (semua titik akhir adalah bilangan bulat). Pertanyaan: adakah bijih monoton f : S T ?ST
f:ST

Bijection adalah monoton wrt set masuknya order pada dan T . X Y S , f ( X ) f ( Y )ST

XYS, f(X)f(Y)

[Saya tidak membutuhkan kondisi sebaliknya di sini. Pembaruan: jika kondisi sebaliknya diperlukan, yaitu, , maka ini akan berada di PTIME karena merupakan pengujian isomorfisme dari pos inklusi terkait (yang memiliki memesan dimensi 2 melalui konstruksi), yang ada di PTIME oleh Möhring, Kelas yang Dapat Diterapkan Secara Komputasi dari Set Pesanan , Teorema 5.10, hlm. 61.X,Y,XYf(X)f(Y) ]

Masalahnya adalah dalam : kita dapat memeriksa secara efisien jika f yang diberikan adalah bijih monoton.NPf

Apakah ada algoritma waktu polinomial untuk masalah ini? Atau apakah -hard?NP

Pertanyaannya dapat dinyatakan secara lebih umum sebagai keberadaan penambangan monoton antara dua poset yang diberikan dari dimensi pesanan 2.

Menggunakan reduksi yang diilhami oleh jawaban atas pertanyaan ini , saya tahu bahwa masalahnya adalah -hard ketika dimensi tidak dibatasi. Namun, tidak jelas apakah pengurangan juga akan berfungsi ketika dimensi dibatasi.NP

Saya juga tertarik untuk mengetahui tentang traktabilitas ketika dimensi hanya dibatasi oleh konstanta arbitrer (bukan hanya 2).

a3nm
sumber
S I1,I2,...,Inn+1IiIj(IjIi)IiIj1,...,Ijm|Ij1|=|Ij2|=...=|Ijm|(IjkIi)T
2
Interval dapat dimasukkan dalam beberapa interval yang tak tertandingi, misalnya [2, 3] termasuk dalam [1, 3] dan [2, 4], jadi saya pikir konstruksi pohon Anda tidak akan menghasilkan pohon tetapi grafik asiklik langsung. Memeriksa apakah dua DAG bersifat isomorfik (atau lebih tepatnya dapat disematkan dalam arti yang saya tanyakan) adalah NP-hard secara umum, saya pikir.
a3nm
Anda benar, pendekatan di atas tidak benar!
Marzio De Biasi
X,Y,XYf(X)f(Y)
@ MohammadAl-Turkistany: lih diskusi dalam komentar tentang jawaban Marzio
a3nm

Jawaban:

8

Berikut adalah upaya untuk membuktikan bahwa masalah tanpa kondisi sebaliknya adalah NP-hard.

S

 [S]  +-a-+ +-b-+
      +---c-----+  c<a, c<b (here < is interval inclusion)

T

 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+    
      +-z-----+  z<x, z<y OK

3mA={a1,a2,...,a3m}BmA1,...,AmAiB

max=ai+3m

S3m BIi3maxmaxBIiaiLBIi (garis biru pada gambar).

TLm GjGjB

Anggaplah ada suatu bijih antara S dan T yang mempertahankan inklusi interval (dalam satu arah dari S ke T).

maxBIj1,BIj2,BIj3SGjBIjkGj

Dengan cara yang sama dapat dibuktikan bahwa jika ada suatu bijidasi maka masalah 3-partisi unary asli memiliki solusi.

masukkan deskripsi gambar di sinim=2,A={3,3,2,2,2,2},B=7

Catatan: seperti yang diamati dalam komentar, interval biru L dalam S dan T tidak penting untuk reduksi.

IiIj(IjIi)

Marzio De Biasi
sumber
Ya, sepertinya ini benar, terima kasih banyak! (Hanya sebuah komentar: interval biru tidak diperlukan untuk membuat pengurangan bekerja, saya pikir.) Saya akan menerima segera kecuali saya menemukan alasan untuk meragukan bahwa pengurangan ini berfungsi.
a3nm
@ A3nm: ya tapi saya menemukannya setelah menggambar angka :-). Saya masih belum 100% yakin bahwa tidak ada kesalahan tersembunyi dalam pengurangan (lebih jauh lagi ini adalah kedua kalinya dalam dua minggu saya menemukan bukti NP-lengkap yang menggunakan 3-partisi unary ... sangat aneh :-)
Marzio De Biasi
Tidak, tampaknya benar: jelas solusi untuk 3-partisi menghasilkan solusi untuk masalah interval. Sekarang, beralih dari masalah interval ke 3-partisi: tentu saja pemetaan interval memetakan interval merah ke interval merah (karena piramida penanda); jumlah interval merah yang sama sehingga intervalnya merah jika gambar dengan pemetaan. Marka dipetakan ke interval merah yang tepat (karena kalau tidak itu adalah keturunan, dan minimal). Sekarang jika merah dipetakan menjadi merah dan marka dipetakan seperti yang diharapkan, angkanya harus sesuai, jadi kita memiliki partisi yang benar. Saya pikir itu masuk akal!
a3nm
@ a3nm: Saya melihat Anda menerima jawabannya; Menurut Anda, apakah hasilnya cukup menarik untuk menulis makalah bersama?
Marzio De Biasi
Tf