Aufzählung topologischer Arten einer vertexmarkierten DAG

11

Sei ein gerichteter azyklischer Graph und sei λ eine Markierungsfunktion, die jeden Scheitelpunkt v V auf eine Markierung λ ( v ) in einem endlichen Alphabet L abbildet . Schreiben von n : = | V | , eine topologische Art von G ist eine Bijektion σ von { 1 , , n } nach V (dh eine Ordnung vonG=(V,E)λvVλ(v)Ln:=|V|Gσ{1,,n}V in einer Sequenz)so dass immer dannwenn ( v , v ' ) E dann σ - 1 ( v ) < σ - 1 ( v ' ) (heißt, wenn es eine Kante von ist v zu v ' dann v auftrittbevor v ' in der Reihenfolge). DieBezeichnungvon σ ist das Wort σ ( 1 ) σ ( n ) in L.V(v,v)Eσ1(v)<σ1(v)vvvvσσ(1)σ(n) .Ln

Angesichts von möchte ich die Bezeichnungen topologischer Arten von G effizient aufzählen . Wie komplex ist die Aufzählung der Bezeichnungen topologischer Sorten? Da es exponentiell viele geben kann, möchte ich natürlich die Komplexität in Abhängigkeit von der Größe der Ausgabe oder in Bezug auf die Verzögerung untersuchen. Kann die Aufzählung insbesondere mit Polynomverzögerung durchgeführt werden? (oder sogar konstante Verzögerung?)(G,λ)G

In dem Fall, in dem alle Scheitelpunkte von unterschiedliche Beschriftungen tragen (oder äquivalent dazu sind die Scheitelpunkte von sich aus { 1 , , n } beschriftet), weiß ich, dass Beschriftungen durch dieses Ergebnis bei der Aufzählung linearer Erweiterungen in konstanter Amortisationszeit aufgezählt werden können von Posets (was dasselbe ist wie die Aufzählung topologischer Arten einer DAG). Wenn Scheitelpunkte jedoch willkürlich beschriftet werden, kann es vorkommen, dass eine sehr große Anzahl topologischer Sortierungen dieselbe Beschriftung aufweist. Sie können also nicht einfach topologische Sortierungen von G auflisten und ihre Beschriftungen berechnen, um eine effiziente Methode zur Aufzählung der Beschriftungen zu erhalten . In der Poset-Terminologie ist die markierte DAG ( G ,G{1,,n}G kann alsbeschrifteterPoset angesehen werden, und ich konnte keine Aufzählungsergebnisse zu diesen finden.(G,λ)

Dank der Antworten auf meine anderen Fragen hier kenne ich bereits die Härte einiger verwandter Probleme. Insbesondere weiß ich, dass es NP-schwer ist, das lexikographisch minimale Etikett zu finden . Ich weiß auch , dass die Entscheidung , ob ein bestimmtes Etikett durch eine topologische Sortierung erreicht werden kann NP-hart ist (von der Härte dieses Problems : ein Kandidaten Etikett angegebene Reihenfolge , fragen Sie nach einer topologischen Art von G , wo jede Ecke an einer Position erfolgen muss wo das richtige Etikett in s vorkommtsGs). Ich glaube jedoch nicht, dass dies eine Härte für die Aufzählung impliziert, da Sie in beliebiger Reihenfolge aufzählen können (nicht unbedingt lexikografisch), und ein Aufzählungsalgorithmus kann nicht verwendet werden, um effizient zu entscheiden, ob eine Beschriftung überhaupt erreichbar ist mit konstanter Verzögerung (da möglicherweise exponentiell viele Sequenzen zuerst aufgezählt werden müssen).

Beachten Sie, dass es offensichtlich einfach ist, ein erstes Label (nehmen Sie einfach eine beliebige topologische Sortierung). Aufzuzählen ein anderes Etikett als s , können Sie durch die Einführung , dass ein Element gehen v von V an einem bestimmten Position aufgezählt wird i { 1 , ... , n } , wo s i & ne; & lgr; ( v ) : versuchen , jeden aus v und i und Scheck wenn G eine topologische Sortierung hat, wobei v an Position i istssvVi{1,,n}siλ(v)viGvi, was eindeutig in PTIME möglich ist. Da Sie jedoch immer mehr Labels ausgeben, bin ich mir nicht sicher, wie ich diesen Ansatz verallgemeinern soll.

a3nm
quelle

Antworten:

-1

vuu

v1,v2,...,vkuvivju

v1,...,vkO(n2)O~(n)

sbzk
quelle
Danke für deine Antwort! Ich verstehe jedoch nicht, warum die von Ihnen im ersten Absatz vorgeschlagene Optimierung ausreichen würde, um sicherzustellen, dass nach polynomiell vielen Schritten ein anderes topologisches Sortieretikett erstellt wird. Wenn beispielsweise alle Elemente dieselbe Bezeichnung haben, muss nur eine topologische Sortierbezeichnung aufgelistet werden. Ich bin mir jedoch nicht sicher, warum Ihr Algorithmus dies bemerken und ausreichend schnell beenden würde. (Ein weiterer Punkt: Sie sagen "Nachbar", aber die Grafik ist eine DAG;
meinten
Die Optimierung in Absatz 1 besteht darin, alle möglichen Ordnungen unabhängig von den Etiketten zu generieren. Um die Reihenfolge bei ähnlichen Beschriftungen einzuschränken, ist es wichtig, die Auswahl von Scheitelpunkten derselben Beschriftungen zu vermeiden, wenn sie in ähnlicher Weise mit dem verbleibenden nicht besuchten Diagramm verbunden zu sein scheinen. Daher würden sie einen isomorphen, nicht besuchten Graphen erzeugen, der dieselbe topologische Reihenfolge erzeugt.
sbzk
O(n2)
Danke für die Erklärung. Ich suche jedoch ein Polynom, das an die Komplexität gebunden ist und für alle Fälle gilt, nicht eine Heuristik ohne theoretische Garantien! :)
a3nm