Problema da divisão de conjuntos

Em teoria da complexidade computacional, o problema da Divisão de Conjuntos é o seguinte problema de decisão: dada uma família F de subconjuntos de um conjunto finito S, decidir se existe uma partição de S em dois subconjuntos S_l, S₂ de tal modo que todos os elementos de F são divididos por esta partição, i.e., nenhum dos elementos de F está completamente em S₁ ou S₂. A divisão de conjuntos é um dos problemas NP-completos de Garey e Johnson.

Variantes

A versão de otimização deste problema é chamada Divisão de conjuntos máxima e requer que sejam encontradas partições que maximizem o número de elementos divididos de F. Este é um problema APX-completo (e portanto ONP-Difícil). Quando cada elemento de F é restringido a ter cardinalidade exatamente k, a variante de decisão é chamada Ek-Divisão de conjuntos e a versão de otimização Ek-Divisão de conjuntos máxima. Para k ≥ 2 o primeiro continua NP completo e o segundo APX completo. A Divisão de conjuntos poderados é uma variante na qual os subconjuntos em F tem pesos e o objetivo é maximizar o peso total dos subconjuntos divididos.

Conexão a outros problemas

Divisão de conjuntos é um caso especial do Problema da satisfação de restrições sem variáveis negativas. Adicionalmente, Ek-Divisão de conjuntos é equivalente à Coloração de grafos de k-Hipergrafos uniformes. Para k=2, a variante de otimização se reduz ao bastante conhecido Corte máximo.

Aproximabilidade

Para k ≥ 4, Ek-Divisão de conjuntos é resistente a aproximações. Ou seja, a não ser que P=NP, não há Algoritmo de aproximação em tempo polinomial que seja mais útil que uma partição randômica.

Tratabilidade Para Parâmetro Fixo

Uma formulação alternativa da variante de decisão é a seguinte: dado um inteiro k, existe alguma partição de S que divide ao menos k subconjuntos de F? Essa formulação é tratável para parâmetro fixo - para cada k fixo, existe um algoritmo de tempo polinomial para resolver o problema.