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

11

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 deG=(V,E)λvVλ(v)Ln:=|V|Gσ{1,,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 LV(v,v)Eσ1(v)<σ1(v)vvvvσσ(1)σ(n) .Ln

É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,λ)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,,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,λ)

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 ssGs). 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 }s iλ ( v ) : essayez tous les v et i , et vérifiez si G a un tri topologique où v est à la position issvVi{1,,n}siλ(v)viGvi, 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.

a3nm
la source

Réponses:

-1

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

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é.v1,v2,...,vkuvjevju

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.v1,...,vkO(n2)O~(n)

sbzk
la source
Merci pour votre réponse! Cependant, je ne comprends pas pourquoi le réglage que vous proposez dans le premier paragraphe serait suffisant pour garantir qu'une étiquette de tri topologique différente est produite après plusieurs étapes polynomiales. Par exemple, si tous les éléments ont la même étiquette, alors il n'y a qu'une seule étiquette de tri topologique à énumérer, mais je ne suis pas sûr de voir pourquoi votre algorithme le remarquerait et se terminerait assez rapidement? (Un autre point: vous dites "voisin", mais le graphique est un DAG; vouliez-vous dire "enfant"?)
a3nm
Le tweak dans le premier paragraphe est de générer toutes les commandes possibles indépendamment des étiquettes. Afin de limiter les commandes dans le cas d'étiquettes similaires, il est important d'éviter de sélectionner des sommets de mêmes étiquettes s'ils semblent être connectés de la même manière au graphique non visité restant. Par conséquent, ils créeraient un graphe isomorphe non visité générant le même ordre topologique.
sbzk
O(n2)
Merci pour l'explication. Cependant, je recherche un polynôme lié à la complexité qui s'applique à tous les cas, pas une heuristique sans garantie théorique! :)
a3nm