El algoritmo de Hopcroft & Karp para calcular un emparejamiento máximo toma tiempo $\mathcal O(mn^{1/2})$, el cual está compuesto por $\mathcal O(n^{1/2})$ iteraciones y cada iteración toma $\mathcal O(m)$.
En mi guion de conferencia dice que $\mathcal O(n^{1/2})$ iteraciones se basan en el hecho de que hay "relativamente" caminos $M$-aumentantes cortos de longitud máxima de $2\cdot \lfloor |M|/ (s - |M|) \rfloor + 1$.
Tengo problemas para entender este límite superior para la longitud de un camino.
Comentarios:
- $G = (V, E)$ con $V = U \cup W$ grafo bipartito
- $s \le n = |V|$ cardinalidad de un emparejamiento máximo $S$
- $M$ cualquier emparejamiento en $G$
Además, sé que
- Después de cada iteración ya no hay caminos más cortos de longitud $l$.
- Los caminos $M$-aumentantes más cortos se extienden por el factor aditivo de 2, dado que siempre tienen longitud impar.
- Emparejamiento $|M \triangle P| = |M| + 1$ donde $\triangle$ es la diferencia simétrica de un emparejamiento $ M$ y un camino $M$-aumentante $P$
