Coincidencia tridimensional

En matemáticas , especialmente en teoría de grafos , un emparejamiento tridimensional (en inglés: emparejamiento tridimensional ) es una generalización del acoplamiento (también llamado emparejamiento en 2D ) a una situación ternaria que, técnicamente, es la de hipergráficos llamados 3-uniformes . Encontrar una coincidencia tridimensional de tamaño máximo es un problema NP-difícil bien conocido en la teoría de la complejidad computacional .

Definición

Sea y tres conjuntos finitos disjuntos, y sea un subconjunto de . Entonces, se compone de trillizos , con y . Una parte es un emparejamiento de 3 dimensiones si la propiedad siguiente es cierto: para cualquier par de triples y distinta de , tenemos , y . En otras palabras, si dos triples difieren en un componente, deben diferir en todos sus componentes. $X, Y$ $Z$ $T$ ${\ Displaystyle X \ times Y \ times Z}$ $T$ $(X y Z)$ ${\ Displaystyle x \ en X, y \ en Y}$ $z \ in Z$ ${\ Displaystyle M \ subseteq T}$ ${\ Displaystyle (x_ {1}, y_ {1}, z_ {1})}$ ${\ Displaystyle (x_ {2}, y_ {2}, z_ {2})}$ $METRO$ ${\ Displaystyle x_ {1} \ neq x_ {2}}$ ${\ Displaystyle y_ {1} \ neq y_ {2}}$ ${\ Displaystyle z_ {1} \ neq z_ {2}}$

Ejemplo

La figura de la derecha ilustra un emparejamiento tridimensional. El conjunto está representado por puntos rojos , puntos azules y puntos verdes. La figura (a) muestra el conjunto dado; cada triplete se dibuja en un área gris. La figura (b) muestra un emparejamiento tridimensional que consta de dos elementos, y la figura (c) muestra un emparejamiento que consta de tres elementos. $X$ $Y$ $Z$ $T$

El emparejamiento de la figura (c) es de tamaño máximo : no hay un tamaño mayor, mientras que el emparejamiento de la figura (b), aunque no es de tamaño máximo, es máximo : no se puede agrandar en un emparejamiento más grande.

Comparación con el acoplamiento

Un acoplamiento , o emparejamiento bidimensional , se puede definir de una manera completamente análoga: let y dos conjuntos finitos disjuntos, y una parte de . Una parte es un acoplamiento si, para cualquier par de pares distintos y de , tenemos y . $X$ $Y$ $T$ $X \ veces Y$ ${\ Displaystyle M \ subseteq T}$ $(x_ {1}, y_ {1})$ $(x_ {2}, y_ {2})$ $METRO$ ${\ Displaystyle x_ {1} \ neq x_ {2}}$ ${\ Displaystyle y_ {1} \ neq y_ {2}}$

En el caso de la coincidencia bidimensional, el conjunto se puede interpretar como el conjunto de aristas de un gráfico bipartito , cada arista de conectar un vértice de a un vértice de . Un emparejamiento bidimensional es entonces un emparejamiento en el gráfico , es decir, un conjunto de bordes no adyacentes de dos por dos. $T$ ${\ Displaystyle G = (X \ cup Y, T)}$ $T$ $X$ $Y$ $GRAMO$

Asimismo, un emparejamiento tridimensional se puede interpretar como una generalización de acoplamientos a hipergráficos : los conjuntos y contienen los vértices, cada triple de es un hiperfilo, y el conjunto está formado por dos a dos hiperfrenos. disjuntos, es decir sin un vértice común. $X, Y$ $Z$ $T$ $METRO$

Comparación con el empaquetado

Un emparejamiento tridimensional es un caso especial de empaquetado de conjuntos : podemos interpretar cada triplete de como un subconjunto de ; un emparejamiento tridimensional consiste entonces en subconjuntos disjuntos de dos por dos. $(X y Z)$ $T$ ${\ Displaystyle \ {x, y, z \}}$ ${\ Displaystyle X \ cup Y \ cup Z}$ $METRO$

Problema de decisión

En la teoría de la complejidad computacional , el problema de emparejamiento tridimensional es el nombre del siguiente problema de decisión : dado un conjunto y un entero k ; decidir si hay un emparejamiento tridimensional con al menos k elementos. $T$ ${\ Displaystyle M \ subseteq T}$

Se sabe que este problema de decisión es NP-completo : es uno de los famosos 21 problemas NP-completos de Karp . Sin embargo, existen algoritmos polinomiales para este problema en casos especiales, como el de los hipergráficos "densos".

El problema es NP-completo incluso en el caso especial . En este caso, un emparejamiento tridimensional no es solo un paquete de conjuntos, sino también un problema de cobertura exacta : el conjunto cubre cada elemento desde y una vez exactamente. ${\ Displaystyle k = | X | = | Y | = | Z |}$ $METRO$ $X, Y$ $Z$

Problema de optimizacion

Una coincidencia máxima tridimensional es una coincidencia de tamaño máximo tridimensional. En teoría de la complejidad, también es el nombre del siguiente problema de optimización combinatoria : dado , encuentre una coincidencia tridimensional de tamaño máximo. $T$ $METRO$

Como el problema de decisión es NP-completo , el problema de optimización es NP-difícil y, por lo tanto, probablemente no exista un algoritmo polinomial para encontrar una coincidencia tridimensional máxima, mientras que existen algoritmos eficientes en tiempo polinomial para la dimensión 2, como Hopcroft y Algoritmo Karp .

Algoritmos de aproximación

El problema es APX completo ; en otras palabras, es difícil aproximarlo con un factor constante. Por otro lado, para cualquier constante , existe un algoritmo de aproximación de tiempo polinomial factorial . $\ varepsilon> 0$ ${\ Displaystyle 3/2 + \ varepsilon}$

Existe un algoritmo polinomial muy simple para calcular una coincidencia tridimensional con un factor de aproximación 3: basta con encontrar cualquier coincidencia tridimensional que no se pueda aumentar (una coincidencia máxima). No es necesariamente el máximo, pero así como un acoplamiento máximo es un acoplamiento máximo a un factor de 1/2, un emparejamiento tridimensional máximo es un máximo a un factor de 1/3.

Notas y referencias

Karp 1972 .
Karpinski, Rucinski y Szymanska 2009
Keevash, Knox y Mycroft 2013
Garey y Johnson 1979 , Sección 3.1 y Problema SP1 en el Apéndice A.3.1.
Korte y Vygen , 2006 , sección 15.5.
Papadimitriou y Steiglitz 1998 , Sección 15.7.
Crescenzi et al. 2000 .
Ausiello et al. 2003 , SP1 Problema del Apéndice B .
Kann 1991 .

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Coincidencia tridimensional " ( consulte la lista de autores ) .

Ver también

Bibliografía

Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi , Viggo Kann , Alberto Marchetti-Spaccamela y Marco Protasi , Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación , Springer ,2003.
Pierluigi Crescenzi , Viggo Kann , Magnús Halldórsson , Marek Karpinski y Gerhard Woeginger , "Máxima coincidencia tridimensional" , en A Compendium of NP Optimization Problems ,2000( leer en línea ).
(en) Michael Garey y David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
Viggo Kann , “La máxima coincidencia tridimensional limitada es MAX SNP-complete ”, Information Processing Letters , vol. 37, n o 1,1991, p. 27–35 ( DOI 10.1016 / 0020-0190 (91) 90246-E ).
(en) Richard M. Karp , "Reducibilidad entre problemas combinatorios" , en Raymond E. Miller y James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , leer en línea ) , p. 85-103
Marek Karpinski , Andrzej Rucinski y Edyta Szymanska , " The Complexity of Perfect Matching Problems on Dense Hypergraphs ", Actas de ISAAC '09 del 20º Simposio Internacional de Algoritmos ,2009, p. 626-636 ( DOI 10.1007 / 978-3-642-10631-6_64 ).
Peter Keevash , Fiachra Knox y Richard Mycroft , " Emparejamientos perfectos de tiempo polinomial en hipergráficos densos ", Actas de STOC '13 del cuadragésimo quinto simposio anual de ACM ,2013, p. 311-320 ( DOI 10.1145 / 2488608.2488647 ).
Bernhard Korte y Jens Vygen , Optimización combinatoria: teoría y algoritmos , Springer ,2006, 3 e ed..
Christos H. Papadimitriou y Kenneth Steiglitz , Optimización combinatoria: algoritmos y complejidad , Publicaciones de Dover ,1998.