Aufzählung topologischer Arten einer vertexmarkierten DAG

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 von$G = (V, E)$$\lambda$$v \in V$$\lambda(v)$$L$$n := |V|$$G$$\sigma$$\{1, \ldots, 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$V$$(v, v') \in E$$\sigma^{-1}(v) < \sigma^{-1}(v')$$v$$v'$$v$$v'$$\sigma$$\sigma(1) \cdots \sigma(n)$ .$L^n$

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, \lambda)$$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, \ldots, n\}$$G$ kann alsbeschrifteterPoset angesehen werden, und ich konnte keine Aufzählungsergebnisse zu diesen finden.$(G, \lambda)$

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$$G$$s$). 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 $s$$s$$v$$V$$i \in \{1, \ldots, n\}$$s_i \neq \lambda(v)$$v$$i$$G$$v$$i$, 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.

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