En la teoría de la complejidad computacional , el problema de 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 1 , S 2 tales que todos los elementos de F estén divididos por esta partición, es decir, ninguno de los elementos de F esté completamente en S 1 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 hipergrafo 2-colorabilidad .
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 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 manejable 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 a tiempo 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 denomina división de conjuntos E k y la versión de optimización max división de conjuntos E k . 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 conjuntos E k 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 ponderados 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 de no todos iguales sin variables negadas. Además, la división de conjuntos E k es igual a la coloración no monocromática de los hipergrafos k -uniformes . Para k = 2, la variante de optimización se reduce al corte máximo bien conocido . [6]
