Stoer–Wagner Algorithm

Definition

Because the definition of source and sink has been removed, we need to redefine the concept of a cut.

(In fact, the definition of a cut in the network-flow context differs from that on Wikipedia; because the cuts most commonly encountered are minimum-cut problems with a source and a sink, this terminology has become conventional.)

Cut

A set of edges whose removal makes a flow network no longer connected (that is, splits it into two subgraphs) is called a cut of the graph.

In other words: in an undirected graph $G = (V, E)$, let $C$ be a set of edges in graph $G$. If deleting from $G$ all edges in $C$ makes $G$ disconnected, then $C$ is called a cut of $G$.

Minimum-cut problem with a source and a sink

Same as the definition in minimum cut.

Minimum-cut problem without a source or a sink

A cut whose edges have the minimum total weight. It is also called the global minimum cut.

Clearly, the complexity of directly running a network flow algorithm is too high.

Stoer–Wagner Algorithm

Introduction

The Stoer–Wagner algorithm was proposed in 1995 by Mechthild Stoer and Frank Wagner. It solves the global minimum-cut problem on undirected graphs with positive edge weights by recursively contracting vertices.

Properties

The time complexity is $O(|V||E| + |V|^{2}\log|V|)$, which is generally approximated as $O(|V|^3)$.

Its implementation is based on the following basic fact: let graph $G$ contain any two vertices $S, T$. Then for graph $G$, any cut $C$ either has $S, T$ in the same connected component, or $C$ is an ${S-T}$ cut.

Procedure

1. Choose any two vertices in graph $G$, namely $s, t$, use them as the source and sink, and find graph $G$'s $S-T$ minimum cut (called a cut of phase), then update the current answer.
2. “Contract” vertices $s, t$. If graph $G$ has $|V|$ greater than $1$, return to the first step.
3. Output the minimum of all cuts of phase.

To contract vertices $s, t$: remove the edge between $s, t$, namely $(s, t)$. For any vertex in $G \setminus \{s, t\}$, say $k$, remove $(t, k)$ and add its edge weight $d(t, k)$ to $d(s, k)$.

Explanation: if $s, t$ are in the same connected component, consider $G \setminus \{s, t\}$ and a vertex $k$ in it. If $(k, s) \in C_{\min}$, then $(k, t) \in C_{\min}$ must also hold; otherwise, since $s, t$ are connected, $k, t$ are connected, which would make $s, k$ lie in the same connected component, and then $C = C_{\min} \setminus \{(t, k)\}$ would be better than $C_{\min}$. The converse is analogous. Therefore, $s, t$ can be regarded as one vertex.

Step 1 considers the case where $s,t$ are not in the same connected component, and step 2 considers the remaining case. Since each execution of step 2 decreases $|V|$ by $1$, the algorithm terminates after $|V| - 1$ executions.

Finding the S-T minimum cut

(Clearly, this is not network flow.)

Suppose that after several contractions the current graph is $G'=(V', E')$, and we execute step 1.

We construct a set $A$, initially setting $A = \varnothing$.

At each step, among all vertices in $V'$, we add a vertex satisfying $i \notin A$ and maximizing the weight function $w(A, i)$ to $A$, until $|A| = |V'|$.

The weight function is defined as follows:

$w(A, i) = \sum_{j \in A} d(i, j)$

(If $(i, j) \notin E'$, then $d(i, j) = 0$.)

It is easy to see that the order in which all vertices are added to $A$ is fixed. Let $\operatorname{ord}(i)$ denote the vertex added in position $i$ in $A$, and let $t = \operatorname{ord}(|V'|)$; let $\operatorname{pos}(v)$ denote the order in which $v$ is added to $A$, namely the size of $|A|$ after $v$ is added.

Then, for any vertex $s$, an $s$-to-$t$ cut has weight $w(t)$.

Proof

Define a vertex $v$ to be activated if and only if, when $v$ is added to $A$, the last vertex in $A$, $u$, was added earlier than $v$, and in the graph $G'' = (V', E'/C)$, $u$ and $v$ are not in the same connected component.

As shown in the figure, the blue and yellow regions are two different connected components; the numbers in brackets indicate the order in which vertices are added to $A$. Gray vertices are activated, while white vertices are not activated.

Define $A_v = \{u \mid \operatorname{pos}(u) < \operatorname{pos}(v)\}$, that is, the set of vertices added strictly before $v$ to $A$. Let $E_v$ be the edge set of the subgraph of $E'$ induced by the vertex set $A_v \cup\{v\}$. (Note that it includes vertex $v$.)

Define the induced cut $C_v$ as $C \cap E_v$. $w(C_v) = \sum_{(i,j) \in C_v} d(i, j)$.

Since $\operatorname{pos}(s) < \operatorname{pos}(t)$ and $s, t$ are not in the same connected component, $t$ is activated. Therefore, $w(A_t, t) \le w(C_t) = w(C)$.

#include <cstring>
#include <iostream>
using namespace std;
constexpr int N = 601;
int fa[N], siz[N], edge[N][N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int dist[N], vis[N], bin[N];
int n, m;

int contract(int &s, int &t) {  // Find s,t
  memset(dist, 0, sizeof(dist));
  memset(vis, false, sizeof(vis));
  int i, j, k, mincut, maxc;
  for (i = 1; i <= n; i++) {
    k = -1;
    maxc = -1;
    for (j = 1; j <= n; j++)
      if (!bin[j] && !vis[j] && dist[j] > maxc) {
        k = j;
        maxc = dist[j];
      }
    if (k == -1) return mincut;
    s = t;
    t = k;
    mincut = maxc;
    vis[k] = true;
    for (j = 1; j <= n; j++)
      if (!bin[j] && !vis[j]) dist[j] += edge[k][j];
  }
  return mincut;
}

constexpr int inf = 0x3f3f3f3f;

int Stoer_Wagner() {
  int mincut, i, j, s, t, ans;
  for (mincut = inf, i = 1; i < n; i++) {
    ans = contract(s, t);
    bin[t] = true;
    if (mincut > ans) mincut = ans;
    if (mincut == 0) return 0;
    for (j = 1; j <= n; j++)
      if (!bin[j]) edge[s][j] = (edge[j][s] += edge[j][t]);
  }
  return mincut;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> n >> m;
  if (m < n - 1) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
  for (int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    int fu = find(u), fv = find(v);
    if (fu != fv) {
      if (siz[fu] > siz[fv]) swap(fu, fv);
      fa[fu] = fv, siz[fv] += siz[fu];
    }
    edge[u][v] += w, edge[v][u] += w;
  }
  int fr = find(1);
  if (siz[fr] != n) {
    cout << 0;
    return 0;
  }
  cout << Stoer_Wagner();
  return 0;
}

Complexity Analysis and Optimization

The complexity of the contract operation is $O(|E| + |V|\log|V|)$.

There are $O(|V|)$ contract operations in total, so the overall complexity is $O(|E||V| + |V|^2\log|V|)$.

As with shortest paths, the bottleneck of the algorithm is finding the vertex with the maximum weight.

One contract operation requires finding the heap maximum $|V|$ times and incrementally updating edge weights $|E|$ times.

A Fibonacci heap can perform heap-maximum queries in $O(\log|V|)$ time and incremental weight updates in $O(1)$ time, giving a theoretical complexity of $O(|E| + |V|\log|V|)$. However, Fibonacci heaps have large constants and require a lot of code, so their practical value is low.

(In actual tests, even enabling O2 requires the judge's performance fluctuations to be favorable in order to pass.)