El problema del conjunto k-dominante mínimo es un problema de optimización combinatoria NP-Difícil. Las aplicaciones en el mundo real van desde las redes de comunicación hasta problemas de localización de instalaciones. Dado un grafo, el objetivo es encontrar un subconjunto de vértices dominantes con mínima cardinalidad, de forma que todo vértice que no pertenezca a este subconjunto sea adyacente al menos a k vértices dominantes. Dada la complejidad del problema, se propone una metaheurística para su resolución, una Búsqueda de Vecindad Variable (VNS). Tanto las decisiones tomadas a lo largo de este trabajo, como las componentes del algoritmo, han sido validadas mediante experimentos computacionales. Además, se incluye una comparativa con la propuesta más reciente de la literatura: Restart Local Search with Relaxed Configuration Checking (RLS_RCC). El VNS propuesto obtiene una desviación promedio de 0.34% demostrando ser una aproximación competitiva para resolver el problema del conjunto k-dominante mínimo.