Lexikographisch minimale topologische Sorte einer markierten DAG

13

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 nG=(V,E)λVL<LGλGVv=v1,,vn 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 < LEXijvivjGi<jSl=λ(v1),,λ(vn)|V|V zugeordnet werden kann(ansonsten ist das Problem trivial).l<LEXlwenn 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 kannili<Llilj=ljj<iSV

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 Tagenoo nach denenn 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 .noonom<noo

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 2S 1 | , | S 3( S 1S 2 ) | , , | S nS1,,Sn|S1||S2S1||S3(S1S2)|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|Sn(S1Sn1)|

Vielen Dank im Voraus für Ihre Ideen!

a3nm
quelle

Antworten:

12

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 .GkGGxyxGyG1G0

Dann gibt es eine Klasse in G, wenn und nur wenn die lexikographisch erste topologische Ordnung eine Folge von k 1 und ( kkGk 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.(k2) 0i1 0i111010010001000010000010G

David Eppstein
quelle
Oh, ich hatte nicht an Cliquen gedacht. Das ist eine schöne Ermäßigung, vielen Dank! Dies zeigt also, dass das Berechnungsproblem auch mit dem festen Bezeichnungsalphabet NP-schwer ist . Dies impliziert auch, dass das Entscheidungsproblem "die lexikographisch kleinste Sequenz ist, die kleiner ist als diese" ebenfalls NP-schwer ist (Sie können es verwenden, um das Minimum mit der binären Suche zu berechnen). Die einzige zusätzliche Frage, die ich sehe, ist, ob das Problem "Ist diese exakte Eingabesequenz die minimale" auch NP-hart ist. (Damit können Sie nicht einfach testen, ob das minimale Wort mit einem Präfix beginnt.) Haben Sie eine Idee für dieses? {0,1}
a3nm
1
Mein Verdacht ist, dass das Problem "Ist diese exakte Sequenz erreichbar?" NP-vollständig ist, aber ich habe keine Reduktion zur Hand. "Ist diese exakte Sequenz die minimale" sollte sich auf der zweiten Ebene der Polynom-Hierarchie befinden, da eine Kombination aus existenzieller Quantifizierung (ist erreichbar) und universeller Quantifizierung (sind alle erreichbaren Sequenzen mindestens so groß) erforderlich ist.
David Eppstein
Tatsächlich weiß ich bereits, dass das Testen, ob eine genaue Sequenz erreichbar ist, NP-schwer ist (auf einem Alphabet mit 3 Bezeichnungen), indem eine Reduktion von einer unären 3-Partition von Marzio de Biasi vorgenommen wird, die hier skizziert wird: cstheory.stackexchange.com/a/19415 . Aber ich denke, es sagt nichts über den Status des Problems aus: "Ist dies die minimal erreichbare Sequenz?" Wenn man fragt, ob eine bestimmte Sequenz erreichbar ist, hat man im Allgemeinen nur eine geringe Chance, in einer bestimmten lexikografischen Reihenfolge minimal zu sein. In jedem Fall ist das, was Ihre Reduktion zeigt, immer noch sehr interessant. Nochmals vielen Dank! :)
a3nm
2

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

λ(u)λ(v)uv

  1. Shoudai, Takayoshi. " Das lexikographisch erste Problem der topologischen Ordnung ist NLOG-vollständig. " Information Processing Letters 33.3 (1989): 121-124.
mhum
quelle
4
NLOG-complete ist eine Teilmenge der Polynomzeit, und (gemäß dem Satz "Achten Sie darauf" im ersten Absatz des Problems) macht die Unterscheidung der Bezeichnungen der Scheitelpunkte das Problem durch einen Algorithmus mit Polynomzeitgier leicht lösbar. Die eigentliche Frage ist, was passiert, wenn die Etiketten nicht eindeutig sind.
David Eppstein
Das ist ein fairer Punkt. Aus Ihrer Antwort geht nun klar hervor, dass die Wiederholung von Etiketten das Problem schwieriger macht als der Fall von eindeutigen Etiketten.
mhum