Énumération des types topologiques d'un DAG étiqueté par un sommet

Soit soit un graphe acyclique orienté , et soit λ est une fonction de marquage en correspondance chaque sommet v ∈ V à une étiquette λ ( v ) dans un alphabet fini L . Écriture n : = | V | , une sorte topologique de G est une bijection σ de { 1 , … , n } à V (c'est-à-dire un ordre de$G = (V, E)$$\lambda$$v \in V$$\lambda(v)$$L$$n := |V|$$G$$\sigma$$\{1, \ldots, n\}$$V$ dans une séquence) telle que chaque fois que ( v , v ′ ) ∈ E alors σ - 1 ( v ) < σ - 1 ( v ′ ) (c'est-à-dire, s'il y a un bord de v à v ′ alors v se produit avant v ′ dans la séquence). L'étiquettede σ est le mot σ ( 1 ) ⋯ σ ( n ) dans$V$$(v, v') \in E$$\sigma^{-1}(v) < \sigma^{-1}(v')$$v$$v'$$v$$v'$$\sigma$$\sigma(1) \cdots \sigma(n)$ .$L^n$

Étant donné , je voudrais énumérer efficacement les étiquettes des sortes topologiques de G. Quelle est la complexité de l'énumération des étiquettes de types topologiques? Bien sûr, comme il peut y en avoir de manière exponentielle, je veux étudier la complexité en fonction de la taille de la sortie, ou en termes de retard. En particulier, l'énumération peut-elle être effectuée avec un retard polynomial? (ou même un retard constant?)$(G, \lambda)$$G$

Dans le cas où tous les sommets de portent des étiquettes distinctes (ou, de manière équivalente, les sommets sont { 1 , … , n } étiquetés par eux-mêmes), je sais que les étiquettes peuvent être énumérées en temps amorti constant, par ce résultat sur l'énumération des extensions linéaires de posets (ce qui revient à énumérer les types topologiques d'un DAG). Cependant, lorsque les sommets sont étiquetés de manière arbitraire, il peut arriver qu'un très grand nombre de tris topologiques aient la même étiquette, vous ne pouvez donc pas simplement énumérer les sortes topologiques de G et calculer leurs étiquettes pour obtenir un moyen efficace d'énumérer les étiquettes . Dans la terminologie des posets, le DAG étiqueté ( G $G$$\{1, \ldots, n\}$$G$ peut être considéré comme unposetétiqueté, et je n'ai pas pu trouver de résultats d'énumération à ce sujet.$(G, \lambda)$

Je connais déjà la dureté de certains problèmes connexes grâce aux réponses à mes autres questions ici. En particulier, je sais que trouver l'étiquette lexicographiquement minimale est difficile à NP . Je sais également que décider si une étiquette donnée peut être obtenue par un tri topologique est NP-difficile (à cause de la dureté de ce problème : étant donné une séquence d'étiquettes candidate , demandez une sorte topologique de G où chaque sommet doit se produire à une position où la bonne étiquette apparaît en $s$$G$$s$). Cependant, je ne pense pas que cela implique une dureté pour l'énumération, comme vous pouvez l'énumérer dans n'importe quel ordre (pas nécessairement lexicographique), et un algorithme d'énumération ne peut pas être utilisé pour décider efficacement si une étiquette est réalisable, même avec un retard constant (car il peut y avoir de façon exponentielle de nombreuses séquences à énumérer en premier).

Notez que, il est évidemment facile d'énumérer une première étiquette (il suffit de prendre n'importe quel tri topologique). Pour énumérer une autre étiquette que s , vous pouvez procéder en imposant qu'un élément v de V soit énuméré à une position i ∈ { 1 , … , n } où s i ≠ λ ( v ) : essayez tous les v et i , et vérifiez si G a un tri topologique où v est à la position $s$$s$$v$$V$$i \in \{1, \ldots, n\}$$s_i \neq \lambda(v)$$v$$i$$G$$v$$i$, ce qui peut clairement être fait dans PTIME. Mais comme vous produisez de plus en plus d'étiquettes, je ne sais pas comment généraliser cette approche.

L'un des moyens les plus simples de calculer l'ordre topologique consiste à effectuer une recherche en profondeur d'abord sur le DAG donné. Différents ordres topologiques peuvent être générés en exploitant la flexibilité de choisir le sommet suivant à parcourir parmi les voisins non visités du sommet actuel u . Depuis, il s'agit d'une procédure récursive énumérant tous les parcours possibles (et donc les ordres topologiques) serait simple, en choisissant des ordres différents dans lesquels les voisins non visités de u sont parcourus.$v$$u$$u$

Maintenant, afin de limiter la répétition de la même traversal en raison des étiquettes similaires, on peut comparer les voisins inexplorées de u ayant des étiquettes similaires. Considérons deux sommets v i et v j qui ont les mêmes voisins non visités lorsque le parcours atteint u . Sûrement, choisir l'un d'entre eux en premier générerait le même arbre DFS et donc chacun d'entre eux peut être évité.$v_1,v_2,...,v_k$$u$$v_i$$v_j$$u$

Maintenant, en comparant les voisins de tous entraînerait une surcharge de O ( n 2 ) sur la durée totale, mais peut être effectuée plus efficacement dans ˜ O ( n ) en utilisant des structures de données appropriées.$v_1,...,v_k$$O(n^2)$$\tilde{O}(n)$