Corte mínimo - algoritmo de Stoer-Wagner

Enunciado del problema

Se da un grafo no dirigido ponderado $G$ con $n$ vértices y $m$ aristas. Un corte $C$ es un subconjunto propio no vacío de los vértices (en efecto, un corte es una partición de los vértices en dos conjuntos no vacíos: los que pertenecen a $C$ y todos los demás). El peso de un corte es la suma de los pesos de las aristas que cruzan el corte, es decir, las aristas que tienen exactamente un extremo en $C$:

$$w(C) = \sum_{\substack{(v,u) \in E \ u \in C,\ v \not\in C}} c(v,u),$$

donde $E$ denota el conjunto de todas las aristas del grafo $G$, y $c(v,u)$ es el peso de la arista $(v,u)$.

La tarea es encontrar un corte de peso mínimo.

A veces este problema se llama el “corte mínimo global”, en contraste con el problema en el que se dan un vértice fuente y un vértice sumidero, y hay que encontrar un corte mínimo $C$ que contenga el sumidero pero no la fuente. El corte mínimo global es igual al mínimo entre los cortes de costo mínimo sobre todos los pares posibles de fuente y sumidero.

Aunque este problema se puede resolver con un algoritmo de flujo máximo (ejecutándolo $O(n^2)$ veces para todos los pares posibles de fuente y sumidero), a continuación describimos un algoritmo mucho más simple y rápido, propuesto por Mechthild Stoer y Frank Wagner en 1994.

En general se permiten bucles y aristas múltiples, aunque los bucles obviamente no influyen en el resultado de ninguna forma, y las aristas múltiples siempre se pueden reemplazar por una sola arista con su peso combinado. Por tanto, por simplicidad, asumiremos que el grafo de entrada no contiene bucles ni aristas múltiples.

Descripción del algoritmo

La idea básica del algoritmo es muy simple. Repetimos de forma iterativa el siguiente proceso: encontrar el corte mínimo entre algún par de vértices $s$ y $t$, y luego fusionar estos dos vértices en uno (conectando sus listas de adyacencia). Eventualmente, después de $n-1$ iteraciones, el grafo se comprimirá en un solo vértice y el proceso se detiene. Después de eso, la respuesta es el mínimo entre todos los $n-1$ cortes encontrados. En efecto, en cada $i$-ésima etapa, el corte mínimo encontrado $C_i$ entre los vértices $s_i$ y $t_i$ o bien resulta ser el corte mínimo global deseado, o, por el contrario, es desventajoso poner $s_i$ y $t_i$ en conjuntos distintos, así que no empeoramos nada al fusionar estos dos vértices en uno.

Así redujimos el problema al siguiente: para un grafo dado, encontrar el corte mínimo entre algún par arbitrario de vértices $s$ y $t$. Para resolver este problema se propuso el siguiente proceso, también iterativo. Introducimos un conjunto de vértices $A$, que inicialmente contiene un solo vértice arbitrario. En cada paso, encontramos el vértice más fuertemente conectado al conjunto $A$, es decir, el vértice $v \not\in A$ para el cual la siguiente cantidad es máxima:

$$w(v,A) = \sum_{\substack{(v,u) \in E \ u \in A}} c(v,u)$$

(es decir, la suma de los pesos de las aristas con un extremo en $v$ y el otro en $A$ es máxima).

Otra vez, este proceso termina después de $n-1$ iteraciones, cuando todos los vértices se han movido al conjunto $A$ (de paso, este proceso se parece mucho al algoritmo de Prim). Entonces, como afirma el teorema de Stoer-Wagner, si denotamos por $s$ y $t$ los últimos dos vértices agregados a $A$, el corte mínimo entre los vértices $s$ y $t$ consiste en un solo vértice: $t$. La demostración de este teorema se dará en la siguiente sección (como suele ocurrir, por sí misma no contribuye de ninguna forma a la comprensión del algoritmo).

Así, el esquema general del algoritmo de Stoer-Wagner es el siguiente. El algoritmo consiste en $n-1$ fases. En cada fase, el conjunto $A$ se inicializa para que contenga algún vértice, y se calculan los pesos iniciales $w(v,A)$ de los vértices. Luego siguen $n-1$ iteraciones, en cada una de las cuales se elige el vértice $u$ con el mayor valor $w(v,A)$ y se agrega al conjunto $A$, después de lo cual se recalculan los valores de $w$ para los vértices restantes (para lo cual, obviamente, hay que recorrer todas las aristas de la lista de adyacencia del vértice seleccionado $u$). Después de realizar todas las iteraciones, registramos en $s$ y $t$ los últimos dos vértices agregados, y el valor $w(t,A \setminus t)$ se puede tomar como el costo del corte mínimo encontrado entre $s$ y $t$. Luego comparamos el corte mínimo encontrado con la respuesta actual, y si es menor, actualizamos la respuesta, y pasamos a la siguiente fase.

Si no usamos estructuras de datos sofisticadas, la parte más crítica es encontrar el vértice con el mayor valor de $w$. Si lo hacemos en $O(n)$, entonces, dado que hay $n-1$ fases con $n-1$ iteraciones cada una, la complejidad resultante del algoritmo es $O(n^3)$.

Si usamos heaps de Fibonacci para encontrar el vértice con el mayor valor de $w$ (que permiten aumentar el valor de una clave en $O(1)$ amortizado y extraer el máximo en $O(\log n)$ amortizado), entonces todas las operaciones relacionadas con el conjunto $A$ en una fase se realizan en $O(m + n \log n)$. La complejidad resultante del algoritmo en este caso es $O(n m + n^2 \log n)$.

Demostración del teorema de Stoer-Wagner

Recordemos el enunciado de este teorema. Si agregamos todos los vértices al conjunto $A$ uno por uno, cada vez agregando el vértice más fuertemente conectado a este conjunto, entonces denotamos el penúltimo vértice agregado por $s$ y el último por $t$. Entonces el corte $s$-$t$ mínimo consiste en un solo vértice: $t$.

Para demostrarlo, consideramos un corte $s$-$t$ arbitrario $C$ y mostramos que su peso no puede ser menor que el peso del corte que consiste en el único vértice $t$:

$$w({t}) \le w(C).$$

Para ello, demostramos el siguiente hecho. Sea $A_v$ el estado del conjunto $A$ inmediatamente antes de agregar el vértice $v$. Sea $C_v$ el corte del conjunto $A_v \cup {v}$ inducido por el corte $C$ (dicho de forma simple, $C_v$ es igual a la intersección de estos dos conjuntos de vértices). Además, un vértice $v$ se llama activo (respecto del corte $C$) si el vértice $v$ y el vértice agregado previamente pertenecen a partes distintas del corte $C$. Entonces, afirmamos, para cualquier vértice activo $v$ se cumple la siguiente desigualdad:

$$w(v,A_v) \le w(C_v).$$

En particular, $t$ es un vértice activo (ya que el vértice agregado antes de él fue $s$), y para $v = t$ esta desigualdad se convierte en el enunciado del teorema:

$$w(t,A_t) = w({t}) \le w(C_t) = w(C).$$

Así, demostraremos esta desigualdad usando inducción matemática.

Para el primer vértice activo $v$ la desigualdad se cumple (más aún, se convierte en una igualdad), ya que todos los vértices de $A_v$ pertenecen a una parte del corte, y $v$ pertenece a la otra.

Ahora supongamos que esta desigualdad se cumple para todos los vértices activos hasta algún vértice $v$; demostrémosla para el siguiente vértice activo $u$. Para ello, transformamos el lado izquierdo:

$$w(u,A_u) \equiv w(u,A_v) + w(u,A_u \setminus A_v).$$

Primero, nótese que:

$$w(u,A_v) \le w(v,A_v),$$

lo cual se sigue del hecho de que cuando el conjunto $A$ era igual a $A_v$, el vértice agregado a él fue precisamente $v$ y no $u$, lo que significa que tenía el mayor valor de $w$.

Además, como $w(v,A_v) \le w(C_v)$ por la hipótesis de inducción, obtenemos:

$$w(u,A_v) \le w(C_v),$$

de lo cual tenemos:

$$w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v).$$

Ahora nótese que el vértice $u$ y todos los vértices de $A_u \setminus A_v$ están en partes distintas del corte $C$, así que la cantidad $w(u,A_u \setminus A_v)$ denota la suma de los pesos de las aristas que se cuentan en $w(C_u)$ pero que aún no se habían contado en $w(C_v)$, de lo cual obtenemos:

$$w(u,A_u) \le w(C_v) + w(u,A_u \setminus A_v) \le w(C_u),$$

como se requería.

Hemos demostrado la relación $w(v,A_v) \le w(C_v)$, y, como se mencionó arriba, de ella se sigue todo el teorema.

Implementación

Para la implementación más simple y clara (con complejidad $O(n^3)$), el grafo se representa como una matriz de adyacencia. La respuesta se guarda en las variables best_cost y best_cut (el costo del corte mínimo y los vértices contenidos en él).

Para cada vértice, el arreglo exist guarda si todavía existe, o si se fusionó con algún otro vértice. La lista v[i] para cada vértice comprimido $i$ guarda los números de los vértices originales que se comprimieron en este vértice $i$.

El algoritmo consiste en $n-1$ fases (el bucle sobre la variable ph). En cada fase, todos los vértices están inicialmente fuera del conjunto $A$, así que el arreglo in_a se llena con ceros, y las conectividades $w$ de todos los vértices son cero. En cada una de las $n-\mathrm{ph}$ iteraciones, se encuentra el vértice sel con el mayor valor de $w$. Si esta es la última iteración, se actualiza la respuesta si es necesario, y se fusionan en uno el penúltimo prev y el último sel vértices seleccionados. Si la iteración no es la última, entonces sel se agrega al conjunto $A$, después de lo cual se recalculan los pesos de todos los vértices restantes.

Nótese que el algoritmo “estropea” el grafo g durante su trabajo, así que si todavía se necesita después, hay que guardar una copia de él antes de llamar a la función.

const int MAXN = 500;
int n;
long long g[MAXN][MAXN];
long long best_cost = (1LL << 62);
vector<int> best_cut;

void mincut() {
    vector<int> v[MAXN];
    for (int i = 0; i < n; ++i)
        v[i].assign(1, i);
    long long w[MAXN];
    bool exist[MAXN], in_a[MAXN];
    memset(exist, true, sizeof exist);
    for (int ph = 0; ph < n - 1; ++ph) {
        memset(in_a, false, sizeof in_a);
        memset(w, 0, sizeof w);
        for (int it = 0, prev; it < n - ph; ++it) {
            int sel = -1;
            for (int i = 0; i < n; ++i)
                if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel]))
                    sel = i;
            if (it == n - ph - 1) {
                if (w[sel] < best_cost) {
                    best_cost = w[sel];
                    best_cut = v[sel];
                }
                v[prev].insert(v[prev].end(), v[sel].begin(), v[sel].end());
                for (int i = 0; i < n; ++i)
                    g[prev][i] = g[i][prev] += g[sel][i];
                exist[sel] = false;
            } else {
                in_a[sel] = true;
                for (int i = 0; i < n; ++i)
                    w[i] += g[sel][i];
                prev = sel;
            }
        }
    }
}

Literatura

• Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm. Journal of the ACM, 44(4):585-591, 1997 
• Kurt Mehlhorn, Christian Uhrig. The minimum cut algorithm of Stoer and Wagner [1995]