Algoritmo Blossom

En teoría de grafos , el algoritmo Blossom es un algoritmo para construir emparejamientos máximos en grafos . El algoritmo fue desarrollado por Jack Edmonds en 1961, ^{[ 1 ]} y publicado en 1965. ^{[ 2 ]} Dado un grafo general G = ( V , E ) , el algoritmo encuentra un emparejamiento M tal que cada vértice en V sea incidente con como máximo una arista en M y | M | sea máximo. El emparejamiento se construye mejorando iterativamente un emparejamiento vacío inicial a lo largo de caminos de aumento en el grafo. A diferencia del emparejamiento bipartito , la idea clave nueva es que un ciclo de longitud impar en el grafo (Blossom) se contrae a un solo vértice, y la búsqueda continúa iterativamente en el grafo contraído.

El algoritmo se ejecuta en tiempo O ( | E | | V | ² ) , donde | E | es el número de aristas del grafo y | V | es su número de vértices . Un mejor tiempo de ejecución de${\displaystyle O(|E|{\sqrt {|V|}})}$para la misma tarea se puede lograr con el algoritmo más complicado de Micali y Vazirani. ^{[ 3 ]}

Una de las principales razones por las que el algoritmo Blossom es importante es que proporcionó la primera prueba de que se podía encontrar un emparejamiento de tamaño máximo utilizando un tiempo de cálculo polinomial. Otra razón es que condujo a una descripción poliédrica de programación lineal del politopo de emparejamiento , lo que dio lugar a un algoritmo para el emparejamiento de peso mínimo . ^{[ 4 ]} Como explica Alexander Schrijver , la importancia del resultado radica en que este fue el primer politopo cuya prueba de integralidad "no se deriva simplemente de la unimodularidad total , y su descripción supuso un avance en la combinatoria poliédrica ". ^{[ 5 ]}

Dado G = ( V , E ) y un vértice M correspondiente a G , un vértice v está expuesto si ninguna arista de M es incidente con v . Un camino en G es un camino alternante si sus aristas están alternativamente fuera de M y en M (o en M y fuera de M ). Un camino de aumento P es un camino alternante que comienza y termina en dos vértices expuestos distintos. Nótese que el número de aristas no coincidentes en un camino de aumento es mayor en uno que el número de aristas coincidentes, y por lo tanto el número total de aristas en un camino de aumento es impar. Un aumento coincidente a lo largo de un camino de aumento P es la operación de reemplazar M con un nuevo vértice coincidente.

${\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)}$.

Según el lema de Berge , el emparejamiento M es máximo si y solo si no existe ningún camino de aumento de M en G. ^{[ 6 ] [ 7 ]} Por lo tanto, o bien un emparejamiento es máximo, o bien puede aumentarse. Así, partiendo de un emparejamiento inicial, podemos calcular un emparejamiento máximo aumentando el emparejamiento actual con caminos de aumento mientras podamos encontrarlos, y regresar cuando no queden caminos de aumento. Podemos formalizar el algoritmo de la siguiente manera:

 ENTRADA: Grafo G , coincidencia inicial M en G SALIDA: coincidencia máxima M* en G A1 función find_maximum_matching ( G , M ) : M* A2 P ← find_augmenting_path ( G , M ) A3 si P no está vacío entonces A4 devolver find_maximum_matching ( G , aumentar M a lo largo de P ) A5 de lo contrario A6 regresa M A7 fin si A8 fin función

Todavía tenemos que describir cómo se pueden encontrar eficientemente las rutas de aumento. La subrutina para encontrarlas utiliza ramificaciones y contracciones.

Dado G = ( V , E ) y un M correspondiente de G , una flor B es un ciclo en G que consta de 2 k + 1 aristas de las cuales exactamente k pertenecen a M , y donde uno de los vértices v del ciclo (la base ) es tal que existe un camino alterno de longitud par (el tallo ) desde v hasta un vértice expuesto w .

En busca de flores:

• Recorre el grafo comenzando desde un vértice expuesto.
• Partiendo de ese vértice, etiquételo como un vértice exterior o .
• Alterna el etiquetado entre vértices internos (i) y externos (o) de manera que no haya dos vértices adyacentes con la misma etiqueta.
• Si terminamos con dos vértices adyacentes etiquetados como o exterior, entonces tenemos un ciclo de longitud impar y, por lo tanto, una floración.

Definimos el grafo contraído G' como el grafo obtenido de G al contraer cada arista de B , y definimos el emparejamiento contraído M' como el emparejamiento de G' correspondiente a M.

G' tiene un camino de aumento M' si y solo si G tiene un camino de aumento M , y cualquier camino de aumento M' P' en G' puede elevarse a un camino de aumento M en G deshaciendo la contracción por B de modo que el segmento de P' ( ^si lo hay) que atraviesa v _B sea reemplazado por un segmento apropiado que atraviese B. [ ^{8 ]} En más detalle:

• si P' atraviesa un segmento u → v _B → w en G' , entonces este segmento se reemplaza con el segmento u → ( u' → … → w' ) → w en G , donde los vértices de la flor u' y w' y el lado de B , ( u' → … → w' ) , que va de u' a w' se eligen para asegurar que el nuevo camino siga siendo alternante ( u' está expuesto con respecto a${\displaystyle M\cap B}$,${\displaystyle \{w',w\}\en E\setminus M}$).

• Si P' tiene un punto final v _B , entonces el segmento de ruta u → v _B en G' se reemplaza con el segmento u → ( u' → … → v' ) en G , donde los vértices de la flor u' y v' y el lado de B , ( u' → … → v' ) , que va de u' a v' se eligen para asegurar que la ruta sea alterna ( v' está expuesto,${\displaystyle \{u',u\}\en E\setminus M}$).

De este modo, los grafos de floración pueden contraerse y la búsqueda puede realizarse en los grafos contraídos. Esta reducción es la base del algoritmo de Edmonds.

La búsqueda de un camino de aumento utiliza una estructura de datos auxiliar que consiste en un bosque F cuyos árboles individuales corresponden a porciones específicas del grafo G. De hecho, el bosque F es el mismo que se usaría para encontrar emparejamientos máximos en grafos bipartitos (sin necesidad de flores de contracción). En cada iteración, el algoritmo (1) encuentra un camino de aumento, (2) encuentra una flor y recurre sobre el grafo contraído correspondiente, o (3) concluye que no hay caminos de aumento. La estructura auxiliar se construye mediante un procedimiento incremental que se describe a continuación. ^{[ 8 ]}

El procedimiento de construcción considera los vértices v y las aristas e en G y actualiza F incrementalmente según corresponda. Si v está en un árbol T del bosque, denotamos root(v)por la raíz de T. Si tanto u como v están en el mismo árbol T en F , denotamos por distance(u,v)la longitud del camino único de u a v en T.

 ENTRADA: Grafo G , emparejamiento de M en G SALIDA: camino de aumento P en G o camino vacío si no se encuentra ninguno B01 función find_augmenting_path ( G , M ) : P B02 F ← bosque vacío B03 Desmarcar todos los vértices y aristas en G , marcar todas las aristas de M B05 Para cada vértice expuesto v , hacer B06 Crear un árbol singleton { v } y agregar el árbol a F B07 Fin del bucle B08 Mientras haya un vértice sin marcar v en F con distancia(v, raíz(v)) par, hacer B09 Mientras exista una arista sin marcar e = { v , w }, hacer B10 Si w no está en F , entonces // w está emparejado, así que agregar la arista emparejada de e y w a F B11 x ← vértice emparejado con w en M B12 Agregar las aristas { v , w } y { w , x } al árbol de v B13 Si no, B14 Si distancia(w, raíz(w)) es impar, entonces // No hagas nada. B15 de lo contrario B16 si raíz(v) ≠ raíz(w) entonces // Informar una ruta de aumento en F${\displaystyle \cup }${ e }. B17 P ← ruta ( raíz ( v ) → ... → v ) → ( w → ... → raíz ( w )) B18 devuelve P B19 de lo contrario // Contrae una flor en G y busca el camino en el grafo contraído. B20 B ← flor formada por e y aristas en el camino v → w en T B21 G', M' ← contraer G y M por B B22 P' ← encontrar_camino_aumentador ( G' , M' ) B23 P ← levantar P' a G B24 devolver P B25 fin si B26 fin si B27 fin si B28 marcar arista e B29 fin mientras B30 marcar vértice v B31 fin mientras B32 devolver ruta vacíaFunción final B33

El algoritmo Blossom es difícil de paralelizar por varias razones. Primero, la contracción y elevación de Blossom modifican recursivamente la estructura del grafo, creando dependencias secuenciales entre las diferentes etapas de la búsqueda. Segundo, una iteración de búsqueda estándar generalmente encuentra solo una ruta de aumento, incrementando el tamaño de coincidencia de uno en uno y requiriendo muchas iteraciones en grafos grandes. Tercero, el algoritmo mantiene estructuras dinámicas, incluyendo árboles alternados y grafos contraídos, que se actualizan repetidamente durante la ejecución. En una implementación paralela, estas actualizaciones pueden requerir sincronización y pueden introducir condiciones de carrera. Estos factores han hecho que las implementaciones paralelas eficientes del algoritmo Blossom sean un gran desafío. ^{[ 10 ] [ 11 ]}

X-Blossom ^{[ 12 ]} proporciona una solución paralela eficaz para calcular emparejamientos máximos en grafos generales y aborda directamente estos desafíos. En primer lugar, introduce un nuevo algoritmo Blossom sin recursión. En el algoritmo tradicional, una flor se contrae durante la búsqueda y posteriormente se expande cuando se encuentra un camino de aumento. Por el contrario, el algoritmo sin recursión elimina este proceso de contracción y expansión. La observación clave es que, al construir un camino de aumento, no es necesario conservar el historial completo de contracción recursiva. La información esencial es el camino apropiado de longitud par a través de la estructura de la flor. Por lo tanto, en lugar de contraer una flor y luego expandirla, el algoritmo sin recursión registra el camino de longitud par desde cada vértice relevante en un ciclo de flor hasta la base de la flor ^{[ 12 ]} . Cuando un camino de aumento pasa a través de la flor, el camino registrado se utiliza para reconstruir el camino correspondiente en el grafo original, como se muestra en la figura siguiente. Esta representación conserva el efecto del manejo de la flor al tiempo que mantiene estática la estructura del grafo durante la búsqueda.

Esta variante sin recursión ofrece una oportunidad crucial para la paralelización masiva. Dado que el grafo no se modifica recursivamente mediante contracción y elevación, se pueden examinar simultáneamente múltiples vértices válidos en el bosque de búsqueda actual. X-Blossom utiliza esta propiedad para identificar múltiples rutas de aumento disjuntas en vértices en una sola iteración de búsqueda, lo que permite que el tamaño de coincidencia aumente en más de uno por iteración.

En su implementación, X-Blossom reemplaza las estructuras de árboles alternados con una tabla de rutas. Esta tabla registra rutas de longitud par para los vértices, independientemente de si pertenecen a una flor. Como resultado, el algoritmo evita la construcción y deconstrucción repetida de árboles alternados y grafos contraídos. Esto reduce la sobrecarga del trazado de rutas y hace que el algoritmo sea más adecuado para la ejecución en paralelo. Los experimentos reportados en el estudio de X-Blossom mostraron que su diseño sin recursión mejora significativamente el rendimiento secuencial, y su versión paralela logra aceleraciones y escalabilidad en plataformas multinúcleo en conjuntos de datos tanto reales como sintéticos ^{[ 12 ]} .

Cuando G es bipartito , no hay ciclos impares en G. En ese caso, nunca se encontrarán flores y se pueden eliminar las líneas B20 a B24 del algoritmo. El algoritmo se reduce así al algoritmo estándar para construir emparejamientos de cardinalidad máxima en grafos bipartitos ^{[ 7 ]} donde buscamos repetidamente un camino de aumento mediante un simple recorrido del grafo : este es, por ejemplo, el caso del algoritmo de Ford-Fulkerson .

El problema de emparejamiento se puede generalizar asignando pesos a las aristas en G y solicitando un emparejamiento con el máximo peso total: esto se conoce como el problema de emparejamiento de peso máximo . Este problema se puede resolver mediante un algoritmo combinatorio que utiliza el algoritmo Blossom sin ponderación como subrutina. Existen algoritmos eficientes de tiempo polinomial para este problema en varias bibliotecas de software, como NetworkX , LEDA y la biblioteca de grafos LEMON .

• X-Blossom