Tri topologique lexicographiquement minimal d'un DAG étiqueté

13

Considérons le problème où on nous donne en entrée un graphe acyclique dirigé , une fonction d'étiquetage λ de V vers un ensemble L avec un ordre total < L (par exemple, les entiers), et où on nous demande de calculer le plus petit tri topologique lexicographiquement de G en termes de λ . Plus précisément, une sorte topologique de G est une énumération de V comme v = v 1 , , v nG=(V,E)λVL<LGλGVv=v1,,vn , telle que pour tout , chaque fois qu'il existe un chemin de v i à v j dans G , alors nous devons avoir i < j . L'étiquetted'une telle sorte topologique est la séquence d'éléments de S obtenue comme l = λ ( v 1 ) , , λ ( v n ) . L'ordre lexicographique de telles séquences (qui ont toutes une longueur | V | ) est défini comme l < LEXijvivjGi<jSl=λ(v1),,λ(vn)|V| ssi il y a une positionitelle que l i < L l i et l j = l j pour toutj<i. Faites attention au fait que chaque étiquette enSpeut être affectée à plusieurs sommets enV(sinon le problème est trivial).l<LEXlili<Llilj=ljj<iSV

Ce problème peut être énoncé soit dans une variante de calcul («calculer le tri topologique lexicographiquement minimal») soit dans une variante de décision («ce mot d'entrée est-il le tri topologique minimal?»). Ma question est, quelle est la complexité de ce problème ? Est-ce en PTIME (ou en FP, pour la variante de calcul) ou est-il NP-difficile? Si le problème général est NP-difficile, je suis également intéressé par la version où l'ensemble d'étiquettes possibles est fixé à l'avance (c'est-à-dire qu'il n'y a qu'un nombre constant d'étiquettes possibles).S

Remarques:

Voici un petit exemple du monde réel pour motiver le problème. Nous pouvons voir le DAG comme représentant les tâches d'un projet (avec une relation de dépendance entre elles) et les étiquettes sont des entiers représentant le nombre de jours que prend chaque tâche. Pour terminer le projet, il me faudra le même temps total, peu importe l'ordre que je choisis pour les tâches. Cependant, je voudrais impressionner mon patron, et pour ce faire, je veux terminer autant de tâches que possible le plus rapidement possible (de manière gourmande, même si cela signifie être très lent à la fin car les tâches les plus difficiles restent). Le choix de l'ordre lexicographiquement minimal optimise le critère suivant: je souhaite choisir un ordre tel qu'il n'y ait pas d'autre ordre o et un nombre de joursoo où aprèsn jours j'aurais fini plus de tâches avec l'ordre o qu'avec l'ordre o (ie si mon patron regarde au temps n , je donne une meilleure impression avec o ), mais pour tout m < n j'ai fini pas moins de tâches avec commande o qu'avec commande o .noonom<noo

Pour donner un aperçu du problème: Je sais déjà par les réponses précédentes que le problème connexe suivant est difficile: "existe-t-il un tri topologique qui réalise la séquence suivante"? Cependant, le fait ici que je veuille une séquence minimale pour cet ordre lexicographique semble contraindre beaucoup les éventuels ordres topologiques qui peuvent y parvenir (en particulier les réductions de ces autres réponses ne semblent plus fonctionner). Intuitivement, il y a beaucoup moins de situations où nous avons un choix à faire.

Notez qu'il semble y avoir des reformulations intéressantes des problèmes en termes de couverture d'ensemble (lors de la limitation du problème aux DAG bipartites, c'est-à-dire de hauteur deux): étant donné un ensemble d'ensembles, les énumérer dans un ordre qui minimise lexicographiquement la séquence | S 1 | , | S 2S 1 | , | S 3( S 1S 2 ) | , , | S n(S1,,Sn|S1||S2S1||S3(S1S2)|. Le problème peut également être reformulé sur des graphiques non orientés (étendre progressivement une zone connectée du graphique en suivant l'ordre qui minimise la séquence lexicographique des étiquettes non couvertes). Cependant, en raison du fait que la séquencedoitêtre toujours gourmande par définition de l'ordre lexicographique, je ne peux pas faire fonctionner les réductions (par exemple, de l'arbre de Steiner).|Sn(S1Sn1)|

Merci d'avance pour vos idées!

a3nm
la source

Réponses:

12

Avec plusieurs copies de la même étiquette autorisées, le problème est NP-difficile, via une réduction des cliques dans les graphiques. Étant donné un graphique dans lequel vous voulez trouver une k -clique, faites un DAG avec un sommet source pour chaque sommet de G , un sommet plongeur pour chaque bord de G et un bord dirigé x y chaque fois que x est un sommet de G qui forme une extrémité du bord y . Donnez aux sommets de G la valeur d'étiquette 1 et les bords de G à la valeur d'étiquette 0 .GkGGxyxGyG1G0

Ensuite, il y a une -clique dans G si et seulement si le premier ordre topologique lexicographiquement forme une séquence de k 1 et ( kkGk 1 0, aveci-10suivant leième1. Par exemple, une clique à six sommets serait représentée par la séquence110100100010000100000. Il s'agit de la séquence lexicographiquement la plus petite qui pourrait éventuellement commencer un ordre topologique d'un DAG étiqueté donné par cette construction (remplacer l'un des1par un0donnerait une séquence avec plus de bords que ce qui pourrait être trouvé dans un graphique simple avec celui plusieurs sommets) et cela ne peut être le début d'un ordre topologique que lorsqueGcontient la clique souhaitée.(k2) 0i1 0i111010010001000010000010G

David Eppstein
la source
Oh, je n'avais pas pensé aux cliques. C'est une belle réduction, merci beaucoup! Cela montre donc que le problème de calcul est NP-difficile, même avec l'alphabet à étiquette fixe ). Cela implique également que le problème de décision "est la séquence lexicographiquement la plus petite inférieure à celle-ci" est également NP-difficile (vous pouvez l'utiliser pour calculer le minimum avec la recherche binaire). La seule question supplémentaire que je vois est de savoir si le problème "est cette séquence d'entrée exacte la séquence minimale" est également NP-difficile. (Avec lui, vous ne pouvez pas tester facilement si le mot minimal commence par un préfixe.) Avez-vous une idée pour celui-là? {0,1}
a3nm
1
Je soupçonne que le problème "est cette séquence exacte réalisable" est NP-complet, mais je n'ai pas de réduction à portée de main. "Est-ce que cette séquence exacte est la séquence minimale" devrait être au deuxième niveau de la hiérarchie polynomiale, car elle nécessite une combinaison de quantification existentielle (est-elle réalisable) et de quantification universelle (sont toutes des séquences réalisables au moins aussi grandes).
David Eppstein
En fait, je sais déjà que tester si une séquence exacte est réalisable est NP-difficile (sur un alphabet avec 3 étiquettes) par une réduction de 3 partitions unaires par Marzio de Biasi esquissé ici: cstheory.stackexchange.com/a/19415 . Mais je pense que cela ne dit pas le statut du problème "est-ce la séquence minimale réalisable": en demandant si une certaine séquence est réalisable, en général, elle aura peu de chance d'être minimale dans un ordre lexicographique. Quoi qu'il en soit, ce que votre réduction montre est toujours très intéressant, merci encore! :)
a3nm
2

Selon cette référence (1), le problème d'ordre topologique lexicographiquement premier est NLOG-complet.

Vous voudrez peut-être jeter un coup d'œil plus approfondi à l'article pour vous assurer qu'il couvre le ou les cas qui vous intéressent. En particulier, sur la base de la version du rapport technique (pdf) de cet article, il semble qu'ils ' re traiter l'ordre lexicographique des sommets comme strict (par exemple: dans votre notation, pour u v ), mais je ne suis pas sûr que cela affecte l'applicabilité du résultat.λ(u)λ(v)uv

  1. Shoudai, Takayoshi. " Le premier problème d'ordre topologique lexicographiquement est NLOG-complet. " Lettres de traitement de l'information 33.3 (1989): 121-124.
mhum
la source
4
NLOG-complete est un sous-ensemble de temps polynomial, et (selon la phrase "Faites attention" dans le premier paragraphe du problème) rendre les étiquettes des sommets distincts rend le problème facilement résolu par un algorithme gourmand de temps polynomial. La vraie question est de savoir ce qui se passe lorsque les étiquettes ne sont pas distinctes.
David Eppstein
C'est un bon point. Il est maintenant clair d'après votre réponse que la répétition des étiquettes rend le problème plus difficile que le cas des étiquettes uniques.
mhum