Problème de la plus longue chaîne
# Problème de la plus longue chaîne

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

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.

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.

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.

## Graphes acycliques et chemins critiques

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. 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, ou en utilisant un algorithme direct comme celui donné ci-dessous.

### Calcul

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 :

* Faire un tri topologique du graphe acyclique donné.
* 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.
* 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

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. 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 et qui a la propriété qu'un arc relie des sommets sur des couches de valeurs croissantes.

## Approximation

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 $n/\exp(\Omega ({\sqrt {\log n}}))$ et qui n'est pas considéré comme très satisfaisant. 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 $2^{(\log n)^{1-\epsilon }}$ pour un $\epsilon >0$ donné; toutefois, il y a un grand écart entre ce résultat d'impossibilité de l'approximation et les méthodes d'approximation connues. 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 $\epsilon >0$ le problème ne peut être approché avec un facteur $n^{1-\epsilon }$ sauf si P = NP, et sous certaines hypothèses plus fortes, il ne peut être approché avec un facteur $n/\log ^{2+\epsilon }n$. 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 $O(n/\log n)$.

## Complexité paramétrée

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 :

* 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 $d$ la profondeur de cet arbre.
* 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 $d$.
* Appliquer enfin un algorithme de programmation dynamique à cette décomposition en chemins pour déterminer un plus long chemin en temps $O(d!2^{d}n)$, où $n$ est le nombre de sommets du graphe.

Comme le chemin obtenu est de longueur au moins $d$, le temps de calcul peut aussi être borné par $O(\ell !2^{\ell }n)$, où $\ell$ est la longueur du plus long chemin. En utilisant la technique du codage de couleurs, la complexité en fonction de la longueur du chemin peut être réduite à une simple $exponentielle^,^,^,.$ 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 $W[1]$, ce qui montre que l'existence d'un algorithme fixed-parameter tractable est improbable.

## Familles particulières de graphes

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 $O(n^{4})$ pour un graphe à n sommets a été développé, basé sur la technique de LDFS (lexicographically depth-first search) ou « recherche en profondeur lexicographique $»^,.$

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.

## Articles liés

* Théorème de Gallai-Hasse-Roy-Vitaver, une relation de dualité entre plus longs chemins et colorations de graphes
* Longest uncrossed knight's path (en)
* Snake-in-the-box (en), la plus longue chaîne induite dans un hypercube
