Conjunto de vértices de retroalimentación
En la disciplina matemática de la teoría de grafos , un conjunto de vértices de retroalimentación (FVS) de un gráfico es un conjunto de vértices cuya eliminación deja un gráfico sin ciclos ("eliminación" significa eliminar el vértice y todos los bordes adyacentes). De manera equivalente, cada FVS contiene al menos un vértice de cualquier ciclo en el gráfico. El número de conjunto de vértices de retroalimentación de un gráfico es el tamaño de un conjunto de vértices de retroalimentación más pequeño. El problema del conjunto de vértices de retroalimentación mínima es un problema NP-completo ; fue uno de los primeros problemas que se demostró que era NP-completo . Tiene amplias aplicaciones en sistemas operativos ,sistemas de bases de datos y diseño de chips VLSI .
El gráfico que queda después de eliminarlo es un bosque inducido (resp. un gráfico acíclico dirigido inducido en el caso de gráficos dirigidos ). Por lo tanto, encontrar un FVS mínimo en un gráfico es equivalente a encontrar un bosque inducido máximo (resp. gráfico acíclico dirigido máximo inducido en el caso de gráficos dirigidos ).
![G[V\setminus X]](https://wikimedia.org/api/rest_v1/media/math/render/svg/1166277c8d75dce9d8ea1f3ede58bd79c083211d)
Karp (1972) mostró que el problema FVS mínimo para grafos dirigidos es NP-completo . El problema sigue siendo NP-completo en gráficos dirigidos con un máximo de grado de entrada y salida de grado dos, y en gráficos planos dirigidos con un máximo de grado de entrada y de salida tres. [1]
La reducción de Karp también implica la NP-completitud del problema FVS en grafos no dirigidos, donde el problema permanece NP-duro en grafos de máximo grado cuatro. El problema FVS se puede resolver en tiempo polinomial en gráficos de máximo grado como máximo tres. [2]
El problema de optimización NP correspondiente de encontrar el tamaño de un conjunto mínimo de vértices de retroalimentación se puede resolver en el tiempo O (1.7347 n ), donde n es el número de vértices en el gráfico. [3] En realidad, este algoritmo calcula un bosque inducido máximo y, cuando se obtiene dicho bosque, su complemento es un conjunto de vértices de retroalimentación mínima. El número de conjuntos de vértices de retroalimentación mínimos en un gráfico está limitado por O (1,8638 n ). [4] El problema del conjunto de vértices con retroalimentación dirigida todavía se puede resolver en el tiempo O* (1,9977 n ), donde n es el número de vértices en el gráfico dirigido dado.[5] Las versiones parametrizadas de los problemas dirigidos y no dirigidos son manejables con parámetros fijos . [6]
En gráficos no dirigidos de máximo grado tres, el problema del conjunto de vértices de retroalimentación se puede resolver en tiempo polinomial , transformándolo en una instancia del problema de paridad matroide para matroides lineales . [7]