Problema de división de conjuntos

En la teoría de la complejidad computacional , el problema de la división de conjuntos es el siguiente problema de decisión : dada una familia F de subconjuntos de un conjunto finito S , decidir si existe una partición de S en dos subconjuntos S ₁ , S ₂ tal que todos los elementos de F sean divididos por esta partición, es decir, ninguno de los elementos de F está completamente en S ₁ o S _2. La división de conjuntos es uno de los problemas NP-completos clásicos de Garey y Johnson . ^{[ 1 ]} El problema a veces se denomina 2-colorabilidad de hipergrafos .

La versión de optimización de este problema se llama división de conjunto máximo y requiere encontrar la partición que maximiza el número de elementos divididos de F. Es un problema APX-completo ^{[ 2 ]} y por lo tanto en NPO .

El problema de la división de conjuntos k se plantea de la siguiente manera: dados S , F y un entero k , ¿existe una partición de S que divida al menos k subconjuntos de F ? La formulación original es el caso restringido con k igual a la cardinalidad de F. La división de conjuntos k es tratable con parámetros fijos , es decir, si k se toma como un parámetro fijo, en lugar de una parte de la entrada, entonces existe un algoritmo polinomial para cualquier k fijo . Dehne, Fellows y Rosamond presentaron un algoritmo que lo resuelve en tiempo${\displaystyle O(f(k)n^{c})}$ para alguna función f y constante c . ^{[ 3 ]}

Cuando cada elemento de F se restringe a tener una cardinalidad exactamente k , la variante de decisión se llama división de k conjuntos E y la versión de optimización división de k conjuntos E máxima . Para k > 2, la primera sigue siendo NP-completa, y para k ≥ 2, la segunda sigue siendo APX-completa. ^{[ 4 ]} Para k ≥ 4, la división de k conjuntos E es resistente a la aproximación. Es decir, a menos que P=NP, no existe ningún algoritmo de aproximación de tiempo polinomial (factor) que funcione esencialmente mejor que una partición aleatoria. ^{[ 5 ] [ 6 ]}

La división de conjuntos ponderada es una variante en la que los subconjuntos en F tienen pesos y el objetivo es maximizar el peso total de los subconjuntos divididos.

La división de conjuntos es un caso especial del problema de satisfacibilidad no totalmente igual sin variables negadas. Además, la división de k conjuntos E es igual a la coloración de grafos no monocromática de hipergrafos k -uniformes . Para k = 2, la variante de optimización se reduce al conocido corte máximo . ^{[ 6 ]}