Menghitung jenis topologi DAG berlabel titik

Mari menjadi grafik asiklik diarahkan , dan membiarkan λ menjadi fungsi pelabelan memetakan setiap titik v ∈ V untuk label λ ( v ) di beberapa alfabet yang terbatas L . Menulis n : = | V | , Sebuah semacam topologi dari G adalah bijection σ dari { 1 , ... , n } ke V (yaitu, pemesanan$G = (V, E)$$\lambda$$v \in V$$\lambda(v)$$L$$n := |V|$$G$$\sigma$$\{1, \ldots, n\}$$V$ secara berurutan) sehingga setiap kali ( v , v ' ) ∈ E maka σ - 1 ( v ) < σ - 1 ( v ' ) (yaitu, jika ada tepi dari v ke v ' kemudian v terjadi sebelum v ' dalam urutan). Thelabeldari σ adalah kata σ ( 1 ) ⋯ σ ( n ) di$V$$(v, v') \in E$$\sigma^{-1}(v) < \sigma^{-1}(v')$$v$$v'$$v$$v'$$\sigma$$\sigma(1) \cdots \sigma(n)$ .$L^n$

Diberikan , saya ingin menyebutkan label jenis topologi G secara efisien. Apa kompleksitas penghitungan label jenis topologi? Tentu saja, karena ada banyak secara eksponensial, saya ingin mempelajari kompleksitas sebagai fungsi dari ukuran output, atau dalam hal keterlambatan. Secara khusus, dapatkah pencacahan dilakukan dengan penundaan polinomial? (atau bahkan penundaan konstan?)$(G, \lambda)$$G$

Dalam kasus di mana semua simpul membawa label yang berbeda (atau, ekuivalen, simpul adalah { 1 , ... , n } dilabelkan sendiri), saya tahu bahwa label dapat disebutkan dalam waktu diamortisasi konstan, dengan hasil ini pada penghitungan ekstensi linear poset (yang merupakan hal yang sama dengan menghitung jenis topologi DAG). Namun, ketika simpul diberi label secara sewenang-wenang, bisa jadi itu kasus bahwa sejumlah besar jenis topologi memiliki label yang sama, sehingga Anda tidak bisa hanya menghitung jenis topologi G dan menghitung label mereka untuk mendapatkan cara yang efisien untuk menyebutkan label. . Dalam terminologi poset, berlabel DAG ( G $G$$\{1, \ldots, n\}$$G$ dapat dilihat sebagaiposetberlabel, dan saya tidak dapat menemukan hasil enumerasi tentang itu.$(G, \lambda)$

Saya sudah tahu kekerasan dari beberapa masalah terkait berkat jawaban atas pertanyaan saya yang lain di sini. Secara khusus, saya tahu bahwa menemukan label minimal leksikografis adalah NP-hard . Saya juga tahu bahwa memutuskan apakah label yang diberikan dapat dicapai dengan semacam topologi adalah NP-keras (dari kekerasan masalah ini : diberi label calon urutan , meminta semacam topologi G di mana setiap titik harus terjadi pada posisi di mana label yang tepat terjadi pada $s$$G$$s$). Namun, saya tidak berpikir bahwa semua ini menyiratkan kekerasan untuk pencacahan, karena Anda dapat menghitung dalam urutan apa pun yang Anda suka (tidak harus leksikografis), dan algoritma pencacahan tidak dapat digunakan untuk memutuskan secara efisien apakah label dapat dicapai, bahkan dengan penundaan konstan (karena mungkin ada banyak urutan secara eksponensial untuk disebutkan terlebih dahulu).

$s$$s$$v$$V$$i \in \{1, \ldots, n\}$$s_i \neq \lambda(v)$$v$$i$$G$$v$$i$, yang jelas dapat dilakukan di PTIME. Tetapi saat Anda menampilkan lebih banyak label, saya tidak yakin bagaimana cara menggeneralisasi pendekatan ini.

$v$$u$$u$

$v_1,v_2,...,v_k$$u$$v_i$$v_j$$u$

$v_1,...,v_k$$O(n^2)$$\tilde{O}(n)$