Ensemble de sommets de retour

Le problème de l'ensemble de sommets de retour (Feedback Vertex Set, FVS) en théorie des graphes et en informatique consiste à trouver le plus petit sous-ensemble de sommets dans un graphe non orienté tel que leur suppression entraîne un graphe sans cycles, c'est-à-dire une forêt. L'objectif du problème FVS est de minimiser la taille de l'ensemble de sommets de retour, et ce problème est NP-difficile, ce qui signifie que la recherche d'une solution optimale présente une complexité algorithmique élevée. Pour les graphes orientés, un ensemble de sommets de retour fait référence à un sous-ensemble de sommets dont la suppression entraîne un graphe orienté acyclique (DAG). Le problème FVS a une valeur d'application significative dans l'optimisation des structures de réseau et la réduction des dépendances cycliques des systèmes.