|
Coupe-cycles de sommetsEn 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É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ésLe 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]. AlgorithmiqueLe problème algorithmiqueLe problème algorithmique pour le cas non orienté, et sans poids est le suivant :
Les cas orientés et avec poids se déduisent facilement. Algorithmes et complexité exacteLe problème dans sa version décisionnelle est NP-complet, et fait partie des 21 problèmes NP-complets de Karp[5]. ApproximationIl 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
Liens externes
|
