¿Es esto NP-duro? No puedo probarlo.

11

Tengo un problema y supongo que es NP-hard, pero no puedo probarlo.

Aquí hay un gráfico de capas, donde la capa 0 es la capa más alta y la capa L la más baja.

hay un borde dirigido entre capas, donde un borde (A, B) indica que el nodo A puede [cubrir] el nodo B. Y cuando A puede cubrir B, cada nodo en cualquier camino de A a B puede cubrir B, B puede cubrir sí mismo.

Finalmente aquí viene un conjunto de nodos S. Necesito elegir otro conjunto de nodos ANS, y asegurarme de que para cada nodo q en S, exista un nodo p en ANS y p cubra q.

Para cada nodo hay un costo, y necesito hacer que el costo total de establecer ANS sea mínimo.

¿Es este un problema NP-difícil? Creo que sí, pero no puedo demostrarlo.

¿Usted me podría ayudar?

Muchas gracias.

graphs np qin.sun
fuente
El costo del nodo de la capa superior es más costoso en cualquier ruta en el gráfico.
Sí, de hecho parece NP difícil. Mire el problema similar de dejar de usar un conjunto mínimo de abandono. en.wikipedia.org/wiki/Set_cover_problem
¿Hay alguna restricción en el borde dirigido, como que los bordes solo conectan un nodo en la capa superior a un nodo en la capa inferior? ¿Puedo aclarar que no puede haber borde entre nodos en la misma capa?
justhalf
@justhalf No, no hay borde entre los nodos en la misma capa. Gracias :)
qin.sun

Respuestas:

6

Sí, este problema es definitivamente NP difícil. Estoy publicando esta respuesta ya que requiere prueba.

Si sigue este enlace http://en.wikipedia.org/wiki/Set_cover_problem , dice que la versión de optimización del problema de cobertura de conjunto mínimo es NP-Hard.

El problema en el enlace:

Dado un conjunto de elementos {1,2, ..., m} (llamado universo) y un conjunto S de n conjuntos cuya unión es igual al universo, el problema de la cobertura del conjunto es identificar el subconjunto más pequeño de S cuya unión es igual al universo. Por ejemplo, considere el universo U = {1, 2, 3, 4, 5} y el conjunto de conjuntos S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Claramente, la unión de S es U. Sin embargo, podemos cubrir todos los elementos con el siguiente número menor de conjuntos: {{1, 2, 3}, {4, 5}}

Puede relacionar esto con su problema de la siguiente manera:

S es el conjunto de nodos que cubren al menos un nodo en su conjunto de entrada. Esto se puede encontrar realizando un DFS en los nodos del conjunto de entrada con la dirección de los bordes invertidos.

Ahora, el problema descrito en el enlace es un caso especial de su problema, donde el costo de cada nodo es igual y solo desea minimizar el número de nodos (conjuntos).

Por lo tanto, su problema es aún más difícil de resolver en el caso general y, por lo tanto, es NP Hard.

Abhishek Bansal
fuente
Creo que esto es cierto con la definición del OP, pero tampoco especifica si puede "cubrir" un nodo con un borde en la misma capa que ese nodo. Si ese es el caso, entonces el problema parece un poco diferente. De lo contrario, si solo puede cubrir un nodo a través de un borde desde una capa superior, entonces parece ser equivalente a establecer la optimización de la cubierta
roliu
@roliu ¿Cómo importaría si los mismos nodos de capa se pueden cubrir o no? El problema, según tengo entendido, es que tenemos un gráfico dirigido con una ruta entre el nodo A a B significa que A cubre B.
Hm, no estoy seguro, supongo. Es extraño porque no creo que casi ninguna de la información en el OP sea realmente útil. Las capas parecen irrelevantes y también la transitividad. Principalmente estoy esperando que el OP aclare que realmente quiso decir algo diferente. En particular, puede demostrar que no solo es tan difícil como la cubierta del set, sino que es equivalente. Porque cualquier cobertura mínima en el problema del OP solo contendrá nodos vecinos de su conjunto de entrada S. Tal vez hay costos negativos o algo así ...
roliu