Acoplamento tridimensional
Na disciplina matemática de teoria dos grafos, um acoplamento tridimensional é uma generalização do acoplamento bipartido (mais conhecido como acoplamento bidimensional) para hipergrafos triuniformes. Encontrar o maior acoplamento tridimensional é um problema NP-difícil bem conhecido na Teoria da Complexidade computacional.
Definição editar
Sejam X, Y, e Z, conjuntos disjuntos finitos, e seja T um subconjunto de X × Y × Z. Isto é, T consiste de triplas (x, y, z) de forma que x ∈ X, y ∈ Y, and z ∈ Z. Dessa forma M ⊆ T é uma acoplamento tridimensional se obedece às seguintes regras: para quaisquer duas triplas distintas (x1, y1, z1) ∈ M e (x2, y2, z2) ∈ M, temos que x1 ≠x2, y1 ≠y2, and z1 ≠z2.
Exemplo editar
A figura à direita ilustra combinações tridimensionais. O conjunto X é marcado com pontos vermelhos, Y é marcado com pontos azuis, e Z é marcado com pontos verdes. A Figura (a) mostra o conjunto T (áreas cinzas). A Figura (b) mostra um acoplamento tridimensional M com |M| = 2, e a Figura (c) mostra uma combinação tridimensional M com |M| = 3.
O acoplamento M ilustrado na Figura (c) é um acoplamento tridimensional máximo, isto é, ele maximiza |M|. O acoplamento ilustrado nas figuras (b)–(c) são acoplamentos tridimensionais maximais, isto é, eles não podem ser estendidos adicionando mais elementos a partir de T.
Comparação com acoplamento bipartido editar
Um acoplamento bidimensional pode ser definido de uma forma completamente análoga. Sejam X e Y, conjuntos disjuntos finitos, e seja T um subconjunto de X × Y. Sendo assim M ⊆ T é um acoplamento bidimensional se obedece as seguintes regras: para quaisquer dois pares distintos (x1, y1) ∈ M e (x2, y2) ∈ M, temos x1 ≠x2 e y1 ≠y2.
No caso de um acoplamento bidimensional, o conjunto T pode ser interpretado como um conjunto de arestas em um grafo bipartido G = (X, Y, T); cada aresta em T conecta um vértice em X para um vértice em Y. Um acoplamento bidimensional é então um acoplamento no grafo G, que é um conjunto de arestas emparelhadas não-adjacentes.
Consequentemente, acoplamentos tridimensionais podem ser interpretados como uma generalização de combinações para hipergrafos: os conjuntos X, Y, e Z vértices, cada elemento de T é uma hiper-aresta, e o conjunto M consiste de arestas emparelhadas não-adjacentes (arestas que não possuem um vértice comum).
Comparação com empacotamento de conjunto (set packing) editar
Um acoplamento tridimensional é um caso especial de empacotamento de conjunto: podemos interpretar cada elemento (x, y, z) de T como um subconjunto {x, y, z} de X ∪ Y ∪ Z; então um acoplamento tridimensional M consiste de subconjuntos disjuntos emparelhados.
Problema de decisão editar
Em Teoria da Complexidade, acoplamento tridimensional é também o nome do seguinte problema de decisão: dado um conjunto T e um inteiro k, decida se existe um acoplamento tridimensional M ⊆ T com |M| ≥ k.
Esse problema de decisão é conhecido por ser NP-completo; é um dos 21 problemas NP-completos de Karp.[1] Não obstante, existem algoritmos de tempo polinomiais para esse problema, para hipergrafos densos.[2][3]
O problema é NP-completo até no caso especial em que k = |X| = |Y| = |Z|.[1][4][5] Nesse caso, um acoplamento tridimensional (dominante) não é só um empacotamento de conjunto, mas também um problema de cobertura exata: o conjunto M cobre cada elemento de X, Y, e Z exatamente uma vez.[6]
Problema de otimização editar
Um acoplamento tridimensional máximo é o maior acoplamento tridimensional possível. Na teoria da Complexidade, é também o nome do seguinte problema de otimização: dado um conjunto T, encontre um acoplamento tridimensional M ⊆ T que maximize |M|.
Sendo o problema de decisão descrito acima NP-completo, esse problema de otimização é NP-difícil, e consequentemente parece que não há algoritmo de tempo polinomial para encontrar um acoplamento tridimensional máximo. Contudo, há algoritmos de tempo polinomial eficientes para encontrar um acoplamento bipartido máximo (acoplamento bidimensional máximo), por exemplo, o algoritmo de Hopcroft–Karp.
Algoritmos de aproximação editar
O problema é APX-completo, ou seja, é difícil criar um Algoritmo de aproximação que difira do resultado exato apenas por uma constante.[7][8][9] No lado positivo, para qualquer constante ε > 0 há um algoritmo de aproximação de tempo polinomial (3/2 + ε) para acoplamento tridimensional.[7][8]
Há um algoritmo de aproximação tridimensional de tempo polinomial muito simples para o acoplamento tridimensional: encontrar qualquer acoplamento tridimensional máximo[9]. Assim como um acoplamento máximo está na ordem de um polinômio de grau 2 em relação a um acoplamento máximo,[10] um acoplamento tridimensional máximo está na ordem de um polinômio de grau 3 em relação a um acoplamento tridimensional máximo.
Referências
- ↑ a b Karp (1972).
- ↑ Karpinski, Rucinski & Szymanska (2009)
- ↑ Keevash, Knox & Mycroft (2013)
- ↑ Garey & Johnson (1979), Section 3.1 and problem SP1 in Appendix A.3.1.
- ↑ Korte & Vygen (2006), Section 15.5.
- ↑ Papadimitriou & Steiglitz (1998), Section 15.7.
- ↑ a b Crescenzi et al. (2000).
- ↑ a b Ausiello et al. (2003), problem SP1 in Appendix B.
- ↑ a b Kann (1991)
- ↑ Matching (graph theory)#Properties .
Referências editar
- Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer.
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), «Maximum 3-dimensional matching», A Compendium of NP Optimization Problems.
- Kann, Viggo (1991), «Maximum bounded 3-dimensional matching is MAX SNP-complete», Information Processing Letters, 37 (1): 27–35, doi:10.1016/0020-0190(91)90246-E.
- Karp, Richard M. (1972), «Reducibility among combinatorial problems», in: Miller, Raymond E.; Thatcher, James W., Complexity of Computer Computations, Plenum, pp. 85–103.
- Karpinski, Marek; Rucinski, Andrzej; Szymanska, Edyta (2009), «The Complexity of Perfect Matching Problems on Dense Hypergraphs», ISAAC '09 Proceedings of the 20th International Symposium on Algorithms: 626–636, doi:10.1007/978-3-642-10631-6_64.
- Keevash, Peter; Knox, Fiachra; Mycroft, Richard (2013), «Polynomial-Time perfect matchings in dense hypergraphs», STOC '13 Proceedings of the forty-fifth annual ACM symposium: 311–320, doi:10.1145/2488608.2488647.
- Korte, Bernhard; Vygen, Jens (2006), Combinatorial Optimization: Theory and Algorithms 3rd ed. , Springer.
- Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover Publications.
Ligações externas editar
- Lista de problemas NP-completos (em inglês).