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 tal que todos los elementos de F sean dividido 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 & Johnson . [1] El problema a veces se denomina hipergrafía 2-colorabilidad .
La versión de optimización de este problema se llama división de conjuntos máximos y requiere encontrar la partición que maximice el número de elementos divididos de F. Es un problema APX completo [2] y, por tanto, en NPO .
El problema de división de conjuntos k se plantea de la siguiente manera: dados S , F y un número 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 del conjunto k es manejable con parámetros fijos , es decir, si k se considera un parámetro fijo, en lugar de una parte de la entrada, entonces existe un algoritmo polinómico para cualquier k fijo . Dehne, Fellows y Rosamond presentaron un algoritmo que lo resuelve en el tiempo para alguna función f y constante c . [3]
Cuando cada elemento de F está restringido a ser de cardinalidad exactamente k , la variante de decisión se llama división E k -set y la versión de optimización max E k división-set . Para k > 2 el primero permanece NP completo, y para k ≥ 2 el último permanece APX completo. [4] Para k ≥ 4, E k -Set Splitting es resistente a la aproximación. Es decir, a menos que P = NP, no existe un 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 del conjunto E k equivale a la coloración de gráficos no monocromáticos de k hipergráficos uniformes . Para k = 2, la variante de optimización se reduce al conocido corte máximo . [6]
