Coincidencia de cardinalidad máxima

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

Un caso especial importante del problema de coincidencia de cardinalidad máxima es cuando $G$ es un gráfico bipartito , cuyos vértices $V$ están divididos entre los vértices izquierdos en $X$ y los vértices derechos en $Y$ , y los bordes en $E$ siempre conectan un vértice izquierdo con un vértice derecho. En este caso, el problema se puede resolver eficientemente con algoritmos más simples que en el caso general.

Algoritmos para gráficos bipartitos

Algoritmo basado en flujo

La forma más sencilla de calcular una coincidencia 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 gráfico bipartito $(X + Y, E)$ se puede convertir en una red de flujo de la siguiente manera.

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

Dado que 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 una arista está en la coincidencia si y solo si su flujo es 1. Es una coincidencia porque:

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

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

Algoritmos avanzados

Una mejora de este algoritmo la proporciona el algoritmo Hopcroft-Karp , más elaborado , que busca múltiples rutas 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 de la coincidencia máxima $k$ , que para $| X | < | Y |$ es

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

Usando operaciones booleanas en palabras de tamaño, la complejidad se mejora aún más a ^[2] ${\displaystyle\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 máxima coincidencia se puede resolver con el algoritmo de Madry basado en flujos eléctricos. ^[3] ${\tilde {O}}(E^{10/7})$
Para gráficos bipartitos planos , el problema se puede resolver en el 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 de flor encuentra una coincidencia de cardinalidad máxima en gráficos generales (no necesariamente bipartitos). Corre en el tiempo . Se puede lograr un mejor rendimiento de $O$ $($ $\sqrt$ $V$ $E$ $)$ para gráficos generales, igualando el rendimiento del algoritmo Hopcroft-Karp en gráficos bipartitos, con el algoritmo mucho más complicado de Micali y Vazirani. ^[5] El mismo límite se logró mediante 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 rápido de multiplicación de matrices . Esto proporciona un algoritmo aleatorio 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.376})$

^{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 de Blossom y los algoritmos de Micali y Vazirani pueden verse como 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 coincidencia con peso máximo en un gráfico ponderado se llama problema de coincidencia de peso máximo , y su restricción a gráficos bipartitos se llama problema de asignación . Si cada vértice se puede hacer coincidir con varios vértices a la vez, entonces este es un problema de asignación generalizada .
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 coincidencia de cardinalidad máxima en hipergrafías es NP completo incluso para hipergrafías de 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 coincidencia bipartita utilizando el algoritmo de pseudoflujo , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C, los algoritmos teóricamente eficientes enumerados anteriormente tienden a funcionar mal en la práctica.
^ Madry, A (2013), "Navegando por el camino central con flujos eléctricos: de flujos a coincidencias y viceversa", Fundamentos de la informática (FOCS), 54º Simposio anual del IEEE de 2013 , págs. 253–262, arXiv : 1307.2205 , Código Bib : 2013arXiv1307.2205M
^ Borradaile, Glencora; Klein, Philip N.; Moisés, 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, SEÑOR 3681377, S2CID 207071917
^ Micali, S .; Vazirani, VV (1980), "Un algoritmo para encontrar la máxima coincidencia en gráficos generales", Proc. 21º Simposio IEEE. Fundamentos de la informática , págs. 17–27, doi :10.1109/SFCS.1980.12, S2CID 27467816 $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ .
^ Blum, Norberto (1990). Paterson, Michael S. (ed.). "Un nuevo enfoque para la máxima coincidencia en gráficos generales" (PDF) . Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. Berlín, Heidelberg: Springer. 443 : 586–597. doi :10.1007/BFb0032060. ISBN 978-3-540-47159-2.
^ Gabow, Harold N ; Tarjan, Robert E (1 de octubre de 1991). "Algoritmos de escala más rápidos para problemas generales de coincidencia de gráficos" (PDF) . Revista de la ACM . 38 (4): 815–853. doi :10.1145/115234.115366. S2CID 18350108.
^ Mucha, M.; Sankowski, P. (2004), "Emparejamientos máximos mediante eliminación gaussiana" (PDF) , Proc. 45º Simposio IEEE. Fundamentos de la informática , págs. 248-255
^ Duan, corrió; Pettie, Seth (1 de enero de 2014). "Aproximación en tiempo lineal para igualar el 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.), "Reducibilidad entre problemas combinatorios", 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, págs. 85-103 , doi :10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2