Biopsi monoton antara daftar interval

Saya memiliki masalah berikut:

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

Bijection adalah monoton wrt set masuknya order pada dan . $S$ $T$

\forall X \subseteq Y \in S, f (X) \subseteq f (Y)

$\forall X\subseteq Y \in S, \ f(X) \subseteq 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. $\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$ ]

Masalahnya adalah dalam : kita dapat memeriksa secara efisien jika diberikan adalah bijih monoton. $\mathsf{NP}$ $f$

Apakah ada algoritma waktu polinomial untuk masalah ini? Atau apakah -hard? $\mathsf{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. $\mathsf{NP}$

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

cc.complexity-theory ds.algorithms np-hardness partial-order matching a3nm
sumber

S

$S$

I_{1}, I_{2}, . . ., I_{n}

$I_1,I_2,...,I_n$

n + 1

$n+1$

I_{i} \subseteq I_{j}

$I_i \subseteq I_j$

(I_{j} \to I_{i})

$(I_j \rightarrow I_i)$

I_{i} \subseteq I_{j_{1}}, . . ., I_{j_{m}}

$I_i \subseteq I_{j_1},...,I_{j_m}$

| I_{j_{1}} | = | I_{j_{2}} | = . . . = | I_{j_{m}} |

$|I_{j_1}|=|I_{j_2}|=...=|I_{j_m}|$

(I_{j_{k}} \to I_{i})

$(I_{j_k} \rightarrow I_i)$

T

$T$

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

\forall X, Y, X \subseteq Y \Leftrightarrow f (X) \subseteq f (Y)

$\forall X, Y, X\subseteq Y \Leftrightarrow f(X) \subseteq f(Y)$

@ MohammadAl-Turkistany: lih diskusi dalam komentar tentang jawaban Marzio

a3nm

Jawaban:

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

$3m$ $A = \{a_1,a_2,...,a_{3m}\}$ $B$ $m$ $A_1,...,A_m$ $A_i$ $B$

$max = \sum a_i + 3m$

$S$ $3m$ $BI_i$ $3*max$ $max$ $BI_i$ $a_i$ $L$ $BI_i$ (garis biru pada gambar).

$T$ $L$ $m$ $G_j$ $G_j$ $B$

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

$max$ $BI_{j_1},BI_{j_2},BI_{j_3}$ $S$ $G_j$ $BI_{j_k}$ $G_j$

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

masukkan deskripsi gambar di sini $m=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.

$I_i \subseteq I_j$ $(I_j \rightarrow I_i)$

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

T

$T$

f

$f$