Pertanyaan tentang ekstensi linear pesanan parsial

Jika Anda diberi koleksi pesanan parsial, jenis topologi akan memberi tahu Anda jika ada perpanjangan koleksi ke pesanan total (ekstensi dalam hal ini adalah pesanan total yang konsisten dengan masing-masing pesanan parsial).

Saya menemukan variasi:

Perbaiki satu set . Anda diberikan urutan elemen yang diambil dari tanpa pengulangan (urutannya panjang antara 1 dan ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

Apakah ada cara untuk memperbaiki orientasi untuk masing-masing urutan (baik maju atau mundur) sehingga koleksi rantai yang dihasilkan (dilihat sebagai urutan parsial) menerima perpanjangan?

Apakah masalah ini sudah diketahui?

Catatan: Orientasi dipilih untuk seluruh urutan. Jadi, jika urutannya , Anda bisa tetap seperti itu, atau membalik ke , tetapi Anda tidak bisa melakukan hal lain. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
sumber

Jika masing-masing urutan memiliki panjang maka seseorang dapat menganggap setiap urutan sebagai tepi yang tidak terarah dan kami bertanya apakah grafik yang tidak diarahkan dapat berorientasi menjadi DAG - jika jika tidak ada siklus. Tetapi algoritma serakah juga bekerja. Mulailah dengan tepi dan orientasikan secara sewenang-wenang dan teruskan selama Anda bisa dan jika Anda buntu Anda tahu itu tidak mungkin. Apakah Anda mencobanya untuk variasi Anda? Sepertinya itu mungkin berhasil.

2

$2$

Chandra Chekuri

Eh, setiap grafik yang tidak diarahkan dapat berorientasi menjadi DAG. Pilih saja urutan simpul dan gunakan urutan itu untuk mengorientasikan tepi.

David Eppstein

Anda benar tentu saja, saya tidak berpikir jernih.

Chandra Chekuri

Dalam variasi saya, setiap baris memiliki panjang tepat 4, jadi jawaban Yury muncul. Satu-satunya harapan saya pada saat ini adalah bahwa rangkaian berikutnya memiliki struktur yang sangat istimewa dan terkait satu sama lain, jadi mungkin sesuatu yang spesifik untuk masalah tersebut akan membantu. Tapi tidak ada palu umum.

Suresh Venkat

Jawaban:

Jika setiap urutan memiliki panjang 3, masalahnya dikenal sebagai Antara . Bahkan masalah Antara adalah NP-keras. Dalam masalah ini, kita diberikan satu set simpul dan satu set batasan bentuk terletak antara dan . Tujuan kami adalah memesan semua simpul untuk memaksimalkan jumlah kendala yang dipenuhi. Opantry [1] membuktikan bahwa versi keputusan dari masalah ini adalah NP-hard. Chor dan Sudan [2] membuktikan bahwa SNP-hard. $u$ $v$ $w$

Algoritma pendekatan yang paling dikenal untuk masalah, oleh Chor dan Sudan, memenuhi 1/2 dari semua kendala jika instance benar-benar memuaskan.

[1] J. Opantry. Total Ordering Problem, Jurnal SIAM tentang Komputer , 8 (1): 111–114, Februari 1979.

[2] B. Chor dan M. Sudan. Pendekatan geometris untuk hubungan antara , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, November 1998.

Suntingan: menjelaskan bahwa versi keputusan masalah adalah NP-hard.

Yury
sumber

Yury, apakah itu berarti bahwa masalah keputusan apakah semua kendala dapat dipenuhi juga sulit?

Chandra Chekuri

Ya, masalah keputusan NP-hard. Selain itu, untuk beberapa NP-sulit untuk memuaskan bahkan fraksi dari semua kendala (yaitu masalah janji yang sesuai adalah NP-hard).

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

Yury

Jika instance tidak sepenuhnya memuaskan , masalahnya sangat sulit: tentu saja, Anda dapat memenuhi dari semua kendala dengan mengambil urutan acak; tetapi sulit untuk memenuhi dari semua batasan jika untuk setiap konstanta [Charikar, Guruswami, Manokaran - CCC 2009].

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

Yury

pertanyaan saya mungkin bodoh. tetapi apakah kekerasan 3-reguler ( untuk semua ) meluas hingga 4-reguler secara alami?

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

Yixin Cao

Ya, ini pengurangannya. Pertimbangkan instance 3-reguler . Perkenalkan variabel baru untuk setiap urutan . Biarkan menjadi urutan yang diperoleh dengan menambahkan ke akhir . Kita mendapatkan instance 4-reguler pada simpul dengan urutan . Sangat mudah untuk melihat bahwa memuaskan jika memuaskan - ambil solusi untuk , masukkan masing-masing baik sebelum semua simpul dalam atau setelah semua simpul dalam

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$ tergantung pada orientasi (urutan relatif dari tidak relevan).

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$

Yury