La coincidencia máxima de cardinalidad es un problema fundamental en la teoría de grafos . [1] Se nos da un gráfico , 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 de modo que cada vértice sea adyacente como máximo a una arista del subconjunto. Como cada borde cubrirá exactamente dos vértices, este problema es equivalente 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 grafo bipartito , cuyos vértices V están divididos entre los vértices izquierdos en X y los 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 gráficos bipartitos
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 , pero se puede adaptar fácilmente: simplemente transformamos el gráfico en una red de flujo agregando un vértice fuente al gráfico que tiene un borde en todos los vértices izquierdos en X , agregando un vértice sumidero teniendo una arista de todos los vértices correctos en Y , manteniendo todas las aristas entre X e Y , y dando una capacidad de 1 a cada arista. El algoritmo de Ford-Fulkerson continuará encontrando repetidamente una ruta de aumento de algún x ∈ X a algo de y ∈ Y y actualizando la coincidencia M tomando la diferencia simétrica de esa ruta con M (asumiendo que tal ruta existe). Como cada camino se puede encontrar en tiempo, el tiempo de ejecución es , Y el máximo a juego consta de los bordes de E que llevan fluya desde X a Y .
Una mejora de este algoritmo viene dada por el algoritmo Hopcroft-Karp más elaborado , que busca múltiples rutas de aumento simultáneamente. Este algoritmo se ejecuta en hora.
El algoritmo de Chandran y Hochbaum [2] para gráficos bipartitos se ejecuta en el tiempo que depende del tamaño de la coincidencia máxima, que para es . Usar operaciones booleanas en palabras de tamaño la complejidad se mejora aún más para . [2]
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 encon el algoritmo de Madry basado en flujos eléctricos. [3]
- Para gráficos bipartitos planos , el problema se puede resolver a tiempodonde 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 a tiempo. Se puede lograr un mejor desempeño de O ( √ V E ) para gráficos generales, igualando el desempeño 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]
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 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]
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 flor 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 correspondencia con el peso máximo en una gráfica ponderada se denomina problema de correspondencia de peso máximo , y su restricción a las gráficas bipartitas se denomina problema de asignación . Si cada vértice puede coincidir con varios vértices a la vez, entonces este es 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 comparan primero.
- El problema de encontrar una coincidencia de cardinalidad máxima en un hipergráfico es NP-completo incluso para hipergráficos uniformes de 3. [10]
Referencias
- ^ West, Douglas Brent (1999), Introducción a la teoría de gráficos (2a ed.), Prentice Hall, Capítulo 3, ISBN 0-13-014400-2
- ^ a b c Chandran, Bala G .; Hochbaum, Dorit S. (2011), Mejoras prácticas y teóricas para el emparejamiento bipartito utilizando el algoritmo pseudoflow , 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 la ruta central con flujos eléctricos: de los flujos a las coincidencias y viceversa", Fundamentos de la informática (FOCS), 54º Simposio Anual de IEEE 2013 , 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 3.681.377 , S2CID 207071917
- ^ Micali, S .; Vazirani, VV (1980), "Analgoritmo 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.
- ^ Blum, Norbert (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 en 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 escalado 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 a través de la eliminación gaussiana" (PDF) , Proc. 45th IEEE Symp. 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 máxima coincidencia de peso" (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 between 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 Oficina de Investigación Naval, Programa de Matemáticas, IBM World Trade Corporation y el Departamento de Ciencias Matemáticas de Investigación de IBM, Serie de Simposios de Investigación de IBM, Boston, MA: Springer US, págs. 85-103 , doi : 10.1007 / 978-1-4684-2001-2_9 , ISBN 978-1-4684-2001-2