Coincidencia de cardinalidad máxima

En teoría de grafos , un emparejamiento de cardinalidad máxima es un tipo especial de subgrafo útil en muchos contextos computacionales. Dado un grafo $G$ , un emparejamiento es un subgrafo donde no hay dos aristas que compartan un vértice. La cardinalidad del emparejamiento es el número de aristas en el subgrafo, y la cardinalidad máxima es el mayor número de aristas que puede contener un emparejamiento. Un emparejamiento para un grafo dado es un emparejamiento de cardinalidad máxima si su cardinalidad es esta cardinalidad máxima. Si consideramos que cada arista "cubre" los vértices que conecta exactamente una vez, entonces un emparejamiento maximal es también la mayor cobertura no superpuesta del grafo. Si todos los vértices están cubiertos, lo llamamos un emparejamiento perfecto . Para grafos finitos, siempre existe un emparejamiento de cardinalidad máxima, pero no suele ser único. La cardinalidad del emparejamiento nunca es mayor que la mitad del número de vértices ni mayor que el número de aristas.

Un caso especial importante del problema de emparejamiento de cardinalidad máxima se da cuando $G$ es un grafo bipartito que representa una relación binaria , cuyos vértices $V$ se dividen entre vértices izquierdos en $X$ y vértices derechos en $Y$ , y las aristas en $E$ siempre conectan un vértice izquierdo con un vértice derecho. En este caso, el problema se puede resolver de manera eficiente con algoritmos más sencillos que en el caso general.

El cálculo de un emparejamiento máximo para un grafo dado es una tarea fundamental en la teoría computacional de grafos . ^{[ 1 ]} Existen teoremas de caracterización no constructivos para el tamaño de un emparejamiento máximo. Este artículo trata sobre el cálculo de emparejamientos máximos.

Algoritmos para grafos bipartitos

Algoritmo basado en flujo

La forma más sencilla de calcular un emparejamiento de cardinalidad máxima es seguir el algoritmo de Ford-Fulkerson . Este algoritmo resuelve el problema más general de calcular el flujo máximo . Un grafo bipartito $(X + Y, E)$ se puede convertir en una red de flujo de la siguiente manera.

Agrega un vértice de origen $s$ ; agrega una arista desde $s$ a cada vértice en $X.$
Agregue un vértice sumidero $t$ ; agregue una arista desde cada vértice en $Y$ a $t$ .
Asigne una capacidad de 1 a cada arista.

Dado que cada arista de la red tiene capacidad entera, existe un flujo máximo donde todos los flujos son enteros; estos enteros deben ser 0 o 1, ya que todas las capacidades son 1. Cada flujo entero define un emparejamiento en el que una arista pertenece al emparejamiento si y solo si su flujo es 1. Es un emparejamiento porque:

El flujo entrante a cada vértice en $X$ es como máximo 1, por lo que el flujo saliente también es como máximo 1, por lo que hay como máximo una arista adyacente a cada vértice en $X.$
El flujo saliente de cada vértice en $Y$ es como máximo 1, por lo que el flujo entrante también es como máximo 1, por lo que hay como máximo una arista adyacente a cada vértice en $Y.$

El algoritmo de Ford-Fulkerson procede encontrando repetidamente un camino de aumento desde algún $x \in X$ hasta algún $y \in Y$ y actualizando el emparejamiento $M$ tomando la diferencia simétrica de ese camino con $M$ (suponiendo que tal camino existe). Como cada camino se puede encontrar en tiempo $O (E) , el tiempo de ejecución es$ $O (VE)$ , y el emparejamiento máximo consiste en las aristas de $E$ que llevan flujo de $X$ a $Y.$

Algoritmos avanzados

Una mejora a este algoritmo la proporciona el algoritmo de Hopcroft-Karp , más elaborado , que busca múltiples caminos de aumento simultáneamente. Este algoritmo se ejecuta en $O({\sqrt {V}}E)$ tiempo.

El algoritmo de Chandran y Hochbaum ^{[ 2 ]} para grafos bipartitos se ejecuta en un tiempo que depende del tamaño del emparejamiento máximo $k$ , que para $| X | < | Y |$ es

O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).

Utilizando operaciones booleanas en palabras de tamaño $\lambda$ La complejidad se mejora aún más a ^{[ 2 ]}

O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).

Existen algoritmos más eficientes para tipos especiales de grafos bipartitos:

Para grafos bipartitos dispersos , el problema de emparejamiento máximo se puede resolver en ${\tilde {O}}(E^{10/7})$ con el algoritmo de Madry basado en flujos eléctricos. ^{[ 3 ]}
Para grafos bipartitos planares , el problema se puede resolver en tiempo $O (n log 3 n)$ donde $n$ es el número de vértices, reduciendo el problema a flujo máximo con múltiples fuentes y sumideros. ^{[ 4 ]}

Algoritmos para grafos arbitrarios

El algoritmo Blossom encuentra una correspondencia de cardinalidad máxima en grafos generales (no necesariamente bipartitos). Se ejecuta en tiempo $O(|V|^{2}\cdot |E|)$ Un mejor rendimiento de $O (\sqrt V E)$ para grafos generales, igualando el rendimiento del algoritmo de Hopcroft-Karp en grafos bipartitos, se puede lograr con el algoritmo mucho más complejo de Micali y Vazirani. ^{[ 5 ]} El mismo límite fue alcanzado por un algoritmo de Blum ^{[ 6 ]} y un algoritmo de Gabow y Tarjan . ^{[ 7 ]}

Un enfoque alternativo utiliza la aleatorización y se basa en el algoritmo de multiplicación rápida de matrices . Esto proporciona un algoritmo aleatorio para grafos generales con complejidad $O(V^{2.372})$ . ^{[ 8 ]} Esto es mejor en teoría para grafos suficientemente densos , pero en la práctica el algoritmo es más lento. ^{[ 2 ]}

^{Duan y Pettie [ 9 ]} revisan otros algoritmos para esta tarea (véase la Tabla I). En cuanto a los algoritmos de aproximación , también señalan que el algoritmo Blossom y los algoritmos de Micali y Vazirani pueden considerarse algoritmos de aproximación que se ejecutan en tiempo lineal para cualquier límite de error fijo.

Aplicaciones y generalizaciones

Al encontrar un emparejamiento de cardinalidad máxima, es posible decidir si existe un emparejamiento perfecto .
El problema de encontrar un emparejamiento con peso máximo en un grafo ponderado se denomina problema de emparejamiento de peso máximo , y su restricción a grafos bipartitos se denomina problema de asignación . Si cada vértice puede emparejarse con varios vértices a la vez, entonces se trata de un problema de asignación generalizado .
Una coincidencia de prioridad es una coincidencia de cardinalidad máxima particular en la que los vértices priorizados se emparejan primero.
El problema de encontrar un emparejamiento de cardinalidad máxima en hipergrafos es NP-completo incluso para hipergrafos 3-uniformes. ^{[ 10 ]}

Referencias

↑ West, Douglas Brent (1999), Introducción a la teoría de grafos (2.ª ed.), Prentice Hall, Capítulo 3, ISBN 0-13-014400-2
1 2 3 Chandran, Bala G.; Hochbaum, Dorit S. (2011), Mejoras prácticas y teóricas para el emparejamiento bipartito utilizando el algoritmo de pseudoflujo , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C , los algoritmos teóricamente eficientes enumerados anteriormente tienden a tener un rendimiento deficiente en la práctica.
↑ Madry, A (2013), "Navegando por la ruta central con flujos eléctricos: de flujos a emparejamientos y viceversa", Foundations of Computer Science (FOCS), 54.º Simposio Anual del IEEE de 2013 , pp. 253–262 , arXiv : 1307.2205 , Bibcode : 2013arXiv1307.2205M
↑ Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Flujo máximo de múltiples fuentes y múltiples sumideros en grafos planares dirigidos en tiempo casi lineal", SIAM Journal on Computing , 46 (4): 1280– 1303, arXiv : 1105.2228 , doi : 10.1137/15M1042929 , MR 3681377 , S2CID 207071917
^ Micali, S .; Vazirani, VV (1980), "Un $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ Algoritmo para encontrar el emparejamiento máximo en grafos generales", Actas del 21.º Simposio IEEE sobre Fundamentos de la Informática , págs. 17-27 , doi : 10.1109/SFCS.1980.12 , S2CID 27467816 .
↑ Blum, Norbert (1990), "Un nuevo enfoque para el emparejamiento máximo en grafos generales" (PDF) , en Paterson, Mike (ed.), Autómatas, lenguajes y programación, 17.º Coloquio Internacional, ICALP90, Universidad de Warwick, Inglaterra, Reino Unido, 16-20 de julio de 1990, Actas , Lecture Notes in Computer Science, vol. 443, Springer, pp. 586-597 , doi : 10.1007/BFb0032060
↑ Gabow, Harold N ; Tarjan, Robert E (1991-10-01). "Algoritmos de escalado más rápidos para problemas generales de emparejamiento de grafos" (PDF) . Journal of the ACM . 38 (4): 815– 853. doi : 10.1145/115234.115366 . S2CID 18350108 .
↑ Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF) , Proc. 45th IEEE Symp. Foundations of Computer Science , pp . 248–255
↑ Duan, Ran; Pettie, Seth (2014-01-01). "Aproximación en tiempo lineal para la coincidencia de peso máximo" (PDF) . Journal of the ACM . 61 : 1–23 . doi : 10.1145/2529989 . S2CID 207208641 .
↑ Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", en Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), Complejidad de los cálculos informáticos: Actas de un simposio sobre la complejidad de los cálculos informáticos, celebrado del 20 al 22 de marzo de 1972 en el Centro de Investigación IBM Thomas J. Watson, Yorktown Heights, Nueva York, y patrocinado por la Oficina de Investigación Naval, el Programa de Matemáticas, IBM World Trade Corporation y el Departamento de Ciencias Matemáticas de Investigación de IBM , The IBM Research Symposia Series, Boston, MA: Springer US, pp. 85–103 , doi : 10.1007/978-1-4684-2001-2_9 , ISBN 978-1-4684-2001-2

[Wes01-1] West, Douglas Brent (1999), Introducción a la teoría de grafos (2.ª ed.), Prentice Hall, Capítulo 3, ISBN 0-13-014400-2

[Chandran-2] 1 2 3 Chandran, Bala G.; Hochbaum, Dorit S. (2011), Mejoras prácticas y teóricas para el emparejamiento bipartito utilizando el algoritmo de pseudoflujo , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C , los algoritmos teóricamente eficientes enumerados anteriormente tienden a tener un rendimiento deficiente en la práctica.

[3] Madry, A (2013), "Navegando por la ruta central con flujos eléctricos: de flujos a emparejamientos y viceversa", Foundations of Computer Science (FOCS), 54.º Simposio Anual del IEEE de 2013 , pp. 253–262 , arXiv : 1307.2205 , Bibcode : 2013arXiv1307.2205M

[4] Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Flujo máximo de múltiples fuentes y múltiples sumideros en grafos planares dirigidos en tiempo casi lineal", SIAM Journal on Computing , 46 (4): 1280– 1303, arXiv : 1105.2228 , doi : 10.1137/15M1042929 , MR 3681377 , S2CID 207071917

[5] Micali, S .; Vazirani, VV (1980), "Un $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ Algoritmo para encontrar el emparejamiento máximo en grafos generales", Actas del 21.º Simposio IEEE sobre Fundamentos de la Informática , págs. 17-27 , doi : 10.1109/SFCS.1980.12 , S2CID 27467816 .

[6] Blum, Norbert (1990), "Un nuevo enfoque para el emparejamiento máximo en grafos generales" (PDF) , en Paterson, Mike (ed.), Autómatas, lenguajes y programación, 17.º Coloquio Internacional, ICALP90, Universidad de Warwick, Inglaterra, Reino Unido, 16-20 de julio de 1990, Actas , Lecture Notes in Computer Science, vol. 443, Springer, pp. 586-597 , doi : 10.1007/BFb0032060

[7] Gabow, Harold N ; Tarjan, Robert E (1991-10-01). "Algoritmos de escalado más rápidos para problemas generales de emparejamiento de grafos" (PDF) . Journal of the ACM . 38 (4): 815– 853. doi : 10.1145/115234.115366 . S2CID 18350108 .

[Mucha-8] Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF) , Proc. 45th IEEE Symp. Foundations of Computer Science , pp . 248–255

[9] Duan, Ran; Pettie, Seth (2014-01-01). "Aproximación en tiempo lineal para la coincidencia de peso máximo" (PDF) . Journal of the ACM . 61 : 1–23 . doi : 10.1145/2529989 . S2CID 207208641 .

[10] Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", en Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), Complejidad de los cálculos informáticos: Actas de un simposio sobre la complejidad de los cálculos informáticos, celebrado del 20 al 22 de marzo de 1972 en el Centro de Investigación IBM Thomas J. Watson, Yorktown Heights, Nueva York, y patrocinado por la Oficina de Investigación Naval, el Programa de Matemáticas, IBM World Trade Corporation y el Departamento de Ciencias Matemáticas de Investigación de IBM , The IBM Research Symposia Series, Boston, MA: Springer US, pp. 85–103 , doi : 10.1007/978-1-4684-2001-2_9 , ISBN 978-1-4684-2001-2

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

Duan y Pettie [ 9 ]

[ 10 ]