Bueno, así que sé que obviamente estoy haciendo algún tipo de error fácil aquí, desde el conjunto de la cubierta es NP-completo y min-costo max-flow está en P, pero no puedo averiguar lo que el error es.
Así, dado un universo $U$ y un conjunto $S$ tales que la unión de todos los conjuntos en $S$ es $U$, el conjunto de la cubierta problema pide el más pequeño subconjunto de $S$ tales que la unión de todos los conjuntos en que el subconjunto es $U$.
Mi pregunta, entonces, es por eso que no se puede construir un min-costo max gráfico de flujo de la siguiente manera:
- Crear un nodo para cada conjunto en $S$, y un nodo para cada elemento en $U$.
- Dibujar los bordes de la fuente para cada conjunto $A \in S$ con 1 costo y la capacidad infinita.
- Dibujar los bordes de cada elemento en $U$ a la pileta con coste 0 y de la capacidad de la unidad.
- Dibujar los bordes de cada conjunto en $S$ a cada uno de los elementos en $U$ que contiene con coste 0 y la capacidad infinita.
- Encontrar el mínimo costo max-flujo de la red resultante; los conjuntos de $A \in S$ que tienen un flujo a través de ellos debe constar de un conjunto de cubierta.
Wikipedia ofrece un ejemplo de problema con $U = \{1, 2, 3 ,4, 5\}$ e $S = \{ \{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\} \}$ -- aquí es un dibujo que hice para ilustrar.
El gráfico resultante tendrá $|S| + |U| + 2$ nodos, y $\Sigma_{A \in S} |A|+ |S| + |U| + 2$ bordes, lo que creo que debería ser polinomial en el tamaño de la entrada. Entonces, ¿qué estoy haciendo mal aquí? Gracias!
