Tri topologique lexicographiquement minimal d'un DAG étiqueté

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 $G = (V, E)$$\lambda$$V$$L$$<_L$$G$$\lambda$$G$$V$$\mathbf{v} = v_1, \ldots, v_n$ , 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 < $i \neq j$$v_i$$v_j$$G$$i < j$$S$$\mathbf{l} = \lambda(v_1), \ldots, \lambda(v_n)$$|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).$\mathbf{l} <_{\text{LEX}} \mathbf{l'}$$i$$l_i <_L l_i'$$l_j = l'_j$$j < i$$S$$V$

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 jours$o$$o'$ où après$n$ 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 .$n$$o'$$o$$n$$o'$$m < n$$o'$$o$

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 2 ∖ S 1 | , | S 3 ∖ ( S 1 ∪ S 2 ) | , … , | S n ∖ $S_1, \ldots, S_n$$|S_1|$$|S_2 \backslash S_1|$$|S_3 \backslash (S_1 \cup S_2)|$$\ldots$. 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).$|S_n \backslash (S_1 \cup \cdots \cup S_{n-1})|$

Merci d'avance pour vos idées!

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 .$G$$k$$G$$G$$xy$$x$$G$$y$$G$$1$$G$$0$

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 ($k$$G$$k$ $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.$\tbinom{k}{2}$ $0$$i-1$ $0$$i$$1$$110100100010000100000$$1$$0$$G$

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.$\lambda(u) \neq \lambda(v)$$u \neq v$

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.