En théorie des graphes, un coupe-cycles de sommets, ou en anglaisLa 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 : . Voir le plan du livre en ligne., 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 É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.
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 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).
Pour tout entier k, la famille des graphes dont le coupe-cycles minimum est bornée par k, est une famille close par mineur.
Algorithmique Le problème algorithmique 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 Le problème dans sa version décisionnelle est NP-complet, et fait partie des 21 problèmes NP-complets de Karp.
Approximation Il existe un algorithme d'approximation de ratio 2, pour le problème non orienté, avec poids.. Le problème est APX-complet par réduction au problème de couverture par sommets.
Notes et références
Liens externes .
Catégorie:Théorie des graphes Catégorie:Problème algorithmique Catégorie:Problème NP-complet