En la disciplina matemática de la teoría de grafos , un emparejamiento tridimensional es una generalización del emparejamiento bipartito (también conocido como emparejamiento bidimensional) a hipergrafos tridimensionales , que consisten en hiperaristas cada una de las cuales contiene 3 vértices (en lugar de aristas que contienen 2 vértices en un grafo habitual).
La correspondencia tridimensional, a menudo abreviada como 3DM , es también el nombre de un conocido problema computacional: encontrar la correspondencia tridimensional más grande en un hipergrafo dado. 3DM es uno de los primeros problemas que se demostró que era NP-hard .
Sean X , Y y Z conjuntos finitos, y sea T un subconjunto de X × Y × Z. Es decir, T consiste en ternas ( x , y , z ) tales que x ∈ X , y ∈ Y y z ∈ Z . Ahora M ⊆ T es una correspondencia tridimensional si se cumple lo siguiente: para dos ternas distintas cualesquiera ( x 1 , y 1 , z 1 ) ∈ M y ( x 2 , y 2 , z 2 ) ∈ M , tenemos x 1 ≠ x 2 , y 1 ≠ y 2 y z 1 ≠ z 2 .
La figura de la derecha ilustra emparejamientos tridimensionales. El conjunto X está marcado con puntos rojos, Y con puntos azules y Z con puntos verdes. La figura (a) muestra el conjunto T (áreas grises). La figura (b) muestra un emparejamiento tridimensional M con | M | = 2, y la figura (c) muestra un emparejamiento tridimensional M con | M | = 3.
La coincidencia M ilustrada en la Figura (c) es una coincidencia tridimensional máxima , es decir, maximiza | M |. Las coincidencias ilustradas en las Figuras (b)–(c) son coincidencias tridimensionales máximas , es decir, no se pueden extender agregando más elementos de T.
Aquí hay un ejemplo de visualización interactiva en javascript
Un emparejamiento bidimensional se puede definir de una manera completamente análoga. Sean X e Y conjuntos finitos, y sea T un subconjunto de X × Y . Ahora M ⊆ T es un emparejamiento bidimensional si se cumple lo siguiente: para dos pares distintos cualesquiera ( x 1 , y 1 ) ∈ M y ( x 2 , y 2 ) ∈ M , tenemos x 1 ≠ x 2 e y 1 ≠ y 2 .
En el caso de un emparejamiento bidimensional, el conjunto T puede interpretarse como el conjunto de aristas en un grafo bipartito G = ( X , Y , T ); cada arista en T conecta un vértice en X a un vértice en Y . Un emparejamiento bidimensional es entonces un emparejamiento en el grafo G , es decir, un conjunto de aristas no adyacentes por pares.
Por lo tanto, los emparejamientos tridimensionales se pueden interpretar como una generalización de los emparejamientos a hipergrafos: los conjuntos X , Y y Z contienen los vértices, cada elemento de T es una hiperarista y el conjunto M consta de aristas no adyacentes por pares (aristas que no tienen un vértice común). En el caso del emparejamiento bidimensional, tenemos Y = Z.
Un emparejamiento tridimensional es un caso especial de empaquetamiento de conjuntos : podemos interpretar cada elemento ( x , y , z ) de T como un subconjunto { x , y , z } de X ∪ Y ∪ Z ; entonces, un emparejamiento tridimensional M consiste en subconjuntos disjuntos por pares.
En la teoría de la complejidad computacional, el emparejamiento tridimensional (3DM) es el nombre del siguiente problema de decisión : dado un conjunto T y un entero k , decidir si existe un emparejamiento tridimensional M ⊆ T con | M | ≥ k .
Se sabe que este problema de decisión es NP-completo ; es uno de los 21 problemas NP-completos de Karp . [1] Es NP-completo incluso en el caso especial de que k = | X | = | Y | = | Z | y cuando cada elemento está contenido en como máximo 3 conjuntos, es decir, cuando queremos una correspondencia perfecta en un hipergrafo 3-regular. [1] [2] [3] En este caso, una correspondencia tridimensional no es solo un empaquetamiento de conjuntos, sino también una cobertura exacta : el conjunto M cubre cada elemento de X , Y y Z exactamente una vez. [4] La prueba es por reducción de 3SAT . Dada una instancia de 3SAT, construimos una instancia de 3DM de la siguiente manera: [2] [5]
Existen algoritmos de tiempo polinomial para resolver 3DM en hipergrafos densos. [6] [7]
Una correspondencia tridimensional máxima es la correspondencia tridimensional más grande. En la teoría de la complejidad computacional, este es también el nombre del siguiente problema de optimización : dado un conjunto T , encuentre una correspondencia tridimensional M ⊆ T que maximice |M| .
Dado que el problema de decisión descrito anteriormente es NP-completo, este problema de optimización es NP-duro y, por lo tanto, parece que no existe un algoritmo de tiempo polinomial para encontrar una correspondencia tridimensional máxima. Sin embargo, existen algoritmos de tiempo polinomial eficientes para encontrar una correspondencia bipartita máxima (correspondencia bidimensional máxima), por ejemplo, el algoritmo Hopcroft–Karp .
Hay un algoritmo de aproximación de tiempo polinomial muy simple para la correspondencia tridimensional: encontrar cualquier correspondencia tridimensional máxima. [8] Así como una correspondencia máxima está dentro del factor 2 de una correspondencia máxima, [9] una correspondencia tridimensional máxima está dentro del factor 3 de una correspondencia tridimensional máxima.
Para cualquier constante ε > 0 existe un algoritmo de aproximación en tiempo polinomial (4/3 + ε) para correspondencia tridimensional. [10]
Sin embargo, lograr mejores factores de aproximación es probablemente difícil: el problema es APX-completo , es decir, es difícil de aproximar dentro de alguna constante. [11] [12] [8]
Es NP-hard lograr un factor de aproximación de 95/94 para una correspondencia máxima en 3-d, y un factor de aproximación de 48/47 para una correspondencia máxima en 4-d. La dificultad se mantiene incluso cuando se restringe a instancias con exactamente dos ocurrencias de cada elemento. [13]
Existen varios algoritmos para la correspondencia 3D en el modelo de computación masivamente paralela . [14]