Coincidencia de cardinalidad máxima

La correspondencia de cardinalidad máxima es un problema fundamental en la teoría de grafos . ^[1] Se nos da un grafo $G$ y el objetivo es encontrar una correspondencia que contenga la mayor cantidad posible de aristas; es decir, un subconjunto de cardinalidad máxima de las aristas de modo que cada vértice sea adyacente a, como máximo, una arista del subconjunto. Como cada arista cubrirá exactamente dos vértices, este problema es equivalente a la tarea de encontrar una correspondencia que cubra la mayor cantidad posible de vértices.

Un caso especial importante del problema de correspondencia de cardinalidad máxima es cuando $G$ es un grafo bipartito , cuyos vértices $V$ están divididos 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 simples que en el caso general.

Algoritmos para grafos bipartitos

Algoritmo basado en flujo

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

Añade un vértice de origen $s$ ; agrega una arista desde $s$ a cada vértice en $X.$
Añade un vértice sumidero $t$ ; agrega una arista desde cada vértice en $Y$ a $t$ .
Asigna una capacidad de 1 a cada borde.

Como cada borde de la red tiene capacidad integral, existe un flujo máximo donde todos los flujos son números enteros; estos números enteros deben ser 0 o 1 ya que todas las capacidades son 1. Cada flujo integral define una coincidencia en la que un borde está en la coincidencia si y solo si su flujo es 1. Es una coincidencia porque:

El flujo entrante en 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 como máximo hay un borde 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 como máximo hay un borde adyacente a cada vértice en $Y.$

El algoritmo de Ford–Fulkerson procede encontrando repetidamente una ruta de aumento desde algún $x \in X$ hasta algún $y \in Y$ y actualizando la $M$ coincidente tomando la diferencia simétrica de esa ruta con $M$ (suponiendo que dicha ruta existe). Como cada ruta se puede encontrar en tiempo $O (E)$ , el tiempo de ejecución es $O (VE)$ , y la coincidencia máxima consiste en los bordes de $E$ que llevan flujo desde $X$ a $Y$ .

Algoritmos avanzados

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

El algoritmo de Chandran y Hochbaum ^[2] para gráficos bipartitos se ejecuta en un tiempo que depende del tamaño del $k$ de coincidencia máxima , que para $| X | < | Y |$ es

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

Al utilizar operaciones booleanas en palabras de tamaño grande, la complejidad se mejora aún más a ^[2] ${\estilo de visualización \lambda}$

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 gráficos bipartitos:

Para gráficos bipartitos dispersos , el problema de coincidencia máxima se puede resolver con el algoritmo de Madry basado en flujos eléctricos. ^[3] ${\tilde {O}}(E^{10/7})$
Para gráficos 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 al flujo máximo con múltiples fuentes y sumideros. ^[4]

Algoritmos para gráficos arbitrarios

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

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

^{Duan y Pettie [9]} revisan otros algoritmos para la tarea (ver Tabla I). En términos de 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 una coincidencia de cardinalidad máxima, es posible decidir si existe una coincidencia perfecta .
El problema de encontrar una correspondencia con el peso máximo en un grafo ponderado se denomina problema de correspondencia de peso máximo y su restricción a grafos bipartitos se denomina problema de asignación . Si cada vértice se puede corresponder 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 coinciden primero.
El problema de encontrar una correspondencia 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
^ abc Chandran, Bala G.; Hochbaum, Dorit S. (2011), Mejoras prácticas y teóricas para la correspondencia bipartita utilizando el algoritmo pseudoflow , 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 los flujos a las coincidencias y viceversa", Fundamentos de la informática (FOCS), 2013 IEEE 54th Annual Symposium on , págs. 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 gráficos planos 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 algoritmo para encontrar la máxima coincidencia en gráficos generales", Proc. 21st IEEE Symp. Foundations of Computer Science , págs. 17–27, doi :10.1109/SFCS.1980.12, S2CID 27467816 $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ .
^ Blum, Norbert (1990), "Un nuevo enfoque para la máxima coincidencia en grafos generales" (PDF) , en Paterson, Mike (ed.), Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, Inglaterra, Reino Unido, 16-20 de julio de 1990, Actas , Lecture Notes in Computer Science, vol. 443, Springer, págs. 586-597, doi :10.1007/BFb0032060
^ Gabow, Harold N ; Tarjan, Robert E (1991-10-01). "Algoritmos de escalamiento más rápidos para problemas generales de correspondencia de grafos" (PDF) . Revista de la ACM . 38 (4): 815–853. doi :10.1145/115234.115366. S2CID 18350108.
^ Mucha, M.; Sankowski, P. (2004), "Máximas coincidencias mediante eliminación gaussiana" (PDF) , Actas del 45.º Simposio IEEE sobre fundamentos de la informática , págs. 248-255
^ Duan, Ran; Pettie, Seth (1 de enero de 2014). "Aproximación de tiempo lineal para la correspondencia de peso máximo" (PDF) . Revista de la ACM . 61 : 1–23. doi :10.1145/2529989. S2CID 207208641.
^ Karp, Richard M. (1972), Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), "Reducibility among Combinatorial Problems", Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, celebrado del 20 al 22 de marzo de 1972 en el IBM Thomas J. Watson Research Center, Yorktown Heights, Nueva York, y patrocinado por la Office of Naval Research, Mathematics Program, IBM World Trade Corporation y el IBM Research Mathematical Sciences Department , The IBM Research Symposia Series, Boston, MA: Springer US, págs. 85-103, doi :10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2