Problema de la división de un conjunto

En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S₁ y S₂ tales que ninguno de los elementos de F esté completamente en S₁ o S₂? Este problema es NP-completo.^[1]

Visto como un problema de optimización, se llama el problema de división del máximo conjunto (en inglés Max Set Splitting) y consiste en encontrar la partición que maximiza el número de elementos divididos de F. Este es un problema APX^[2] (y NP-hard). El problema sigue siendo NP-hard incluso si todos los subconjuntos de F contienen el mismo número de elementos, todos ellos mayores que 1.^[3]

Como problema de decisión, el Max Set Splitting, también llamado "Set Splitting" queda como sigue: dado un número entero k, ¿existe una partición de S que divida al menos k subconjuntos de F? Si k toma el valor de un parámetro dado, luego el "Set Splitting" posee complejidad parametrizada, es decir existe un algoritmo polinomial para cualquier valor de k.^[3]

Referencias

1. ↑ Garey, M.R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. 
2. ↑ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
3. ↑ ^{a b} "An FPT Algorithm for Set Splitting"