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.
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.
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.
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].
↑Oliver Bastert, Christian Matuszewski, Michael Kaufmann et Dorothea Wagner, « Layered drawings of digraphs », dans Drawing Graphs: Methods and Models, vol. 2025, Springer-Verlag, coll. « Lecture Notes in Computer Science », (DOI10.1007/3-540-44969-8_5), p. 87–120.
↑Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, New York, Plenum,, coll. « Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y. », , p. 85–103.
↑Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan et Igor Razgon, « A fixed-parameter algorithm for the directed feedback vertex set problem », Journal of the ACM, vol. 55, no 5, (DOI10.1145/1411509.1411511).
↑Viggo Kann, On the Approximability of NP-complete Optimization Problems (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, (lire en ligne).
↑ a et bPierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Minimum Feedback Arc Set », dans A compendium of NP optimization problems, (lire en ligne).
↑B. Berger et P. Shor, « Approximation algorithms for the maximum acyclic subgraph problem », dans Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90), (lire en ligne), p. 236–243.
↑P. Eades, X. Lin et W. F. Smyth, « A fast and effective heuristic for the feedback arc set problem », Information Processing Letters, vol. 47, , p. 319–323 (DOI10.1016/0020-0190(93)90079-O).
↑Claire Kenyon-Mathieu et Warren Schudy, « How to rank with few errors: a PTAS for weighted feedback arc set on tournaments », dans Proc. 39th ACM Symposium on Theory of Computing (STOC '07), (DOI10.1145/1250790.1250806, MR2402432), p. 95–103. Voir aussi la version détailée.
↑M. Karpinski et W. Schudy, « Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament », dans Proc. 21st ISAAC (2010), vol. 6506, coll. « Lecture Notes in Computer Science », , 3–14 p. (DOI10.1007/978-3-642-17517-6_3).
↑Refael Hassin et Shlomi Rubinstein, « Approximations for the maximum acyclic subgraph problem », Information Processing Letters, vol. 51, no 3, , p. 133–140 (DOI10.1016/0020-0190(94)00086-7)
