Aller au contenu

Problème de la plus longue chaîne

Un article de Wikipédia, l'encyclopédie libre.
Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale.

En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.

Contrairement au problème de plus court chemin, qui peut être résolu en temps polynomial dans les graphes sans cycle de poids négatif, le problème de la plus longue chaîne est NP-complet; il ne peut donc être résolu en temps polynomial, sauf si P=NP. Des résultats complémentaires montrent que, de plus, ce problème est également difficile à résoudre de manière approchée. En revanche, il a une complexité linéaire pour les graphes orientés acycliques, et il a alors des applications importantes, par exemple dans la détermination du chemin critique dans des problèmes d'ordonnancement, comme ils sont modélisés dans la méthode PERT par exemple.

Un problème NP-difficile

[modifier | modifier le code]

Pour voir que le problème de la plus longue chaîne est NP-difficile, même dans des graphes non pondérés, on utilise une réduction au problème de la chaîne hamiltonienne : un graphe G possède une chaîne hamiltonienne si et seulement si la plus longue chaîne élémentaire dans G est de longueur n-1, où n est le nombre de sommets de G. Comme on sait que le problème de la chaîne hamiltonienne est NP-complet, cette réduction montre que le problème de la plus longue chaîne, vu comme problème de décision, est aussi NP-complet. Dans ce problème de décision, la donnée est formée d'un graphe G et d'un entier k; le résultat est « oui » si G possède une chaîne de longueur k ou plus, et « non » dans le cas contraire[1].

Maintenant, si le problème de la plus longue chaîne pouvait être résolu en temps polynomial, on pourrait s'en servir pour résoudre le problème de décision, en calculant d'abord une plus longue chaîne et en comparant ensuite sa longueur à l'entier k, deuxième paramètre du problème. Ceci montre que le problème de la plus longue chaîne est NP-difficile ; il n'est pas NP-complet dans la mesure où cette notion ne s'applique qu'à un problème de décision[2].

Dans un graphe complet pondéré, où les arêtes portent des poids non négatifs, le problème de la plus longue chaîne est le même que le problème du voyageur de commerce, puisque la plus longue chaîne passe toujours par tous les sommets[3].

Graphes acycliques et chemins critiques

[modifier | modifier le code]

Un chemin de poids maximal entre deux sommets s et t d'un graphe pondéré G est le même qu'un chemin de poids minimal entre s et t dans le graphe à poids opposés, noté −G, obtenu à partir de G en remplaçant chaque poids par sa valeur opposée. Par conséquent, si on peut trouver des chemins de poids minimal dans −G, on peut trouver des chemins de poids maximal dans G[4]. Toutefois, cette transformation n'est en général pas utile parce qu'elle crée des circuits de poids négatif dans −G, ce qui rend le calcul des chemins minimaux plus compliqué. En revanche si G est un graphe orienté acyclique, le graphe −G est tout aussi acyclique, et un chemin de poids maximal dans G peut être trouvé en temps linéaire en appliquant un algorithme linéaire de calcul de plus court chemin à −G[4], ou en utilisant un algorithme direct comme celui donné ci-dessous.

Calcul

[modifier | modifier le code]

On peut calculer un chemin de longueur maximale, dans un graphe orienté acyclique et non pondéré, en deux étapes : on cherche d'abord la longueur des plus longs chemins se terminant en un sommet v donné, pour tout v, puis on cherche la valeur maximale parmi ces longueurs.

Dans la première étape, on opère comme suit en deux phases :

  1. Faire un tri topologique du graphe acyclique donné.
  2. Pour les sommets v du graphe dans leur ordre topologique, calculer la longueur du plus long chemin finissant en v, en examinant les voisins antécédents de v, et en ajoutant 1 au maximum des longueurs calculées pour ces voisins. Si v n'a pas d'arc entrant, la longueur du plus long chemin arrivant en v est 0. Dans tous les cas, enregistrer la valeur calculée pour le sommet v.
  3. La longueur maximale des chemins dans le graphe est le maximum des valeurs calculées pour les sommets v.

Après avoir calculé la longueur du plus long chemin arrivant en v pour chaque sommet v, on trouve un chemin de longueur maximale comme suit ; on commence par choisir un sommet v avec la plus grande valeur enregistrée, puis en remontant, on cherche itérativement un voisin antécédent de v avec la grande valeur enregistrée. La suite de sommets visitée est la suite, en sens inverse, d'un chemin de longueur maximale.

Applications

[modifier | modifier le code]

Chemin critique. La méthode du chemin critique pour l’ordonnancement d'un ensemble de tâches ou activités utilise la construction d'un graphe orienté acyclique : les sommets représentent des étapes ou jalons du projet et les arcs des tâches qui doivent être accomplies entre une étape et la suivante ; chaque arc est pondéré par une estimation du temps nécessaire pour réaliser la tâche correspondante. Dans un tel graphe, un plus long chemin de l'étape initiale à l'étape finale est un chemin critique, dont la longueur décrit le temps total nécessaire pour achever le projet[4]. La méthode PERT fait usage de cette notion, avec des développements considérables pour notamment inclure des éléments tenant compte des impondérables.

Tracé de graphes. Une autre application des plus longs chemins dans les graphes acycliques est le dessin de graphes par niveau (en) : on attribue à chaque sommet v d'un graphe orienté acyclique G un niveau dont le numéro est la longueur du plus long chemin arrivant en v. On obtient ainsi une attribution de niveaux aux sommets de graphe avec un minimum de couches[5] et qui a la propriété qu'un arc relie des sommets sur des couches de valeurs croissantes.

Approximation

[modifier | modifier le code]

Comme le problème est difficile, on cherche des algorithmes d'approximation en temps polynomial, avec un ratio d'approximation aussi bon que possible et un temps qui ne croît que polynomialement avec la précision d'approximation souhaité.

Il existe un algorithme d'approximation en temps polynomial, dont le ratio d'approximation pour un graphe à n sommets est et qui n'est pas considéré comme très satisfaisant[6]. On peut montrer que, sous l'hypothèse P ≠ NP, il n'est pas possible d'approximer en temps quasi-polynomial déterministe la longueur de la chaîne la plus longue avec un ratio de pour un donné; toutefois, il y a un grand écart entre ce résultat d'impossibilité de l'approximation et les méthodes d'approximation connues[7]. Dans le cas de graphe orientés et non pondérés, on connaît des résultats plus précis pour l'impossibilité d'approximations. Pour tout le problème ne peut être approché avec un facteur sauf si P = NP, et sous certaines hypothèses plus fortes, il ne peut être approché avec un facteur [8]. La technique du codage de couleurs (en) peut être employée pour trouver un chemin de longueur logarithmique en fonction de la taille du graphe si un tel chemin existe, mais le ratio d'approximation n'est que [9].

Complexité paramétrée

[modifier | modifier le code]

Le problème de la plus longue chaîne est "fixed-parameter tractable" quand il est paramétré par la longueur de la chaîne. Il peut par exemple être résolu en temps linaire en la taille du graphe, mais exponentiel en la longueur de la chaîne, par la méthode suivante :

  1. Réaliser un parcours en profondeur du graphe, et retenir les arêtes parcourues lors des premières visites des sommets : l'arbre ainsi distingué est parfois appelé arbre de Trémaux. Soit la profondeur de cet arbre.
  2. Utiliser la suite de chemins de la racine aux feuilles dans l'arbre de Trémaux dans l'ordre de leur découverte, pour construire une décomposition arborescente du graphe de largeur arborescente .
  3. Appliquer enfin un algorithme de programmation dynamique à cette décomposition en chemins pour déterminer un plus long chemin en temps , où est le nombre de sommets du graphe.

Comme le chemin obtenu est de longueur au moins , le temps de calcul peut aussi être borné par , où est la longueur du plus long chemin[10]. En utilisant la technique du codage de couleurs, la complexité en fonction de la longueur du chemin peut être réduite à une simple exponentielle[9],[11],[12],[13]. Une technique similaire de programmation dynamique montre que le problème du plus long chemin est également fixed-parameter tractable quand il est paramétré par la largeur arborescente du graphe.

Pour des graphes dont la largeur de clique est bornée, le problème de la plus longue chaîne peut être résolu en temps polynomial par un algorithme de programmation dynamique. L'exposant dépend de la largeur de clique, de sorte que l'algorithme n'est pas fixed-parameter tractable. Le problème de la plus longue chaîne, paramétré par la largeur de clique, est un problème difficile pour la classe de complexité paramétrée , ce qui montre que l'existence d'un algorithme fixed-parameter tractable est improbable[14].

Familles particulières de graphes

[modifier | modifier le code]

Une famille de graphes où le problème peut être résolu en temps polynomial est formée des complémentaires de graphes de comparabilité ; pour ces graphes, un algorithme en pour un graphe à n sommets a été développé, basé sur la technique de LDFS (lexicographically depth-first search) ou « recherche en profondeur lexicographique »[15],[16].

D'autres classes où le problème peut être résolu en temps polynomial sont celles des graphes avec largeur arborescente ou largeur de clique bornées, ou la classe de graphes complètement séparables. Mais le problème reste NP-difficile pour d'autres familles comme les split graphs, les circle graphs ou les graphes planaires[17].

Articles liés

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]
  1. ↑ Alexander Schrijver, Combinatorial Optimization : Polyhedra and Efficiency, Volume 1, Springer (no 24), , 1881 p. (ISBN 978-3-540-44389-6, lire en ligne), p. 114.
  2. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], Exercice 34.1.1 Problème de la longueur du plus long chemin p. 945-946.
  3. ↑ Eugene L. Lawler, Combinatorial Optimization : Networks and Matroids, Courier Dover Publications, , 374 p. (ISBN 978-0-486-41453-9, lire en ligne), p. 64.
  4. ↑ a b et c (en) Robert Sedgewick et Kevin Daniel Wayne, Algorithms, Upper Saddle River, Addison-Wesley Professional, , 4e éd., 955 p. (ISBN 978-0-321-57351-3, lire en ligne), p. 661–666.
  5. ↑ Giuseppe Di Battista, Peter Eades, Roberto Tamassia et Ioannis G. Tollis, Graph Drawing : Algorithms for the Visualization of Graphs, Prentice Hall, (ISBN 978-0-13-301615-4), « Layered Drawings of Digraphs », p. 265–302.
  6. ↑ Harold N. Gabow et Shuxin Nie, « Finding long paths, cycles and circuits », International Symposium on Algorithms and Computation, Berlin, Springer Lecture Notes in Computer Science 5369,‎ , p. 752–763 (DOI 10.1007/978-3-540-92182-0_66, MR 2539968).
  7. ↑ David Karger, Rajeev Motwani et G. D. S. Ramkumar, « On approximating the longest path in a graph », Algorithmica, vol. 18, no 1,‎ , p. 82–98 (DOI 10.1007/BF02523689, MR 1432030).
  8. ↑ Andreas Björklund, Thore Husfeldt et Sanjeev Khanna, « Approximating longest directed paths and cycles », Proc. Int. Coll. Automata, Languages and Programming (ICALP), Berlin, Springer Lecture Notes in Computer Science 3142,‎ , p. 222–233 (MR 2160935).
  9. ↑ a et b Noga Alon, Raphael Yuster et Uri Zwick, « Color-coding », Journal of the ACM, vol. 42, no 4,‎ , p. 844–856 (DOI 10.1145/210332.210337, MR 1411787).
  10. ↑ Hans L. Bodlaender, « On linear time minor tests with depth-first search », Journal of Algorithms, vol. 14, no 1,‎ , p. 1–23 (DOI 10.1006/jagm.1993.1001, MR 1199244).
  11. ↑ Jianer Chen, Songjian Lu, Sing-Hoi Sze et Fenghui Zhang, « Improved algorithms for path, matching, and packing problems », Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07),‎ , p. 298–307 (ISBN 978-0-898716-24-5, lire en ligne).
  12. ↑ Ioannis Koutis, « Faster algebraic algorithms for path and packing problems », International Colloquium on Automata, Languages and Programming, Berlin, Springer, lecture Notes in Computer Science,‎ , p. 575–586 (DOI 10.1007/978-3-540-70575-8_47, MR 2500302, lire en ligne).
  13. ↑ Ryan Williams, « Finding paths of length k in O*(2k) time », Information Processing Letters, vol. 109, no 6,‎ , p. 315–318 (DOI 10.1016/j.ipl.2008.11.004, MR 2493730, arXiv 0807.3026).
  14. ↑ Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov et Saket Saurabh, « Clique-width: on the price of generality », Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09),‎ , p. 825–834 (lire en ligne).
  15. ↑ Michel Habib, « Parcours de graphes », Institut de recherche en informatique fondamentale (IRIF), (consulté le ).
  16. ↑ George B. Mertzios et Derek G. Corneil, « A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs », SIAM Journal on Discrete Mathematics, vol. 26, no 3,‎ , p. 940–963 (DOI 10.1137/100793529, lire en ligne).
  17. ↑ Kyriaki Ioannidou, George B. Mertzios et Stavros D. Nikolopoulos, « The longest path problem has a polynomial solution on interval graphs », Algorithmica, vol. 61, no 2,‎ , p. 320–341 (DOI 10.1007/s00453-010-9411-3, MR 2822187, lire en ligne).
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « longest path problem » (voir la liste des auteurs).

Lien externe

[modifier | modifier le code]
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_de_la_plus_longue_chaîne&oldid=192371740 ».