Según Wikipedia, el problema del conjunto independiente es un caso especial del problema del conjunto de conjuntos . Pero, me parece que estos problemas son equivalentes.
El problema de la búsqueda de conjunto independiente es: dado un gráfico y un número entero , encuentre vértices, ninguno de los cuales es adyacente.
El problema de búsqueda de Set Packing es: dada una colección finita de conjuntos finitos y un número entero , encuentre conjuntos que están separados por pares.
Creo que son equivalentes en función de la siguiente reducción bidireccional:
→: Dado un problema de conjunto independiente en un gráfico , cree una colección de de conjuntos, donde para cada vértice hay un conjunto contiene todos los bordes adyacentes a . Ahora, cada conjunto de empaque en corresponde a un conjunto de vértices, de los cuales ninguno tiene un borde en común, es decir, este es un conjunto independiente en del mismo tamaño.
←: Dado un problema de empaquetado en una colección , cree un gráfico donde para cada conjunto hay un vértice , y hay un borde entre y si los conjuntos y cruzan. Ahora, cada conjunto de vértices independientes en corresponde a un conjunto de conjuntos de no se cruzan dos, es decir, este es un conjunto de conjuntos en del mismo tamaño.
Mi pregunta es: ¿es correcta mi reducción? Si es así, ¿son equivalentes estos problemas? ¿Es posible usar algoritmos de aproximación para un problema en el otro problema?
fuente