Feedback arc set

vignette|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 darcs 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 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. 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.