Coupe-cycles de sommets
En théorie des graphes, un coupe-cycles de sommets, ou feedback vertex set en anglais[1], est un ensemble de sommets d'un graphe, tel que le retrait de ces nœuds laisse le graphe acyclique. Autrement dit, c'est un ensemble de nœuds ayant une intersection non nulle avec chaque cycle.
Le problème du coupe-cycle de sommets, est un problème algorithmique d'optimisation combinatoire, qui consiste à trouver un coupe-cycles de sommets de taille minimum.
Définition
[modifier | modifier le code]Étant donné un graphe non orienté G=(V,E), un coupe-cycles C est un sous-ensemble de V, tel que le graphe G restreint à V privé de C est acyclique, c'est-à-dire est une forêt[2].
On peut associer à chaque sommet s de G un poids w(s). On peut aussi considérer un graphe orienté, il s'agit alors de couper tous les cycles orientés.
Propriétés
[modifier | modifier le code]Le théorème d'Erdős-Pósa dit qu'il existe une fonction f, tel que pour tout entier k, tout graphe possède ou bien k cycles disjoints (par leurs sommets) ou bien un coupe-cycles de taille f(k). De plus, f(k) = O(k log k)[3].
Pour tout entier k, la famille des graphes dont le coupe-cycles minimum est bornée par k, est une famille close par mineur[4].
Algorithmique
[modifier | modifier le code]Le problème algorithmique
[modifier | modifier le code]Le problème algorithmique pour le cas non orienté, et sans poids est le suivant :
- Entrée : Un graphe G
- Tâche : Trouver un coupe-cycles de sommets de cardinal minimum.
Les cas orientés et avec poids se déduisent facilement.
Algorithmes et complexité exacte
[modifier | modifier le code]Le problème dans sa version décisionnelle est NP-complet, et fait partie des 21 problèmes NP-complets de Karp[5].
Approximation
[modifier | modifier le code]Il existe un algorithme d'approximation de ratio 2, pour le problème non orienté, avec poids[6]. Le problème est APX-complet par réduction au problème de couverture par sommets.
Notes et références
[modifier | modifier le code]- La traduction coupe-cycles de sommets est notamment présente dans le chapitre 6 de la traduction par N. Schabanel de l'ouvrage de référence : (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7). Voir le plan du livre en ligne.
- (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 6 (« Coupe-cycles de sommets »)
- (en) Reinhard Diestel, Graph Theory [détail des éditions], chap. 2.3 (« Packing and covering »), p. 47
- Michael J. Dinneen, Kevin Cattell and et Michael R. Fellows, « Forbidden minors to graphs with small feedback sets », Discrete Mathematics, vol. 230, nos 1-3, , p. 215-252 (lire en ligne)
- (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
- Vineet Bafna, Piotr Berman et Toshihiro Fujito, « A 2-approximation algorithm for the undirected feedback vertex set problem », SIAM Journal on Discrete Mathematics, vol. 12, no 3, , p. 289-297 (DOI 10.1137/S0895480196305124, MR 1710236).
Liens externes
[modifier | modifier le code]- (en) Viggo Kann, « Minimum feedback vertex set », sur A compendium of NP optimization problems, .
