PROFILPELAJAR.COM

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.

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].

Références

↑ Giuseppe Di Battista, Peter Eades, Roberto Tamassia et Ioannis G. Tollis, « Layered Drawings of Digraphs », dans Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1998 (ISBN 9780133016154), p. 265–302.
↑ 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 », 2001 (DOI 10.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. », 1972, p. 85–103.
↑ (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5).
↑ 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, n^o 5,‎ 2008 (DOI 10.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, 1992 (lire en ligne).
↑ ^{a et b} Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Minimum Feedback Arc Set », dans A compendium of NP optimization problems, 2000 (lire en ligne).
↑ Irit Dinur et Samuel Safra, « On the hardness of approximating minimum vertex cover », Annals of Mathematics, vol. 162, n^o 1,‎ 2005, p. 439–485 (DOI 10.4007/annals.2005.162.439, lire en ligne).
↑ G. Even, J. Naor, B. Schieber et M. Sudan, « Approximating minimum feedback sets and multicuts in directed graphs », Algorithmica, vol. 20, n^o 2,‎ 1998, p. 151–174 (DOI 10.1007/PL00009191, MR 1484534).
↑ 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), 1990 (lire en ligne), p. 236–243.
↑ P. Eades, X. Lin et W. F. Smyth, « A fast and eﬀective heuristic for the feedback arc set problem », Information Processing Letters, vol. 47,‎ 1993, p. 319–323 (DOI 10.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), 2007 (DOI 10.1145/1250790.1250806, MR 2402432), 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 », 2010, 3–14 p. (DOI 10.1007/978-3-642-17517-6_3).
↑ Refael Hassin et Shlomi Rubinstein, « Approximations for the maximum acyclic subgraph problem », Information Processing Letters, vol. 51, n^o 3,‎ 1994, p. 133–140 (DOI 10.1016/0020-0190(94)00086-7)
↑ (en) Steven Skiena, The Algorithm Design Manual, 2nd, 2010, 730 p. (ISBN 978-1-84996-720-4 et 1-84996-720-2), p. 348 et 559–561.