¿Cuál es la siguiente variación de Set Cover conocida como?

15

¿Cuál es la siguiente variación en la cubierta del set conocida como?

Dado un conjunto S, una colección C de subconjuntos de S y un entero positivo K, ¿existen K conjuntos en C de manera que cada par de elementos de S se encuentre en uno de los subconjuntos seleccionados?

Nota: No es difícil ver que este problema es NP-Completo: dado un problema de cobertura de conjunto normal (S, C, K), haga tres copias de S, diga S ', S' 'y S' '', luego cree sus subconjuntos como S '' ', | S | subconjuntos de la forma {a '} U {x en S' '| x! = a} U {a '' '}, | S | subconjuntos de la forma {a ''} U {x en S '| x! = a} U {a '' '}, {a', a '' | a en C_i}. Entonces podemos resolver el problema de la cubierta del conjunto con K subconjuntos si podemos resolver el problema de la cubierta del par con K + 1 + 2 | S | subconjuntos.

Esto se generaliza a triples, etc. Me gustaría poder no perder media página probando esto, y probablemente no sea lo suficientemente obvio como para descartarlo como trivial. Ciertamente es suficientemente útil que alguien lo haya probado, pero no tengo idea de quién o dónde.

Además, ¿hay un buen lugar para buscar resultados de NP-Completeness que no estén en Garey y Johnson?

np-hardness set-cover cc.complexity-theory deinst
fuente

Respuestas:

7

Para responder a su segunda pregunta, el compendio Kahn-Crescenzi de resultados de dureza NP es una fuente valiosa para resultados de dureza, y también cubre muchas variantes de problemas centrales de G&J. La entrada para la portada del set es un buen ejemplo de esto.

Suresh Venkat
fuente
2
Lo había visto antes, y sí, ayuda, pero ni siquiera comienza a arañar la superficie de lo que se ha demostrado NP-Complete. Para dar otro ejemplo, me llevó mucho más tiempo encontrar la prueba de Uehara de que Vertex Cover estaba completa en NP en un gráfico plano cúbico 3 conectado de lo que me llevó probarlo. (Su prueba era mucho más limpia que la mía.)
desde el
7

Parece que está generalizando la cobertura del conjunto para considerar no solo los elementos de S, sino todos los subconjuntos de tamaño M de S. Podemos enunciar el problema de manera más general:

"Dado un conjunto S, una colección C de subconjuntos de S y un entero positivo m, ¿cuál es el número más pequeño de elementos de C de manera que cada subconjunto tamaño S de M se encuentre en uno de los elementos seleccionados de C?"

Esto realmente me parece una generalización bastante obvia de la cobertura del set, y no una en la que deba pasar el tiempo probando NP-complete más allá de una sola línea. Después de todo, elegir m = 1 recupera el problema de la cubierta del conjunto original. ¿Quizás esta formulación más general es lo suficientemente buena para sus propósitos como para evitar tener que entrar en detalles?

Su pregunta sobre un conjunto actualizado de resultados de completitud de NP es buena y merece su propia pregunta. Crescenzi y Kann han creado un compendio útil en línea aquí .

En segundo lugar, apenas es generalizado, pero el Manual de diseño de algoritmos de Steven Skiena es a menudo una primera parada útil para una gran cantidad de problemas, y está disponible en línea en parte .

Anand Kulkarni
fuente
Estoy interesado solo en m = 2. Puede ser que haya una prueba de una línea, pero dicha prueba se me escapa. Creo que lo dije claramente en la segunda oración de la pregunta.
desde el
Disculpas; ¡No quise sugerir que hay una pequeña prueba en el caso de pares! La prueba de una línea que sugerí está solo en la versión general del problema: "el caso especial de m = 1 recupera la cubierta del conjunto estándar". Como señala, la prueba en el caso de pares es obvia (introduzca elementos ficticios y conjuntos en la cubierta del conjunto estándar para generar la cubierta del conjunto emparejado), pero sí, tomaría algunas líneas para mostrar que es formal. Veré si puedo encontrar alguna referencia en la literatura.
Anand Kulkarni