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

É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

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

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^[5].

Approximation

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.