Jenis topologi minimal secara linguistik dari DAG berlabel

Pertimbangkan masalah di mana kita diberikan sebagai input grafik asiklik langsung $G = (V, E)$ , fungsi pelabelan $\lambda$ dari $V$ ke beberapa set $L$ dengan urutan total $<_L$ (misalnya, bilangan bulat), dan di mana kita diminta untuk hitung jenis topologi terkecil $G$ dari segi $\lambda$ . Lebih tepatnya, semacam topologi dari $G$ adalah penghitungan $V$ sebagai $\mathbf{v} = v_1, \ldots, v_n$, sehingga untuk semua , setiap kali ada jalur dari v i ke v j di G , maka kita harus memiliki i < j . The label dari seperti semacam topologi adalah urutan elemen dari S diperoleh sebagai l = λ ( v 1 ) , ... , λ ( v n ) . Urutan leksikografis pada sekuens semacam itu (yang semuanya memiliki panjang | V | ) didefinisikan sebagai l < $i \neq j$$v_i$$v_j$$G$$i < j$$S$$\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$$|V|$ IFF ada beberapa posisisayasehingga l i < L l ' i dan l j = l ' j untuk semuaj<i. Perhatikan fakta bahwa setiap label dalamSdapat ditetapkan ke banyak simpul dalamV(jika tidak masalahnya masalahnya sepele).$\mathbf{l} <_{\text{LEX}} \mathbf{l'}$$i$$l_i <_L l_i'$$l_j = l'_j$$j < i$$S$$V$

Masalah ini dapat dinyatakan dalam varian komputasi ("hitung jenis topologi minimal leksikografis") atau dalam varian keputusan ("apakah kata input ini jenis topologi minimal?"). Pertanyaan saya adalah, apa kompleksitas masalah ini ? Apakah di PTIME (atau di FP, untuk varian perhitungan) atau apakah NP-hard? Jika masalah umum NP-hard, saya juga tertarik tentang versi di mana himpunan dari label mungkin diperbaiki sebelumnya (yaitu, hanya ada jumlah label yang mungkin konstan).$S$

Catatan:

Berikut adalah contoh kecil dunia nyata untuk memotivasi masalah. Kita bisa melihat DAG sebagai tugas mewakili suatu proyek (dengan hubungan ketergantungan di antara mereka) dan label adalah bilangan bulat yang mewakili jumlah hari yang dibutuhkan setiap tugas. Untuk menyelesaikan proyek, saya akan membutuhkan total waktu yang sama tidak peduli urutan yang saya pilih untuk tugas-tugas tersebut. Namun, saya ingin mengesankan atasan saya, dan untuk melakukan ini saya ingin menyelesaikan banyak tugas secepat mungkin (dengan cara serakah, bahkan jika itu berarti sangat lambat pada akhirnya karena tugas yang lebih sulit tetap). Memilih urutan minimal leksikografis mengoptimalkan kriteria berikut: Saya ingin memilih pesanan sedemikian rupa sehingga tidak ada pesanan lain o ′ dan beberapa hari n setelah$o$$o'$$n$ hari saya akan menyelesaikan lebih banyak tugas dengan pesanan o ′ daripada dengan pesanan o (yaitu, jika bos saya melihat waktu n , saya memberikan kesan yang lebih baik dengan o ′ ), tetapi untuk semua m < n saya telah menyelesaikan tugas yang tidak kurang dengan memesan o ′ daripada dengan memesan o .$n$$o'$$o$$n$$o'$$m < n$$o'$$o$

Untuk memberikan beberapa wawasan tentang masalah: Saya sudah tahu dari jawaban sebelumnya bahwa masalah terkait berikut ini sulit: "adakah jenis topologi yang mencapai urutan berikut"? Namun, fakta di sini bahwa saya menginginkan urutan yang minimal untuk tatanan leksikografis ini tampaknya banyak membatasi tatanan topologi yang mungkin mencapainya (khususnya pengurangan jawaban-jawaban lain itu tampaknya tidak lagi berfungsi). Secara intuitif, ada jauh lebih sedikit situasi di mana kita punya pilihan untuk membuat.

Perhatikan bahwa tampaknya ada pengulangan menarik masalah dalam hal set cover (ketika membatasi masalah ke DAG yang bipartit, yaitu, memiliki tinggi dua): diberi satu set set, sebutkan dengan urutan yang meminimalkan urutan leksikografis | S 1 | , | S 2 ∖ S 1 | , | S 3 ∖ ( S 1 ∪ S 2 ) | , ... , | S n ∖ $S_1, \ldots, S_n$$|S_1|$$|S_2 \backslash S_1|$$|S_3 \backslash (S_1 \cup S_2)|$$\ldots$. Masalahnya juga dapat diulangi pada grafik yang tidak terarah (semakin memperluas area terhubung dari grafik mengikuti urutan yang meminimalkan urutan leksikografis dari label yang terbuka). Namun, karena fakta bahwa urutanmemilikimenjadi serakah setiap saat dengan definisi dari urutan leksikografis, saya tidak bisa mendapatkan pengurangan (misalnya, pohon Steiner) bekerja.$|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$

Terima kasih sebelumnya atas ide Anda!

Dengan beberapa salinan dari label yang sama diizinkan, masalahnya adalah NP-hard, melalui pengurangan dari klik-klik dalam grafik. Diberikan grafik di mana Anda ingin menemukan k -clique, buat DAG dengan simpul sumber untuk setiap simpul G , simpul wastafel untuk setiap tepi G , dan tepi terarah x y setiap kali x adalah simpul G yang membentuk titik akhir dari tepi y . Berikan simpul G nilai label 1 dan tepi G nilai label 0 .$G$$k$$G$$G$$xy$$x$$G$$y$$G$$1$$G$$0$

Kemudian, ada -clique di G jika dan hanya jika urutan leksikografis pertama topologi membentuk urutan k 1 's dan ($k$$G$$k$ $1$ 0's, dengani-10' s mengikutiith1. Misalnya klik enam-titik akan diwakili oleh urutan110100100010000100000. Ini adalah urutan terkecil secara leksikografis yang mungkin dapat memulai urutan topologi dari DAG berlabel yang diberikan oleh konstruksi ini (mengganti salah satu dari1dengan0akan memberikan urutan dengan lebih banyak tepi daripada yang dapat ditemukan dalam grafik sederhana dengan itu banyak simpul) dan itu hanya bisa menjadi awal dari pemesanan topologi ketikaGberisi klik yang diinginkan.$\tbinom{k}{2}$ $0$$i-1$ $0$$i$$1$$110100100010000100000$$1$$0$$G$

Menurut referensi ini (1), masalah urutan topologi leksikografis pertama adalah NLOG-lengkap.

You may want to take a more thorough look at the article to ensure that it covers the case(s) that you're interested in. In particular, based on the technical report version (pdf) of that article, it appears that they're treating the lexicographic ordering of the vertices as strict (e.g.: in your notation, $\lambda(u) \neq \lambda(v)$ for $u \neq v$), but I'm not sure if this affects the applicability of the result.

1. Shoudai, Takayoshi. "The lexicographically first topological order problem is NLOG-complete." Information processing letters 33.3 (1989): 121-124.