Problema de la división de un conjunto

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? 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 polinómico para cualquier valor de k.[3]

Referencias[editar]

  1. Garey, M.R.; Johnson, D.S. (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"