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 Sl, S2 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 S1 ou S2. A divisão de conjuntos é um dos problemas NP-completos de Garey e Johnson.[1]
Variantes
[editar | editar código-fonte]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[2] (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. [3] 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
[editar | editar código-fonte]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.[4]
Aproximabilidade
[editar | editar código-fonte]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. [5][4]
Tratabilidade Para Parâmetro Fixo
[editar | editar código-fonte]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.[6]
Referências
[editar | editar código-fonte]- ↑ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5
- ↑ Petrank, Erez (1994). «The Hardness of Approximation: Gap Location». Springer. Computational Complexity
- ↑ Lovász, László (1973). Coverings and Colorings of Hypergraphs. Symposium on Theory of Computing. Association for Computing Machinery
- ↑ a b Guruswami, Venkatesan (2003). «Inapproximability Results for Set Splitting and Satisfiability Problems with no Mixed Clauses». Springer. Algorithmica
- ↑ Håstad, Johan (2001). «Some Optimal Inapproximability Results». Association for Computing Machinery. Journal of the ACM
- ↑ Dehne, Frank; Fellows, Michael; Rosamond, Frances (2003). An FPT Algorithm for Set Splitting. Graph Theoretic Concepts in Computer Science. Springer