Algoritmo de Kuhn para matching bipartito máximo

Problema

Se da un grafo bipartito $G$ con $n$ vértices y $m$ aristas. Encontrar el matching máximo, es decir, seleccionar tantas aristas como sea posible de modo que ninguna arista seleccionada comparta un vértice con ninguna otra arista seleccionada.

Descripción del algoritmo

Definiciones necesarias

Un matching $M$ es un conjunto de aristas del grafo que son no adyacentes por pares (en otras palabras, no más de una arista del conjunto debe ser incidente a cualquier vértice del grafo $M$ ). La cardinalidad de un matching es el número de aristas que contiene. Todos aquellos vértices que tienen una arista adyacente del matching (es decir, que tienen grado exactamente uno en el subgrafo formado por $M$ ) se llaman saturados por este matching.
Un matching maximal es un matching $M$ de un grafo $G$ que no es subconjunto de ningún otro matching.
Un matching máximo (también conocido como matching de cardinalidad máxima) es un matching que contiene el mayor número posible de aristas. Todo matching máximo es un matching maximal.
Un camino de longitud $k$ aquí significa un camino simple (es decir, que no contiene vértices ni aristas repetidos) que contiene $k$ aristas, salvo que se indique lo contrario.
Un camino alternante (en un grafo bipartito, respecto de algún matching) es un camino en el que las aristas pertenecen / no pertenecen al matching de forma alternada.
Un camino aumentante (en un grafo bipartito, respecto de algún matching) es un camino alternante cuyos vértices inicial y final son no saturados, es decir, no pertenecen al matching.
La diferencia simétrica (también conocida como unión disyuntiva) de los conjuntos $A$ y $B$ , representada por $A \oplus B$ , es el conjunto de todos los elementos que pertenecen a exactamente uno de $A$ o $B$ , pero no a ambos. Es decir, $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$ .

Lema de Berge

Este lema fue demostrado por el matemático francés Claude Berge en 1957, aunque ya lo había observado el matemático danés Julius Petersen en 1891 y el matemático húngaro Dénes Kőnig en 1931.

Formulación

Un matching $M$ es máximo $\Leftrightarrow$ no existe un camino aumentante relativo al matching $M$ .

Demostración

Ambos lados de la biimplicación se demuestran por contradicción.

Un matching $M$ es máximo $\Rightarrow$ no existe un camino aumentante relativo al matching $M$ .

Sea $P$ un camino aumentante relativo al matching máximo dado $M$ . Este camino aumentante $P$ tendrá necesariamente longitud impar, con una arista más que no está en $M$ que el número de aristas que también están en $M$ . Creamos un matching nuevo $M’$ incluyendo todas las aristas del matching original $M$ excepto las que también están en $P$ , y las aristas de $P$ que no están en $M$ . Este es un matching válido porque los vértices inicial y final de $P$ no están saturados por $M$ , y el resto de los vértices están saturados solo por el matching $P \cap M$ . Este matching nuevo $M’$ tendrá una arista más que $M$ , y por tanto $M$ no podía ser máximo.

Formalmente, dado un camino aumentante $P$ respecto de algún matching máximo $M$ , el matching $M’ = P \oplus M$ cumple $|M’| = |M| + 1$ , una contradicción.
Un matching $M$ es máximo $\Leftarrow$ no existe un camino aumentante relativo al matching $M$ .

Sea $M’$ un matching de cardinalidad mayor que $M$ . Consideramos la diferencia simétrica $Q = M \oplus M’$ . El subgrafo $Q$ ya no es necesariamente un matching. Cualquier vértice en $Q$ tiene grado máximo $2$ , lo que significa que todas las componentes conexas son una de estas tres -
- un vértice aislado
- un camino (simple) cuyas aristas provienen alternadamente de $M$ y de $M’$
- un ciclo de longitud par cuyas aristas provienen alternadamente de $M$ y de $M’$
Como $M’$ tiene cardinalidad mayor que $M$ , $Q$ tiene más aristas de $M’$ que de $M$ . Por el principio del palomar, al menos una componente conexa será un camino que tiene más aristas de $M’$ que de $M$ . Como cualquier camino de ese tipo es alternante, tendrá vértices inicial y final no saturados por $M$ , lo que lo convierte en un camino aumentante para $M$ , lo cual contradice la premisa. $\blacksquare$

Algoritmo de Kuhn

El algoritmo de Kuhn es una aplicación directa del lema de Berge. Esencialmente se describe así:

Primero, tomamos un matching vacío. Luego, mientras el algoritmo sea capaz de encontrar un camino aumentante, actualizamos el matching alternándolo a lo largo de este camino y repetimos el proceso de buscar el camino aumentante. En cuanto no sea posible encontrar tal camino, detenemos el proceso: el matching actual es el máximo.

Resta detallar la forma de encontrar caminos aumentantes. El algoritmo de Kuhn simplemente busca cualquiera de estos caminos usando un recorrido en profundidad o en anchura. El algoritmo recorre todos los vértices del grafo por turnos, iniciando cada recorrido desde él, e intenta encontrar un camino aumentante que empiece en este vértice.

El algoritmo es más cómodo de describir si asumimos que el grafo de entrada ya está partido en dos partes (aunque, de hecho, el algoritmo se puede implementar de modo que el grafo de entrada no esté explícitamente partido en dos partes).

El algoritmo mira todos los vértices $v$ de la primera parte del grafo: $v = 1 \ldots n_1$ . Si el vértice actual $v$ ya está saturado con el matching actual (es decir, alguna arista adyacente a él ya fue seleccionada), entonces se salta este vértice. En caso contrario, el algoritmo intenta saturar este vértice, para lo cual inicia una búsqueda de un camino aumentante que empiece en este vértice.

La búsqueda de un camino aumentante se realiza usando un recorrido especial en profundidad o en anchura (habitualmente se usa el recorrido en profundidad por facilidad de implementación). Inicialmente, el recorrido en profundidad está en el vértice no saturado actual $v$ de la primera parte. Recorremos todas las aristas desde este vértice. Sea la arista actual una arista $(v, to)$ . Si el vértice $to$ aún no está saturado por el matching, entonces hemos logrado encontrar un camino aumentante: consiste en una sola arista $(v, to)$ ; en este caso, simplemente incluimos esta arista en el matching y detenemos la búsqueda del camino aumentante desde el vértice $v$ . En caso contrario, si $to$ ya está saturado con alguna arista $(to, p)$ , entonces iremos a lo largo de esta arista: así intentaremos encontrar un camino aumentante que pase por las aristas $(v, to),(to, p), \ldots$ . Para ello, simplemente vamos al vértice $p$ en nuestro recorrido: ahora intentamos encontrar un camino aumentante desde este vértice.

Así, este recorrido, lanzado desde el vértice $v$ , o bien encontrará un camino aumentante y con ello saturará el vértice $v$ , o bien no encontrará tal camino aumentante (y, por tanto, este vértice $v$ no puede saturarse).

Después de haber recorrido todos los vértices $v = 1 \ldots n_1$ , el matching actual será máximo.

Tiempo de ejecución

El algoritmo de Kuhn puede pensarse como una serie de $n$ ejecuciones de un recorrido en profundidad/anchura sobre el grafo completo. Por tanto, el algoritmo entero se ejecuta en tiempo $O(nm)$ , que en el peor caso es $O(n^3)$ .

Sin embargo, esta cota se puede mejorar un poco. Resulta que, para el algoritmo de Kuhn, es importante qué parte del grafo se elige como primera y cuál como segunda. En efecto, en la implementación descrita arriba, el recorrido en profundidad/anchura solo empieza desde los vértices de la primera parte, así que el algoritmo entero se ejecuta en tiempo $O(n_1m)$ , donde $n_1$ es el número de vértices de la primera parte. En el peor caso, esto es $O(n_1 ^ 2 n_2)$ (donde $n_2$ es el número de vértices de la segunda parte). Esto muestra que es más ventajoso cuando la primera parte contiene menos vértices que la segunda. En grafos muy desbalanceados (cuando $n_1$ y $n_2$ son muy distintos), esto se traduce en una diferencia significativa de tiempos de ejecución.

Implementación

Implementación estándar

Presentamos aquí una implementación del algoritmo anterior basada en un recorrido en profundidad y que acepta un grafo bipartito en forma de un grafo explícitamente partido en dos partes. Esta implementación es muy concisa, y quizá conviene recordarla en esta forma.

Aquí $n$ es el número de vértices en la primera parte, $k$ en la segunda parte, $g[v]$ es la lista de aristas desde el vértice de la primera parte (es decir, la lista de números de los vértices a los que estas aristas llegan desde $v$ ). Los vértices de ambas partes se numeran de forma independiente, es decir, los vértices de la primera parte se numeran $1 \ldots n$ , y los de la segunda se numeran $1 \ldots k$ .

Luego hay dos arreglos auxiliares: $\rm mt$ y $\rm used$ . El primero, $\rm mt$ , contiene información sobre el matching actual. Por conveniencia de programación, esta información se guarda solo para los vértices de la segunda parte: $\textrm{mt[} i \rm]$ es el número del vértice de la primera parte conectado por una arista con el vértice $i$ de la segunda parte (o $-1$ , si no sale de él ninguna arista del matching). El segundo arreglo es $\rm used$ : el arreglo habitual de “visitas” a los vértices en el recorrido en profundidad (hace falta precisamente para que el recorrido en profundidad no entre dos veces en el mismo vértice).

Una función $\textrm{try_kuhn}$ es un recorrido en profundidad. Devuelve $\rm true$ si pudo encontrar un camino aumentante desde el vértice $v$ , y se considera que esta función ya realizó la alternancia del matching a lo largo de la cadena encontrada.

Dentro de la función se recorren todas las aristas salientes del vértice $v$ de la primera parte, y luego se comprueba lo siguiente: si esta arista lleva a un vértice no saturado $to$ , o si este vértice $to$ está saturado, pero es posible encontrar un camino aumentante empezando de forma recursiva desde $\textrm{mt[}to \rm ]$ , entonces decimos que hemos encontrado un camino aumentante, y antes de volver de la función con el resultado $\rm true$ , alternamos la arista actual: redirigimos la arista adyacente a $to$ hacia el vértice $v$ .

El programa principal primero indica que el matching actual está vacío (la lista $\rm mt$ se llena con números $-1$ ). Luego, para cada vértice $v$ de la primera parte se llama a $\textrm{try_kuhn}$ , y se inicia un recorrido en profundidad desde él, habiendo puesto antes a cero el arreglo $\rm used$ .

Vale la pena notar que el tamaño del matching es fácil de obtener como el número de llamadas a $\textrm{try_kuhn}$ en el programa principal que devolvieron el resultado $\rm true$ . El matching máximo deseado está contenido en el arreglo $\rm mt$ .


int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<bool> used;
 
bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}
 
int main() {
    //... lectura del grafo ...
 
    mt.assign(k, -1);
    for (int v = 0; v < n; ++v) {
        used.assign(n, false);
        try_kuhn(v);
    }
 
    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

Repetimos una vez más que el algoritmo de Kuhn es fácil de implementar de modo que funcione sobre grafos que se sabe que son bipartitos, pero cuya partición explícita en dos partes no se ha dado. En este caso, habrá que abandonar la conveniente división en dos partes, y guardar toda la información para todos los vértices del grafo. Para ello, un arreglo de listas $g$ ahora se especifica no solo para los vértices de la primera parte, sino para todos los vértices del grafo (por supuesto, ahora los vértices de ambas partes se numeran con una numeración común, de $1$ a $n$ ). Los arreglos $\rm mt$ y $\rm used$ ahora también se definen para los vértices de ambas partes, y, en consecuencia, hay que mantenerlos en este estado.

Implementación mejorada

Modifiquemos el algoritmo de la siguiente forma. Antes del bucle principal del algoritmo, encontraremos un matching arbitrario con algún algoritmo simple (un algoritmo heurístico simple), y solo entonces ejecutaremos un bucle con llamadas a la función $\textrm{try_kuhn}()$ , que mejorará este matching. Como resultado, el algoritmo funcionará de forma notablemente más rápida en grafos aleatorios: porque en la mayoría de los grafos se puede encontrar fácilmente un matching de tamaño suficientemente grande usando heurísticas, y luego mejorar el matching encontrado hasta el máximo usando el algoritmo de Kuhn usual. Así, nos ahorramos lanzar un recorrido en profundidad desde aquellos vértices que ya incluimos usando la heurística en el matching actual.

Por ejemplo, se puede simplemente iterar sobre todos los vértices de la primera parte y, para cada uno de ellos, encontrar una arista arbitraria que se pueda agregar al matching, y agregarla. Incluso una heurística tan simple puede acelerar el algoritmo de Kuhn varias veces.

Nótese que el bucle principal tendrá que modificarse un poco. Como al llamar a la función $\textrm{try_kuhn}$ en el bucle principal se asume que el vértice actual aún no está incluido en el matching, hay que agregar la comprobación correspondiente.

En la implementación, solo cambiará el código de la función $\textrm{main}()$ :


int main() {
    // ... lectura del grafo ...
 
    mt.assign(k, -1);
    vector<bool> used1(n, false);
    for (int v = 0; v < n; ++v) {
        for (int to : g[v]) {
            if (mt[to] == -1) {
                mt[to] = v;
                used1[v] = true;
                break;
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        if (used1[v])
            continue;
        used.assign(n, false);
        try_kuhn(v);
    }
 
    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

Otra buena heurística es la siguiente. En cada paso, buscará el vértice de menor grado (pero no aislado), seleccionará cualquier arista desde él y la agregará al matching, luego quitará ambos vértices con todas las aristas incidentes del grafo. Esta voracidad funciona muy bien en grafos aleatorios; en muchos casos incluso construye el matching máximo (aunque hay un caso de prueba en contra, en el que encontrará un matching mucho más pequeño que el máximo).

Notas

El algoritmo de Kuhn es una subrutina en el algoritmo húngaro, también conocido como el algoritmo de Kuhn-Munkres.
El algoritmo de Kuhn corre en tiempo $O(nm)$ . En general es simple de implementar; sin embargo, existen algoritmos más eficientes para el problema de matching bipartito máximo, como el algoritmo de Hopcroft-Karp-Karzanov, que corre en tiempo $O(\sqrt{n}m)$ .
El problema de cubierta de vértices mínima es NP-hard para grafos generales. Sin embargo, el teorema de Kőnig establece que, para grafos bipartitos, la cardinalidad del matching máximo es igual a la cardinalidad de la cubierta de vértices mínima. Por tanto, podemos usar algoritmos de matching bipartito máximo para resolver el problema de cubierta de vértices mínima en tiempo polinómico para grafos bipartitos.