Lexikographisch minimale topologische Sorte einer markierten DAG

Betrachten Sie das Problem, bei dem wir als Eingabe einen gerichteten azyklischen Graphen , eine Markierungsfunktion λ von V bis zu einer Menge L mit einer Gesamtordnung < L (z. B. die ganzen Zahlen) erhalten und dazu aufgefordert werden Berechnen Sie die lexikographisch kleinste topologische Sorte von G in λ . Genauer gesagt ist eine topologische Art von G eine Aufzählung von V als v = v 1 , … , v $G = (V, E)$$\lambda$$V$$L$$<_L$$G$$\lambda$$G$$V$$\mathbf{v} = v_1, \ldots, v_n$ so groß , daß für alle , wann immer es einen Pfad von v i nach v j in G gibt , müssen wir i < j haben . DieBezeichnungeiner solchen topologischen Sorte ist die Folge von Elementen von S, die sich ergibt als l = λ ( v 1 ) , … , λ ( v n ) . Die lexikographische Reihenfolge auf solchen Sequenzen (die alle die Länge | V | haben ) ist definiert als l < $i \neq j$$v_i$$v_j$$G$$i < j$$S$$\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$$|V|$V zugeordnet werden kann(ansonsten ist das Problem trivial).$\mathbf{l} <_{\text{LEX}} \mathbf{l'}$wenn es eine Position so dass l i < L l ' i und l j = l ' j für alle j < i . Beachten Sie, dass jedes Label in S mehreren Vertices in zugeordnet werden kann$i$$l_i <_L l_i'$$l_j = l'_j$$j < i$$S$$V$

Dieses Problem kann entweder in einer Berechnungsvariante ("Berechnen der lexikografisch minimalen topologischen Sortierung") oder in einer Entscheidungsvariante ("Ist dieses Eingabewort die minimale topologische Sortierung?") Angegeben werden. Meine Frage ist, wie komplex dieses Problem ist . Ist es in PTIME (oder in FP, für die Berechnungsvariante) oder ist es NP-schwer? Wenn das allgemeine Problem NP-schwer ist, interessiert mich auch die Version, bei der die Menge möglicher Etiketten im Voraus festgelegt ist (dh es gibt nur eine konstante Anzahl möglicher Etiketten).$S$

Bemerkungen:

Hier ist ein kleines Beispiel aus der Praxis, um das Problem zu motivieren. Wir können sehen, dass die DAG Aufgaben eines Projekts darstellt (mit einer Abhängigkeitsbeziehung zwischen ihnen), und die Bezeichnungen sind ganze Zahlen, die die Anzahl der Tage darstellen, die jede Aufgabe benötigt. Um das Projekt abzuschließen, benötige ich unabhängig von der Reihenfolge, in der ich die Aufgaben erledige, insgesamt die gleiche Zeit. Ich möchte jedoch meinen Chef beeindrucken, und dazu möchte ich möglichst viele Aufgaben so schnell wie möglich erledigen (auf gierige Weise, auch wenn es am Ende bedeutet, sehr langsam zu sein, weil die schwierigeren Aufgaben bestehen bleiben). Die Auswahl der lexikografisch minimalen Reihenfolge optimiert das folgende Kriterium: Ich möchte eine Reihenfolge so wählen, dass es keine andere Reihenfolge o ' und eine Anzahl von Tagen$o$$o'$ nach denen$n$ Tage hätte ich mit Befehl o ' mehr Aufgaben erledigtals mit Befehl o (dh wenn mein Chef zum Zeitpunkt n schaut, mache ich mit o ' einen besseren Eindruck), aber für alle m < n habe ich nicht weniger Aufgaben erledigt mit Bestellung o ' als bei Bestellung o .$n$$o'$$o$$n$$o'$$m < n$$o'$$o$

Um einen Einblick in das Problem zu geben: Ich weiß bereits aus früheren Antworten, dass das folgende verwandte Problem schwierig ist: "Gibt es eine topologische Sortierung, die die folgende Reihenfolge erreicht"? Die Tatsache, dass ich hier eine Sequenz wünsche, die für diese lexikografische Reihenfolge minimal ist , scheint jedoch die möglichen topologischen Ordnungen, die dies bewirken könnten, stark einzuschränken (insbesondere scheinen die Verringerungen dieser anderen Antworten nicht mehr zu funktionieren). Intuitiv gibt es viel weniger Situationen, in denen wir eine Wahl treffen müssen.

Beachten Sie, dass es interessante Umformulierungen der Probleme in Bezug auf die Mengenabdeckung zu geben scheint (wenn Sie das Problem auf zweigeteilte DAGs beschränken, dh die Höhe zwei haben): Wenn Sie eine Menge von Mengen haben, listen Sie sie in einer Reihenfolge , das die Sequenz lexikographisch minimiert | S 1 | , | S 2 ∖ S 1 | , | S 3 ≤ ( S 1 ≤ S 2 ) | , … , | S $S_1, \ldots, S_n$$|S_1|$$|S_2 \backslash S_1|$$|S_3 \backslash (S_1 \cup S_2)|$$\ldots$hatjederzeit per Definition, gierig zu sein von der lexikographischen Ordnung, kann ich nicht bekommen Senkungen (zB von Steiner Baum) anArbeit.. Das Problem kann auch in ungerichteten Diagrammen umformuliert werden (erweitern Sie einen verbundenen Bereich des Diagramms schrittweise in der Reihenfolge, in der die lexikografische Reihenfolge der nicht abgedeckten Beschriftungen minimiert wird). Allerdings wegen der Tatsache, dass die Reihenfolge$|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$

Vielen Dank im Voraus für Ihre Ideen!

Wenn mehrere Kopien desselben Etiketts zulässig sind, ist das Problem NP-schwer, durch eine Reduzierung von Cliquen in Diagrammen. Ausgehend von einem Graphen in dem Sie eine k- Klasse finden möchten, erstellen Sie eine DAG mit einem Quellenscheitelpunkt für jeden Scheitelpunkt von G , einem Senkenscheitelpunkt für jede Kante von G und einer gerichteten Kante x y, wenn x ein Scheitelpunkt von G ist das bildet einen Endpunkt der Kante y . Geben Sie den Eckpunkten von G den Beschriftungswert 1 und den Kanten von G den Beschriftungswert 0 .$G$$k$$G$$G$$xy$$x$$G$$y$$G$$1$$G$$0$

Dann gibt es eine Klasse in G, wenn und nur wenn die lexikographisch erste topologische Ordnung eine Folge von k 1 und ($k$$G$$k$ $1$ 0's, wobeii-10' s aufith1folgen. Beispielsweise würde eine Clique mit sechs Eckpunkten durch die Sequenz110100100010000100000 dargestellt. Dies ist die lexikographisch kleinste Sequenzdie möglicherweise eine topologische Ordnung eines markierten DAG durch diese Konstruktion (Ersatzjede der gegebenen beginnen konnte1's von0ist eine Sequenz mit mehr Kanten geben würdeals in einem einfachen Graphen gefunden werden konnte mit der viele Eckpunkte) und es kann nur der Beginn einer topologischen Ordnung sein, wennGdie gewünschte Clique enthält.$\tbinom{k}{2}$ $0$$i-1$ $0$$i$$1$$110100100010000100000$$1$$0$$G$

Nach dieser Referenz (1) ist das lexikographisch erste Problem der topologischen Ordnung NLOG-vollständig.

$\lambda(u) \neq \lambda(v)$$u \neq v$

1. Shoudai, Takayoshi. " Das lexikographisch erste Problem der topologischen Ordnung ist NLOG-vollständig. " Information Processing Letters 33.3 (1989): 121-124.