Zliczanie rodzajów topologicznych DAG oznaczonych wierzchołkami

Niech być skierowany acykliczny wykres i pozwolić być funkcją znakowania mapowanie każdego wierzchołka do naklejania w pewnym skończonym alfabetu . Zapisywanie , A topologiczna sortowania z jest bijection z do (tj zamawiania $G = (V, E)$ $\lambda$ $v \in V$ $\lambda(v)$ $L$ $n := |V|$ $G$ $\sigma$ $\{1, \ldots, n\}$ $V$ w sekwencji) tak, że ilekroć a następnie (tj. Jeśli istnieje krawędź od do wówczas występuje przed w sekwencji). Etykietaz jest słowo w $V$ $(v, v') \in E$ $\sigma^{-1}(v) < \sigma^{-1}(v')$ $v$ $v'$ $v$ $v'$ $\sigma$ $\sigma(1) \cdots \sigma(n)$ . $L^n$

Biorąc pod uwagę , chciałbym efektywnie wyliczyć etykiety topologicznych rodzajów Jaka jest złożoność wyliczania etykiet rodzajów topologicznych? Oczywiście, ponieważ może być ich wykładniczo wiele, chcę zbadać złożoność w zależności od wielkości wyniku lub pod względem opóźnienia. W szczególności, czy można wyliczyć z opóźnieniem wielomianowym? (czy nawet stałe opóźnienie?) $(G, \lambda)$ $G$

W przypadku, gdy wszystkie wierzchołki mają odrębne etykiety (lub, równoważnie, wierzchołki mają same oznaczenia ), wiem, że etykiety można wyliczyć w stałym czasie zamortyzowanym, dzięki temu przy wyliczaniu rozszerzeń liniowych posetów (co jest tym samym, co wyliczenie topologicznych rodzajów DAG). Jednak gdy wierzchołki są arbitralnie etykietowane, może się zdarzyć, że bardzo duża liczba rodzajów topologicznych ma tę samą etykietę, więc nie można po prostu wyliczyć topologicznych rodzajów i obliczyć ich etykiety, aby uzyskać skuteczny sposób wyliczenia etykiet . W terminologii posetowej oznaczony DAG $G$ $\{1, \ldots, n\}$ $G$ można postrzegać jako zestaw zetykietąi nie mogłem znaleźć wyników wyliczeń na ich temat. $(G, \lambda)$

Znam już twardość niektórych powiązanych problemów dzięki odpowiedziom na moje inne pytania tutaj. W szczególności wiem, że znalezienie leksykograficznie minimalnej etykiety jest trudne NP . Wiem także, że podjęcie decyzji, czy dany znacznik można osiągnąć jakimś rodzajem topologicznym, jest trudne do przeprowadzenia na podstawie NP (od stopnia trudności tego problemu : biorąc pod uwagę sekwencję znacznika kandydata , poproś o rodzaj topologiczny którym każdy wierzchołek musi wystąpić w pozycji gdzie właściwa etykieta występuje w $s$ $G$ $s$ ). Nie sądzę jednak, aby cokolwiek z tego sugerowało twardość wyliczania, ponieważ można wyliczyć w dowolnej kolejności (niekoniecznie leksykograficznej), a algorytmu wyliczenia nie można użyć do skutecznego ustalenia, czy etykieta jest możliwa do osiągnięcia, nawet ze stałym opóźnieniem (ponieważ może być wykładniczo wiele sekwencji do wyliczenia w pierwszej kolejności).

$s$ $s$ $v$ $V$ $i \in \{1, \ldots, n\}$ $s_i \neq \lambda(v)$ $v$ $i$ $G$ $v$ $i$ , co można wyraźnie zrobić w PTIME. Ale kiedy generujesz coraz więcej etykiet, nie jestem pewien, jak uogólnić to podejście.

— a3nm
źródło

-1

$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)$

— sbzk
źródło

Dziękuję za odpowiedź! Nie rozumiem jednak, dlaczego poprawka, którą sugerujesz w pierwszym akapicie, byłaby wystarczająca do zapewnienia, że po wielomianowo wielu krokach powstanie inna etykieta sortowania topologicznego. Na przykład, jeśli wszystkie elementy mają tę samą etykietę, wówczas istnieje tylko jedna topologiczna etykieta sortowania do wyliczenia, ale nie jestem pewien, czy rozumiem, dlaczego twój algorytm to zauważył i zakończył wystarczająco szybko? (Inna kwestia: mówisz „sąsiad”, ale wykres przedstawia DAG; czy miałeś na myśli „dziecko”?)

— a3nm

Ulepszenie w pierwszym akapicie polega na generowaniu wszystkich możliwych zamówień niezależnie od etykiet. Aby ograniczyć uporządkowanie w przypadku podobnych etykiet, ważne jest, aby unikać wybierania wierzchołków tych samych etykiet, jeśli wydają się one być podobnie połączone z pozostałym niewidocznym wykresem. W ten sposób stworzyliby izomorficzny niewidoczny wykres generujący ten sam porządek topologiczny.

— sbzk

O (n^{2})

$O(n^2)$

Dziękuję za wyjaśnienie. Jednak szukam wielomianu związanego ze złożonością, który dotyczy wszystkich przypadków, a nie heurystyki bez teoretycznych gwarancji! :)

— a3nm