« Feedback arc set » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
m v1.41 - Correction syntaxique (Catégorie en anglais - Catégorie avant la dernière section - Ponctuation avant une référence - Référence en double - Orthographe et typographie)
ManiacParisien (discuter | contributions)
20 080 modifications
Aucun résumé des modifications
Ligne 5 : Ligne 5 :
En lien étroit avec le [[Coupe-cycles de sommets|feedback vertex set]], qui est un ensemble de sommets contenant au moins un sommet de chaque circuit dans le graphe orienté, et le [[Arbre couvrant de poids minimal|minimum spanning tree]], qui est la non-orienté variante du feedback arc set problème.
En lien étroit avec le [[Coupe-cycles de sommets|feedback vertex set]], qui est un ensemble de sommets contenant au moins un sommet de chaque circuit dans le graphe orienté, et le [[Arbre couvrant de poids minimal|minimum spanning tree]], qui est la non-orienté variante du feedback arc set problème.


Un minimum de feedback arc set (qui ne peuvent pas être réduits en taille par la suppression de tout bords) a la propriété supplémentaire que, si les arcs sont inversés plutôt que supprimé, alors le graphe reste acyclique. Trouver un petit ensemble avec cette propriété est une étape clé dans le dessin de graphes par couches<ref name="dett98">{{Citation}}.</ref>{{,}}<ref name="bm01">{{Citation}}.</ref>.
Un minimum de feedback arc set (qui ne peuvent pas être réduits en taille par la suppression de tout bords) a la propriété supplémentaire que, si les arcs sont inversés plutôt que supprimé, alors le graphe reste acyclique. Trouver un petit ensemble avec cette propriété est une étape clé dans le dessin de graphes par couches
<ref name="dett98">{{chapitre
| last1 = Di Battista | first1 = Giuseppe
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
| last4 = Tollis | first4 = Ioannis G.
| titre = Layered Drawings of Digraphs
| isbn = 9780133016154
| passage = 265–302
| publisher = [[Prentice Hall]]
| titre ouvrage = Graph Drawing: Algorithms for the Visualization of Graphs
| year = 1998}}.
</ref>{{,}}<ref name="bm01">
{{chapitre
| last1 = Bastert | first1 = Oliver
| last2 = Matuszewski | first2 = Christian
| editor1-last = Kaufmann | editor1-first = Michael
| editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner
| titre = Layered drawings of digraphs
| doi = 10.1007/3-540-44969-8_5
| passage = 87–120
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| titre ouvrage = Drawing Graphs: Methods and Models
| volume = 2025
| year = 2001}}.</ref>.


Il est parfois souhaitable de supprimer aussi peu d'arcs que possible, l'obtention d'un '''minimum de feedback arc set''', ou de manière équivalente un '''maximum de sous-graphe acyclique'''. C'est un  problème difficile au sens de la complexité des algorithmes, et pour lequel plusieurs approximative des solutions ont été développées.
Il est parfois souhaitable de supprimer aussi peu d'arcs que possible, l'obtention d'un '''minimum de feedback arc set''', ou de manière équivalente un '''maximum de sous-graphe acyclique'''. C'est un  problème difficile au sens de la complexité des algorithmes, et pour lequel plusieurs approximative des solutions ont été développées.
Ligne 13 : Ligne 38 :


=== Résultats théoriques ===
=== Résultats théoriques ===
Ce problème est particulièrement difficile dans les [[Graphe arête-connexe|''k''-edge connecté graphiques]] pour les grands ''k'', où chaque arête tombe dans de nombreux différents cycles. La décision de la version du problème, qui est NP-complet, demande si tous les cycles peuvent être cassés, en supprimant au plus ''k'' bords; c'était l'un de [[Richard Karp|Richard M. Karp]]'21 [[Problème NP-complet|NP-complet problèmes]], illustré par la réduction du [[Problème de couverture par sommets|vertex cover problème]]<ref>{{Citation}}</ref>{{,}}<ref name="dett98" />.
Ce problème est particulièrement difficile dans les [[Graphe arête-connexe|''k''-edge connecté graphiques]] pour les grands ''k'', où chaque arête tombe dans de nombreux différents cycles. La décision de la version du problème, qui est NP-complet, demande si tous les cycles peuvent être cassés, en supprimant au plus ''k'' bords; c'était l'un de [[Richard Karp|Richard M. Karp]]'21 [[Problème NP-complet|NP-complet problèmes]], illustré par la réduction du [[Problème de couverture par sommets|vertex cover problème]]<ref>
{{chapitre
| last = Karp | first = Richard M. | author-link = Richard M. Karp
| titre = Reducibility Among Combinatorial Problems
| location = New York
| passage = 85–103
| publisher = Plenum,
| series = Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.
| titre ouvrage = Complexity of Computer Computations
| year = 1972}}.
</ref>{{,}}<ref>
{{citation
| last1 = Garey | first1 = Michael R. | author1-link = Michael R. Garey
| last2 = Johnson | first2 = David S. | author2-link = David S. Johnson
| isbn = 0-7167-1045-5
| at = A1.1: GT8, p.&nbsp;192
| publisher = W.H. Freeman
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
| year = 1979}}.
</ref>.


Bien que la NP-complet, le feedback arc set problème est [[Complexité paramétrée|à paramètre fixe docile]]: il existe un algorithme pour le résoudre, dont le temps d'exécution est fixé de façon polynomiale en la taille de l'entrée de graphique (indépendant du nombre d'arêtes dans le jeu), mais exponentielle en le nombre d'arêtes dans le feedback arc set<ref name="dett98" />.
Bien que la NP-complet, le feedback arc set problème est [[Complexité paramétrée|à paramètre fixe docile]]: il existe un algorithme pour le résoudre, dont le temps d'exécution est fixé de façon polynomiale en la taille de l'entrée de graphique (indépendant du nombre d'arêtes dans le jeu), mais exponentielle en le nombre d'arêtes dans le feedback arc set<ref>{{article
| last1 = Chen | first1 = Jianer
| last2 = Liu | first2 = Yang
| last3 = Lu | first3 = Songjian
| last4 = O'Sullivan | first4 = Barry
| last5 = Razgon | first5 = Igor
| doi = 10.1145/1411509.1411511
| issue = 5
| journal = [[Journal of the ACM]]
| title = A fixed-parameter algorithm for the directed feedback vertex set problem
| volume = 55
| year = 2008}}.</ref>


Viggo Kann a montré, en 1992, que le minimum de feedback arc set problème est [[APX (complexité)|APX-dur]], ce qui signifie qu'il existe une constante ''c''tels que, en supposant que P≠NP, il n'existe pas de polynôme temps [[Algorithme d'approximation|approximation de l'algorithme]] qui trouveront toujours un bord de définir au plus ''c'' fois plus grand que le résultat optimal<ref name="dett98" />{{,}}<ref name="compendium">{{Citation}}.</ref>. <span>à partir de 2006</span><sup class="plainlinks noprint asof-tag update" style="display:none;">[//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit &#x5B;mise à jour&#x5D;]</sup>, la valeur la plus élevée de ''c'' pour laquelle une telle impossibilité résultat est connu est ''c'' = 1.3606<ref name="dett98" />. Le plus connu d'approximation de l'algorithme a ratio ''O''(log ''n'' log log ''n'')<ref name="compendium">{{Citation}}.</ref>{{,}}<ref name="dett98" />. Pour le problème dual, de rapprocher le nombre maximum d'arêtes dans un graphe acyclique, une approximation un peu mieux que 1/2 est possible<ref name="dett98" />{{,}}<ref name="dett98" />.
Viggo Kann a montré, en 1992, que le minimum de feedback arc set problème est [[APX (complexité)|APX-dur]], ce qui signifie qu'il existe une constante ''c''tels que, en supposant que P≠NP, il n'existe pas de polynôme temps [[Algorithme d'approximation|approximation de l'algorithme]] qui trouveront toujours un bord de définir au plus ''c'' fois plus grand que le résultat optimal<ref>{{ouvrage
| last = Kann | first = Viggo
| éditeur = Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm
| nature = Ph.D. thesis
| titre = On the Approximability of NP-complete Optimization Problems
| url = http://www.nada.kth.se/~viggo/papers/phdthesis.pdf
| year = 1992}}.</ref><ref name="compendium">{{chapitre
| last1 = Crescenzi | first1 = Pierluigi
| last2 = Kann | first2 = Viggo
| last3 = Halldórsson | first3 = Magnús
| last4 = Karpinski | first4 = Marek | author4-link = Marek Karpinski
| last5 = Woeginger | first5 = Gerhard | author5-link = Gerhard J. Woeginger
| titre = Minimum Feedback Arc Set
| titre ouvrage = A compendium of NP optimization problems
| url = http://www.nada.kth.se/~viggo/wwwcompendium/node20.html
| year = 2000}}.</ref>. En 2006, la valeur la plus élevée de ''c'' pour laquelle une telle impossibilité résultat est connu est ''c'' = 1.3606<ref>{{article
| first1=Irit | last1=Dinur
| first2=Samuel | last2=Safra | authorlink2=Shmuel Safra
| title=On the hardness of approximating minimum vertex cover
| journal=[[Annals of Mathematics]]
| volume=162 | number=1
| pages=439–485
| year=2005
| doi=10.4007/annals.2005.162.439
| url=http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf
}}. (Preliminary version in [[Symposium on Theory of Computing|STOC]] 2002, titled "The importance of being biased", {{doi|10.1145/509907.509915}}.)</ref>. Le plus connu d'approximation de l'algorithme a ratio ''O''(log ''n'' log log ''n'')<ref name="compendium"/>{{,}}<ref>{{article
| last1 = Even | first1 = G.
| last2 = Naor | first2 = J.
| last3 = Schieber | first3 = B.
| last4 = Sudan | first4 = M. | author4-link = Madhu Sudan
| doi = 10.1007/PL00009191
| issue = 2
| journal = [[Algorithmica]]
| mr = 1484534
| pages = 151–174
| title = Approximating minimum feedback sets and multicuts in directed graphs
| volume = 20
| year = 1998}}.</ref>. Pour le problème dual, de rapprocher le nombre maximum d'arêtes dans un graphe acyclique, une approximation un peu mieux que 1/2 est possible.<ref>{{chapitre
| last1 = Berger | first1 = B. | author1-link = Bonnie Berger
| last2 = Shor | first2 = P. | author2-link = Peter Shor
| titre = Approximation algorithms for the maximum acyclic subgraph problem
| passage = 236–243
| titre ouvrage = Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90)
| url = http://dl.acm.org/citation.cfm?id=320176.320203
| year = 1990}}.</ref>{{,}}<ref>{{article
| last1 = Eades | first1 = P. | author1-link = Peter Eades
| last2 = Lin | first2 = X.
| last3 = Smyth | first3 = W. F.
| doi = 10.1016/0020-0190(93)90079-O
| journal = Information Processing Letters
| pages = 319–323
| titre = A fast and effective heuristic for the feedback arc set problem
| volume = 47
| year = 1993}}.</ref>.


Si les graphes sont limités à [[Tournoi (graphe)|des tournois]], le problème qui en résulte est connu comme le ''minimum de feedback arc set problème sur les tournois'' (RAPIDE). Cela restreint problème admet un [[Schéma d'approximation en temps polynomial|polynôme de temps rapprochement régime]], et cela tient toujours pour une restriction de l'pondérée version du problème<ref name="MathieuSchudy">{{Citation}}. </ref>. Un subexponential fixe paramètre de l'algorithme pour le pondérée RAPIDE a été donné par [[Feedback arc set#CITEREFKarpinskiSchudy2010|Karpinski &#x26; Schudy (2010)]]<ref name="KarpinskiSchudy">{{Citation}}.</ref>.
Si les graphes sont limités à [[Tournoi (graphe)|des tournois]], le problème qui en résulte est connu comme le ''minimum de feedback arc set problème sur les tournois'' (RAPIDE). Cela restreint problème admet un [[Schéma d'approximation en temps polynomial|polynôme de temps rapprochement régime]], et cela tient toujours pour une restriction de l'pondérée version du problème
<ref name="MathieuSchudy">{{citation
| last1 = Kenyon-Mathieu | first1 = Claire
| last2 = Schudy | first2 = Warren
| contribution = How to rank with few errors: a PTAS for weighted feedback arc set on tournaments
| doi = 10.1145/1250790.1250806
| mr = 2402432
| pages = 95–103
| title = Proc. 39th ACM Symposium on Theory of Computing (STOC '07)
| year = 2007}}. See also [http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf author's extended version].</ref> Un subexponential fixe paramètre de l'algorithme pour le pondérée RAPIDE a été donné par {{harvsp|Karpinski|Schudy|2010}}<ref name="KarpinskiSchudy">{{chapitre
| last1 = Karpinski | first1 = M. | author1-link = Marek Karpinski
| last2 = Schudy | first2 = W.
| titre = Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
| doi = 10.1007/978-3-642-17517-6_3
| pages = 3–14
| series = Lecture Notes in Computer Science
| titre ouvrage = Proc. 21st ISAAC (2010)
| volume = 6506
| year = 2010}}.</ref>.


D'autre part, si les bords sont [[Graphe simple|non-orienté]], le problème de la suppression des bords pour faire le graphe de cycle libre est équivalent à trouver un [[Arbre couvrant de poids minimal|minimum spanning tree]], qui peut facilement être fait en temps polynomial.
D'autre part, si les bords sont [[Graphe simple|non-orienté]], le problème de la suppression des bords pour faire le graphe de cycle libre est équivalent à trouver un [[Arbre couvrant de poids minimal|minimum spanning tree]], qui peut facilement être fait en temps polynomial.
Ligne 27 : Ligne 153 :
* Correction d'un arbitraire [[permutation]] des sommets, c'est-à-dire, l'étiquette de 1 à n.
* Correction d'un arbitraire [[permutation]] des sommets, c'est-à-dire, l'étiquette de 1 à n.
* La construction de deux sousgraphes L et R, contenant les arêtes {{Formule|(''u'', ''v'')}} où {{Formule|''u'' < ''v''}}, et ceux où {{Formule|''u'' > ''v''}}, respectivement.
* La construction de deux sousgraphes L et R, contenant les arêtes {{Formule|(''u'', ''v'')}} où {{Formule|''u'' < ''v''}}, et ceux où {{Formule|''u'' > ''v''}}, respectivement.
Maintenant, à la fois L et R sont acycliques sousgraphes de G, et au moins l'un d'entre eux est au moins la moitié de la taille maximale de sous-graphe acyclique<ref>{{Cite book|authorlink=Steven Skiena|author-link=Steven Skiena}}</ref>.{{Rp|348}}
Maintenant, à la fois L et R sont acycliques sousgraphes de G, et au moins l'un d'entre eux est au moins la moitié de la taille maximale de sous-graphe acyclique<ref>
{{cite book
|last=Skiena |first=Steven
|title = The Algorithm Design Manual
|publisher=Springer Science+Business Media |edition=2nd |year=2010 |isbn=1-849-96720-2 |passage=348 et 559–561}}.</ref>.


== Références ==
== Références ==

Version du 24 novembre 2016 à 08:53

Cet article est en cours de réécriture ou de restructuration importante (indiquez la date de pose grâce au paramètre date).

Un utilisateur prévoit de modifier cet article pendant plusieurs jours. Vous êtes invité(e) à en discuter en page de discussion et à participer à son amélioration de préférence en concertation pour des modifications de fond.

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 circuits. Dans certaines applications, ces cycles sont indésirables, et on cherche à les éliminer et d'obtenir un graphe orienté acyclique (DAG). Une façon de le faire est de simplement supprimer des arcs du graphe pour briser les cycles. Un feedback arc set (FAS) ou de la rétroaction ensemble de bord est un ensemble d'arêtes qui, lorsqu'il est retiré du graphe, laisse un DAG. Dit d'une autre manière, c'est un ensemble contenant au moins un arc de chaque cycle dans le graphe.

En lien étroit avec le feedback vertex set, qui est un ensemble de sommets contenant au moins un sommet de chaque circuit dans le graphe orienté, et le minimum spanning tree, qui est la non-orienté variante du feedback arc set problème.

Un minimum de feedback arc set (qui ne peuvent pas être réduits en taille par la suppression de tout bords) a la propriété supplémentaire que, si les arcs sont inversés plutôt que supprimé, alors le graphe reste acyclique. Trouver un petit ensemble avec cette propriété est une étape clé dans le dessin de graphes par couches [1],[2].

Il est parfois souhaitable de supprimer aussi peu d'arcs que possible, l'obtention d'un minimum de feedback arc set, ou de manière équivalente un maximum de sous-graphe acyclique. C'est un  problème difficile au sens de la complexité des algorithmes, et pour lequel plusieurs approximative des solutions ont été développées.

feedback arc set minimal

Quand il y a  des coûts associés à la suppression  d'un arc, on veut supprimer aussi peu que possible les bords. La suppression d'une arête suffit dans un cycle simple, mais, en général, de déterminer le nombre minimum d'arêtes à supprimer est un problème NP-difficile problème qu'on appelle le minimum de feedback arc set ou maximum de sous-graphe acyclique problème.

Résultats théoriques

Ce problème est particulièrement difficile dans les k-edge connecté graphiques pour les grands k, où chaque arête tombe dans de nombreux différents cycles. La décision de la version du problème, qui est NP-complet, demande si tous les cycles peuvent être cassés, en supprimant au plus k bords; c'était l'un de Richard M. Karp'21 NP-complet problèmes, illustré par la réduction du vertex cover problème[3],[4].

Bien que la NP-complet, le feedback arc set problème est à paramètre fixe docile: il existe un algorithme pour le résoudre, dont le temps d'exécution est fixé de façon polynomiale en la taille de l'entrée de graphique (indépendant du nombre d'arêtes dans le jeu), mais exponentielle en le nombre d'arêtes dans le feedback arc set[5]

Viggo Kann a montré, en 1992, que le minimum de feedback arc set problème est APX-dur, ce qui signifie qu'il existe une constante ctels que, en supposant que P≠NP, il n'existe pas de polynôme temps approximation de l'algorithme qui trouveront toujours un bord de définir au plus c fois plus grand que le résultat optimal[6][7]. En 2006, la valeur la plus élevée de c pour laquelle une telle impossibilité résultat est connu est c = 1.3606[8]. Le plus connu d'approximation de l'algorithme a ratio O(log n log log n)[7],[9]. Pour le problème dual, de rapprocher le nombre maximum d'arêtes dans un graphe acyclique, une approximation un peu mieux que 1/2 est possible.[10],[11].

Si les graphes sont limités à des tournois, le problème qui en résulte est connu comme le minimum de feedback arc set problème sur les tournois (RAPIDE). Cela restreint problème admet un polynôme de temps rapprochement régime, et cela tient toujours pour une restriction de l'pondérée version du problème [12] Un subexponential fixe paramètre de l'algorithme pour le pondérée RAPIDE a été donné par Karpinski et Schudy 2010[13].

D'autre part, si les bords sont non-orienté, le problème de la suppression des bords pour faire le graphe de cycle libre est équivalent à trouver un minimum spanning tree, qui peut facilement être fait en temps polynomial.

Approximations

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

  • Correction d'un arbitraire permutation des sommets, c'est-à-dire, l'étiquette de 1 à n.
  • La construction de deux sousgraphes L et R, contenant les arêtes (u, v) où u < v, et ceux où u > v, respectivement.

Maintenant, à la fois L et R sont acycliques sousgraphes de G, et au moins l'un d'entre eux est au moins la moitié de la taille maximale de sous-graphe acyclique[15].

Références

  1. ↑ 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, (ISBN 9780133016154), p. 265–302.
  2. ↑ Oliver Bastert et Christian Matuszewski, « Layered drawings of digraphs », dans Drawing Graphs: Methods and Models, vol. 2025, Springer-Verlag, coll. « Lecture Notes in Computer Science », (DOI 10.1007/3-540-44969-8_5), p. 87–120.
  3. ↑ 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.
  4. ↑ « {{{1}}} ».
  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, no 5,‎ (DOI 10.1145/1411509.1411511).
  6. ↑ Viggo Kann, On the Approximability of NP-complete Optimization Problems, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, (lire en ligne).
  7. ↑ 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, (lire en ligne).
  8. ↑ Irit Dinur et Samuel Safra, « On the hardness of approximating minimum vertex cover », Annals of Mathematics, vol. 162,‎ , p. 439–485 (DOI 10.4007/annals.2005.162.439, lire en ligne). (Preliminary version in STOC 2002, titled "The importance of being biased", DOI 10.1145/509907.509915.)
  9. ↑ G. Even, J. Naor, B. Schieber et M. Sudan, « Approximating minimum feedback sets and multicuts in directed graphs », Algorithmica, vol. 20, no 2,‎ , p. 151–174 (DOI 10.1007/PL00009191, MR 1484534).
  10. ↑ 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.
  11. ↑ 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 (DOI 10.1016/0020-0190(93)90079-O).
  12. ↑ « {{{1}}} ». See also author's extended version.
  13. ↑ 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. (DOI 10.1007/978-3-642-17517-6_3).
  14. ↑ Refael Hassin et Shlomi Rubinstein, « Approximations for the maximum acyclic subgraph problem », Information Processing Letters, vol. 51, no 3,‎ , p. 133–140 (DOI 10.1016/0020-0190(94)00086-7)
  15. ↑ (en) Steven Skiena, The Algorithm Design Manual, 2nd, (ISBN 1-849-96720-2), p. 348 et 559–561.
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Feedback_arc_set&oldid=132091637 ».