Algoritmo de Hopcroft-Karp

En informática , el algoritmo de Hopcroft-Karp (a veces llamado con mayor precisión algoritmo de Hopcroft-Karp-Karzanov ) ^{[ 1 ]} es un algoritmo que toma un grafo bipartito como entrada y produce un emparejamiento de cardinalidad máxima como salida: un conjunto de tantas aristas como sea posible con la propiedad de que no hay dos aristas que compartan un extremo. Se ejecuta en${\displaystyle O(|E|{\sqrt {|V|}})}$tiempo en el peor de los casos , donde${\displaystyle E}$es un conjunto de aristas en el grafo,${\displaystyle V}$es el conjunto de vértices del grafo, y se supone que${\displaystyle |E|=\Omega (|V|)}$En el caso de grafos densos , el límite de tiempo se convierte en${\displaystyle O(|V|^{2.5})}$y para grafos aleatorios dispersos se ejecuta en tiempo${\displaystyle O(|E|\log |V|)}$con alta probabilidad . ^{[ 2 ]}

El algoritmo fue descubierto por John Hopcroft y Richard Karp ( 1973 ) e independientemente por Alexander Karzanov ( 1973 ) . ^{[ 3 ]} Al igual que en métodos anteriores para emparejamiento, como el algoritmo húngaro y el trabajo de Edmonds (1965) , el algoritmo de Hopcroft-Karp aumenta repetidamente el tamaño de un emparejamiento parcial al encontrar caminos de aumento . Estos caminos son secuencias de aristas del grafo, que alternan entre aristas en el emparejamiento y aristas fuera del emparejamiento parcial, y donde la arista inicial y final no están en el emparejamiento parcial. Encontrar un camino de aumento nos permite incrementar el tamaño del emparejamiento parcial, simplemente intercambiando las aristas del camino de aumento (poniendo en el emparejamiento parcial las que no estaban, y viceversa). Los algoritmos más simples para emparejamiento bipartito, como el algoritmo de Ford-Fulkerson , encuentran un camino de aumento por iteración: el algoritmo de Hopcroft-Karp en cambio encuentra un conjunto máximo de caminos de aumento más cortos, para asegurar que solo  ${\displaystyle O({\sqrt {|V|}})}$Se necesitan iteraciones en lugar de${\displaystyle O(|V|)}$iteraciones. El mismo rendimiento de${\displaystyle O(|E|{\sqrt {|V|}})}$Se puede lograr encontrar emparejamientos de cardinalidad máxima en grafos arbitrarios, con el algoritmo más complejo de Micali y Vazirani. ^{[ 4 ]}

El algoritmo de Hopcroft-Karp puede considerarse un caso especial del algoritmo de Dinic para el problema del flujo máximo . ^{[ 5 ]}

Un vértice que no es el punto final de una arista en alguna coincidencia parcial${\displaystyle M}$Se denomina vértice libre . El concepto básico en el que se basa el algoritmo es el de una ruta de aumento , una ruta que comienza en un vértice libre, termina en un vértice libre y alterna entre aristas coincidentes y no coincidentes dentro de la ruta. De esta definición se deduce que, excepto los extremos, todos los demás vértices (si los hay) en la ruta de aumento deben ser vértices no libres. Una ruta de aumento podría constar de solo dos vértices (ambos libres) y una única arista no coincidente entre ellos.

Si${\displaystyle M}$es una coincidencia, y${\displaystyle P}$es una ruta de aumento relativa a${\displaystyle M}$, entonces la diferencia simétrica de los dos conjuntos de aristas,${\displaystyle M\oplus P}$, formaría una pareja con el tamaño${\displaystyle |M|+1}$De este modo, al encontrar rutas de aumento, un algoritmo puede incrementar el tamaño del emparejamiento.

Por el contrario, supongamos que un emparejamiento${\displaystyle M}$no es óptimo y dejar${\displaystyle P}$sea ​​la diferencia simétrica${\displaystyle M\oplus M^{*}}$dónde${\displaystyle M^{*}}$es una coincidencia óptima . Porque${\displaystyle M}$y${\displaystyle M^{*}}$son ambos emparejamientos, cada vértice tiene grado como máximo 2 en${\displaystyle P}$. Entonces${\displaystyle P}$debe formar una colección de ciclos disjuntos, de caminos con un número igual de aristas coincidentes y no coincidentes en${\displaystyle M}$, de aumentar las rutas para${\displaystyle M}$y de aumentar las rutas para${\displaystyle M^{*}}$; pero esto último es imposible porque${\displaystyle M^{*}}$es óptimo. Ahora, los ciclos y los caminos con igual número de vértices coincidentes y no coincidentes no contribuyen a la diferencia de tamaño entre${\displaystyle M}$y${\displaystyle M^{*}}$, por lo que esta diferencia es igual al número de caminos de aumento para${\displaystyle M}$en${\displaystyle P}$Por lo tanto, siempre que exista una coincidencia${\displaystyle M^{*}}$mayor que el ajuste actual${\displaystyle M}$, también debe existir una ruta de aumento. Si no se puede encontrar una ruta de aumento, un algoritmo puede terminar de forma segura, ya que en este caso${\displaystyle M}$debe ser óptimo.

Un camino de aumento en un problema de emparejamiento está estrechamente relacionado con los caminos de aumento que surgen en los problemas de flujo máximo , caminos a lo largo de los cuales se puede aumentar la cantidad de flujo entre los terminales del flujo. Es posible transformar el problema de emparejamiento bipartito en una instancia de flujo máximo, de modo que los caminos alternados del problema de emparejamiento se conviertan en caminos de aumento del problema de flujo. Basta con insertar dos vértices, origen y sumidero, e insertar aristas de capacidad unitaria desde el origen a cada vértice en${\displaystyle U}$y desde cada vértice en${\displaystyle V}$al fregadero; y deje que los bordes de${\displaystyle U}$a${\displaystyle V}$tienen capacidad unitaria. ^{[ 6 ]} Una generalización de la técnica utilizada en el algoritmo de Hopcroft-Karp para encontrar el flujo máximo en una red arbitraria se conoce como el algoritmo de Dinic .

El algoritmo puede expresarse en el siguiente pseudocódigo .

Entrada : Grafo bipartito${\displaystyle G(U\cup V,E)}$

Salida : Coincidencia${\displaystyle M\subseteq E}$

${\displaystyle M\leftarrow \emptyset }$

repetir

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$Conjunto máximo de caminos de aumento más cortos disjuntos en vértices

${\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}$

hasta${\displaystyle {\mathcal {P}}=\emptyset }$

En más detalle, deje que${\displaystyle U}$y${\displaystyle V}$sean los dos conjuntos en la bipartición de${\displaystyle G}$y deje que la coincidencia de${\displaystyle U}$a${\displaystyle V}$en cualquier momento ser representado como el conjunto${\displaystyle M}$El algoritmo se ejecuta en fases. Cada fase consta de los siguientes pasos.

• Una búsqueda en anchura divide los vértices del grafo en capas.
  • Los vértices libres en${\displaystyle U}$se utilizan como vértices iniciales de esta búsqueda y forman la primera capa de la partición. En el primer nivel de la búsqueda, solo hay aristas sin emparejar, ya que los vértices libres en${\displaystyle U}$Por definición, no son adyacentes a ningún borde coincidente.
  • En los niveles subsiguientes de la búsqueda, se requiere que los bordes recorridos alternen entre coincidentes y no coincidentes. Es decir, al buscar sucesores desde un vértice en${\displaystyle U}$, solo se pueden recorrer los bordes no coincidentes, mientras que desde un vértice en${\displaystyle V}$Solo se pueden recorrer las aristas coincidentes.
  • La búsqueda finaliza en la primera capa.${\displaystyle k}$donde uno o más vértices libres en${\displaystyle V}$se alcanzan.
  • Debido a que cada ruta que llega a un nodo coincidente procede inmediatamente a su pareja en la coincidencia, algunas implementaciones asignan la misma profundidad a ambos vértices, incrementando la profundidad solo cuando se recorre una arista no coincidente.
• Todos los vértices libres en${\displaystyle V}$en la capa${\displaystyle k}$se recopilan en un conjunto${\displaystyle F\subseteq V}$. Es decir, un vértice${\displaystyle v}$se pone en${\displaystyle F}$si y solo si finaliza un camino de aumento más corto.
• El algoritmo encuentra un conjunto máximo de caminos de aumento disjuntos de vértices de longitud${\displaystyle k}$( Máximo significa que no se pueden añadir más caminos de este tipo. Esto es diferente de encontrar el número máximo de dichos caminos, lo cual sería más difícil. Afortunadamente, en este caso basta con encontrar un conjunto máximo de caminos).
  • Este conjunto se puede calcular mediante búsqueda en profundidad (DFS) a partir de${\displaystyle F}$a los vértices libres en${\displaystyle U}$, utilizando el método de capas de búsqueda en amplitud para guiar la búsqueda: el DFS solo puede seguir aristas que conduzcan a un vértice no utilizado en la capa anterior, y las rutas en el árbol DFS deben alternar entre aristas coincidentes y no coincidentes.
  • Una vez que se encuentra un camino de aumento entre uno de los vértices en${\displaystyle F}$y los vértices libres en${\displaystyle U}$, el DFS continúa desde el siguiente vértice de inicio.
  • Cualquier vértice encontrado durante la DFS puede marcarse inmediatamente como usado, ya que si la DFS tiene éxito se utilizará, mientras que si la DFS no tiene éxito (no hay ruta desde él a un vértice libre en${\displaystyle U}$a través de los vértices restantes no utilizados), entonces no tiene sentido explorar más allá de ese vértice en ningún punto posterior en el DFS. Esto garantiza${\displaystyle O(\left|E\right|)}$tiempo de ejecución para el DFS.
  • También es posible trabajar en la otra dirección, desde vértices libres en${\displaystyle U}$a aquellos en${\displaystyle V}$, que es la variante utilizada en el pseudocódigo que aparece a continuación .
• Cada uno de los caminos encontrados de esta manera se utiliza para ampliar${\displaystyle M}$.

El algoritmo finaliza cuando la búsqueda en anchura de una de las fases no encuentra más rutas de aumento.

Cada fase consta de una única búsqueda en amplitud y una única búsqueda en profundidad. Por lo tanto, se puede implementar una única fase en${\displaystyle O(|E|)}$tiempo. Por lo tanto, el primero${\displaystyle {\sqrt {|V|}}}$fases, en un gráfico con${\displaystyle |V|}$vértices y${\displaystyle |E|}$bordes, tómese su tiempo${\displaystyle O(|E|{\sqrt {|V|}})}$.

Cada fase aumenta la longitud del camino de aumento más corto en al menos uno: la fase encuentra un conjunto máximo de caminos de aumento de la longitud dada, por lo que cualquier camino de aumento restante debe ser más largo. Por lo tanto, una vez que el inicial${\displaystyle {\sqrt {|V|}}}$Las fases del algoritmo se han completado, el camino de aumento restante más corto tiene al menos${\displaystyle {\sqrt {|V|}}}$aristas en él. Sin embargo, la diferencia simétrica del emparejamiento óptimo final y del emparejamiento parcial M encontrado por las fases iniciales forma una colección de caminos de aumento disjuntos en vértices y ciclos alternados. Si cada uno de los caminos en esta colección tiene una longitud al menos${\displaystyle {\sqrt {|V|}}}$, puede haber como máximo${\displaystyle {\sqrt {|V|}}}$rutas en la colección, y el tamaño de la coincidencia óptima puede diferir del tamaño de${\displaystyle M}$por como máximo${\displaystyle {\sqrt {|V|}}}$bordes. Dado que cada fase del algoritmo aumenta el tamaño del emparejamiento en al menos uno, puede haber como máximo${\displaystyle {\sqrt {|V|}}}$fases adicionales antes de que finalice el algoritmo.

Dado que el algoritmo realiza un total de como máximo${\displaystyle 2{\sqrt {|V|}}}$fases, toma un tiempo total de${\displaystyle O(|E|{\sqrt {|V|}})}$en el peor de los casos.

En muchos casos, sin embargo, el tiempo que tarda el algoritmo puede ser incluso más rápido de lo que indica este análisis del peor caso. Por ejemplo, en el caso promedio para grafos aleatorios bipartitos dispersos , Bast et al. (2006) (mejorando un resultado anterior de Motwani 1994 ) demostraron que con alta probabilidad todos los emparejamientos no óptimos tienen caminos de aumento de longitud logarítmica . Como consecuencia, para estos grafos, el algoritmo de Hopcroft-Karp tarda${\displaystyle O(\log |V|)}$fases y${\displaystyle O(|E|\log |V|)}$tiempo total.

Para grafos dispersos , el algoritmo de Hopcroft-Karp sigue teniendo el mejor rendimiento conocido en el peor de los casos, pero para grafos densos (${\displaystyle |E|=\Omega (|V|^{2})}$) un algoritmo más reciente de Alt et al. (1991) logra un límite de tiempo ligeramente mejor,${\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}$Su algoritmo se basa en el uso de un algoritmo de flujo máximo de reetiquetado y, cuando la correspondencia creada por este algoritmo se acerca al óptimo, se cambia al método de Hopcroft-Karp.

Varios autores han realizado comparaciones experimentales de algoritmos de emparejamiento bipartito. Sus resultados, en general, tienden a mostrar que el método de Hopcroft-Karp no es tan bueno en la práctica como en la teoría: es superado tanto por estrategias más simples de búsqueda en amplitud y en profundidad para encontrar caminos de aumento, como por técnicas de reetiquetado. ^{[ 7 ]}

La misma idea de encontrar un conjunto máximo de caminos de aumento más cortos también funciona para encontrar emparejamientos de cardinalidad máxima en grafos no bipartitos, y por las mismas razones los algoritmos basados ​​en esta idea toman${\displaystyle O({\sqrt {|V|}})}$fases. Sin embargo, para grafos no bipartitos, la tarea de encontrar los caminos de aumento dentro de cada fase es más difícil. Basándose en el trabajo de varios predecesores más lentos, Micali y Vazirani (1980) mostraron cómo implementar una fase en tiempo lineal, lo que resultó en un algoritmo de emparejamiento no bipartito con el mismo límite de tiempo que el algoritmo de Hopcroft-Karp para grafos bipartitos. La técnica de Micali-Vazirani es compleja, y sus autores no proporcionaron pruebas completas de sus resultados; posteriormente, Peterson y Loui (1988) publicaron una "exposición clara" y otros autores describieron métodos alternativos. ^{[ 8 ]} En 2012, Vazirani ofreció una nueva prueba simplificada del algoritmo de Micali-Vazirani. ^{[ 9 ]}

/* G = U ∪ V ∪ {NIL} donde U y V son los lados izquierdo y derecho del grafo bipartito y NIL es un vértice nulo especial */ La función BFS() es para cada u en U hacer si Pair_U[u] = NIL entonces Dist[u] := 0 Encolar(Q, u) demás Dist[u] := ∞ Dist[NIL] := ∞ mientras Empty(Q) = falso hacer u := Dequeue(Q) Si Dist[u] < Dist[NIL] entonces para cada v en Adj[u] hacer si Dist[Pair_V[v]] = ∞ entonces Dist[Pair_V[v]] := Dist[u] + 1 Encolar(Q, Par_V[v]) devolver Dist[NIL] ≠ ∞ La función DFS(u) es si u ≠ NIL entonces para cada v en Adj[u] hacer si Dist[Pair_V[v]] = Dist[u] + 1 entonces si DFS(Pair_V[v]) = verdadero entonces Par_V[v] := u Par_U[u] := v devolver verdadero Dist[u] := ∞ devolver falso devolver verdadero La función Hopcroft-Karp es para cada u en U hacer Pair_U[u] := NIL para cada v en V hacer Pair_V[v] := NIL coincidencia := 0 mientras BFS() = verdadero hacer para cada u en U hacer si Pair_U[u] = NIL entonces si DFS(u) = verdadero entonces coincidencia := coincidencia + 1 coincidencia de retorno

Dist[u] = ∞ devolver falso

• Emparejamiento de cardinalidad máxima , el problema resuelto por el algoritmo, y su generalización a grafos no bipartitos.
• Problema de asignación , una generalización de este problema en grafos ponderados , resuelto, por ejemplo, por el algoritmo húngaro.
• Algoritmo de Edmonds-Karp para encontrar el flujo máximo, una generalización del algoritmo de Hopcroft-Karp.