Leksykograficznie minimalny rodzaj topologiczny oznaczonego DAG

Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ . Dokładniej, A topologiczna sortowania z G jest wyliczenie V jako v = v 1 , ... , v $G = (V, E)$$\lambda$$V$$L$$<_L$$G$$\lambda$$G$$V$$\mathbf{v} = v_1, \ldots, v_n$, tak, że dla wszystkich , ilekroć istnieje ścieżka od v i do v j w G , wówczas musimy mieć i < j . Etykiecie takiego topologicznej rodzaju jest kolejność elementów S otrzymuje się l = λ ( V 1 ) , ... , λ ( V n ) . Porządek leksykograficzny takich sekwencji (które wszystkie mają długość | V | ) jest zdefiniowany jako l < $i \neq j$$v_i$$v_j$$G$$i < j$$S$$\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$$|V|$ iff istnieje pewna pozycjaitaka, że l i < L l ' i i l j = l ' j dla wszystkichj<i. Zwróć uwagę na fakt, że każda etykieta wSmoże być przypisana do wielu wierzchołków wV(w przeciwnym razie problem jest trywialny).$\mathbf{l} <_{\text{LEX}} \mathbf{l'}$$i$$l_i <_L l_i'$$l_j = l'_j$$j < i$$S$$V$

Problem ten można stwierdzić albo w wariancie obliczeniowym („obliczyć leksykograficznie minimalne sortowanie topologiczne”), albo w wariancie decyzyjnym („czy to słowo wejściowe jest minimalnym sortowaniem topologicznym?”). Moje pytanie brzmi: jaka jest złożoność tego problemu ? Czy jest w PTIME (lub w FP, dla wariantu obliczeniowego), czy jest to NP-trudne? Jeśli ogólnym problemem jest trudność NP, jestem również zainteresowany wersją, w której zestaw możliwych etykiet jest z góry ustalony (tj. Istnieje tylko stała liczba możliwych etykiet).$S$

Uwagi:

Oto mały przykład z prawdziwego świata, który motywuje problem. Widzimy, że DAG reprezentuje zadania projektu (z zależnością między nimi), a etykiety są liczbami całkowitymi reprezentującymi liczbę dni, które zajmuje każde zadanie. Aby ukończyć projekt, zajmie mi to tyle samo czasu, bez względu na kolejność, jaką wybiorę dla zadań. Chciałbym jednak zaimponować mojemu szefowi i aby to zrobić, chcę wykonać jak najwięcej zadań tak szybko, jak to możliwe (w zachłanny sposób, nawet jeśli na końcu oznacza to bardzo powolne, ponieważ trudniejsze zadania pozostają). Wybór leksykograficznie Minimalne zamówienie optymalizuje następujące kryterium: Chcę wybrać rozkaz tak, że nie ma innej kolejności o ' a liczba dni n , gdzie po$o$$o'$$n$ dni ukończyłbym więcej zadań z rozkazem o ′ niż z rozkazem o (tj. jeśli mój szef patrzy na czas n , robię lepsze wrażenie z o ′ ), ale dla wszystkich m < n wykonałem nie mniej zadań z zamówienie o ′ niż zamówienie o .$n$$o'$$o$$n$$o'$$m < n$$o'$$o$

Aby dać wgląd w problem: już wiem z poprzednich odpowiedzi, że następujący powiązany problem jest trudny: „czy istnieje rodzaj topologiczny, który osiąga następującą sekwencję”? Jednak fakt, że chcę sekwencji, która jest minimalna dla tego porządku leksykograficznego, wydaje się bardzo ograniczać możliwe porządki topologiczne, które mogą to osiągnąć (w szczególności redukcje tych innych odpowiedzi już nie działają). Intuicyjnie jest znacznie mniej sytuacji, w których mamy wybór.

Zauważ, że wydaje się, że istnieją interesujące przeredagowania problemów pod względem pokrycia zestawu (przy ograniczeniu problemu do DAG, które są dwustronne, tj. Mają wysokość dwa): biorąc pod uwagę zestaw zbiorów, wylicz je w kolejności która minimalizuje leksykograficznie sekwencję | 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$. Problem można również przeformułować na niekierowanych wykresach (stopniowo rozszerzaj połączony obszar wykresu zgodnie z kolejnością, która minimalizuje sekwencję leksykograficzną odkrytych etykiet). Jednak z uwagi na fakt, że sekwencjamusibyć zawsze zachłanna, z definicji porządku leksykograficznego, nie mogę uzyskać redukcji (np. Drzewa Steiner) do działania.$|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$

Z góry dziękuję za twoje pomysły!

$G$$k$$G$$G$$xy$$x$$G$$y$$G$$1$$G$$0$

$k$$G$$k$ $1$ 0i-10i111010010001000010000010$\tbinom{k}{2}$ $0$$i-1$ $0$$i$$1$$110100100010000100000$$1$$0$dałby sekwencję z większą liczbą krawędzi niż można by znaleźć na prostym wykresie z tyloma wierzchołkami) i może być jedynie początkiem uporządkowania topologicznego, gdy zawiera pożądaną klikę.$G$

Zgodnie z tym odnośnikiem (1) problem leksykograficzny pierwszego porządku topologicznego jest kompletny dla NLOG.

Możesz dokładniej przyjrzeć się temu artykułowi, aby upewnić się, że obejmuje on interesujący Cię przypadek. W szczególności, w oparciu o wersję raportu technicznego (pdf) tego artykułu, wydaje się, że „ traktuję porządek leksykograficzny wierzchołków jako ścisły (np .: w twojej notacji dla ), ale nie jestem pewien, czy to wpływa na możliwość zastosowania wyniku .u ≠ $\lambda(u) \neq \lambda(v)$$u \neq v$

1. Shoudai, Takayoshi. „ Pierwszym problemem leksykograficznym porządku topologicznego jest kompletny NLOG. ” Listy przetwarzania informacji 33.3 (1989): 121-124.