Feedback arc set

En théorie des graphes, un graphe orienté peut contenir des circuits, c'est-à-dire des chemins qui reviennent sur leur point de départ. Dans certaines applications, ces circuits sont indésirables, et on cherche à les éliminer pour obtenir un graphe orienté acyclique (souvent abrégé en DAG). Une façon de procéder est de simplement supprimer certains arcs du graphe pour couper les circuits. Un ensemble d'arcs de retour, ou coupe-cycles d'arcs communément appelé par son nom anglais un feedback arc set (FAS) est un ensemble d'arcs qui, lorsqu'il est supprimé du graphe, le transforme en graphe acyclique. Dit d'une autre manière, c'est un ensemble contenant au moins un arc de chaque circuit dans le graphe.

Ce graphe orienté n'a pas de circuits: il n'est pas possible de partir d'un sommet quelconque et de revenir à ce même point, en suivant les connexions dans la direction indiquée par les flèches.

Définitions

Un concept étroitement lié est celui de feedback vertex set, en français coupe-cycles de sommets ; c'est un ensemble de sommets contenant au moins un sommet de chaque circuit d'un graphe ; un arbre couvrant de poids minimal est la variante non-orienté problème du feedback arc set.

Un feedback arc set minimal est un ensemble d'arcs de retour de taille minimale, et qui n'est donc plus une feedback arc set si on lui enlève un de ses arcs ; un tel ensemble a la propriété supplémentaire que, si les arcs de retour sont inversés plutôt que supprimé, alors le graphe devient acyclique. Trouver un ensemble d'arcs de retour de taille minimale est une étape clé dans le dessin de graphes par couches^[1],[2].

L'obtention d'un feedback arc set set ou, de manière équivalente, d'un sous-graphe acyclique maximal, est un problème difficile au sens de la complexité des algorithmes, et pour lequel plusieurs solutions approximatives ont été développées.

Une variante complique encore le problème : c'est quand il y a des coûts associés à la suppression  d'un arc. On veut supprimer aussi peu d'arcs que possible, tout en choisissant ceux de coût minimal. La suppression d'une arc suffit dans un circuit simple, mais, en général, déterminer le nombre minimum d'arcs à supprimer est un problème NP-difficile ; en théorie de complexité des algorithmes, c'est le problème du feedback arc set minimal ou problème du sous-graphe acyclique maximal.

Résultats théoriques

La version de décision du problème du feedback arc set minimal demande si tous les circuits peuvent être supprimés en supprimant au plus k arcs; ce problème est NP-complet. C'est l'un des 21 problèmes NP-complets donnés par Richard M. Karp dans son célèbre article ; il le traite par réduction du problème de couverture par sommets^[3],[4].

Bien que NP-complet, le problème du feedback arc set est fixed-parameter tractable : il existe un algorithme pour le résoudre, dont le temps d'exécution est polynomial en la taille du graphe mais exponentiel en le nombre d'arcs dans le feedback arc set^[5].

Viggo Kann a montré, en 1992, que le problème du feedback arc set est APX-dur, ce qui signifie qu'il existe une constante c telle que, en supposant que P≠NP, il n'existe pas d'algorithme d'approximation en temps polynomial qui trouve toujours un ensemble d'arcs de taille au plus c fois plus grand que la taille du résultat optimal^[6],[7]. Une majoration de la constante c est c = 1.3606^[8]. Le meilleur algorithme d'approximation connu a ratio O(log n log log n)^[7],[9]. Pour le problème dual d'approximation du nombre maximum d'arcs dans un sous-graphe acyclique, un ratio légèrement au-dessus de 1/2 est connu^[10],[11].

Si les graphes sont restreints à des tournois, le problème est connu sous le nom de problème du feedback arc set sur les tournois (abrégé en FAST). Ce problème admet un schéma d'approximation en temps polynomial, et cela reste valable pour la version pondérée du problème^[12]. Un algorithme à complexité paramétrée sous-exponentielle pour le problème FAST pondéré a été donné par Karpinski et Schudy 2010^[13].

Si les arcs sont non-orientés, le problème de la suppression d'arêtes pour rendre le graphe acyclique équivalent à la recherche d'un arbre couvrant de poids minimal, ce qui peut être fait facilement en temps polynomial.

Un algorithme d'approximation

Plusieurs algorithmes d'approximation pour le problème ont été développés^[14]. Un algorithme particulièrement simple est le suivant:

• Numéroter les sommets de manière arbitraire de 1 à n.
• Construire deux sous-graphes L et R, contenant respectivement les arcs (u, v) où u < v, et ceux où u > v.

Clairement, les graphes L et R sont tous deux des sous-graphes acycliques du graphe donné, et l'un des deux contient au moins la moitié des arcs d'un sous-graphe acyclique de taille maximale^[15].