Inspirado en muchas aplicaciones de detección de interbloqueos, el conjunto de vértices de retroalimentación se define como un conjunto de vértices en un grafo no dirigido, cuya eliminación daría como resultado un grafo sin ciclo. El Problema del Conjunto de Vértices de Retroalimentación, conocido por ser NP-completo, consiste en buscar un conjunto de vértices de retroalimentación con la cardinalidad mínima para beneficiar la recuperación del interbloqueo. Para abordar el problema, este artículo presenta NewkLS_FVS (LS, búsqueda local; FVS, conjunto de vértices de retroalimentación), un algoritmo de búsqueda local basado en la profundidad variable con un esquema aleatorizado para optimizar la eficiencia y el rendimiento. Se realizan simulaciones experimentales para comparar el algoritmo con metaheurísticas recientes, y los resultados computacionales muestran que el algoritmo propuesto puede superar a otros algoritmos de vanguardia y generar soluciones satisfactorias para la mayoría de los benchmarks DIMACS.