AIOJ

This page develops general-graph maximum-weight matching from general-graph maximum-weight perfect matching (a maximum-weight matching can be made perfect by adding zero-weight edges).

Prerequisites

Blossom

Unlike bipartite matching, a general graph may contain odd cycles. An even cycle can be viewed as a bipartite graph.

The Blossom Algorithm handles an odd cycle by shrinking it into a blossom and setting all vertices in the blossom to even vertices. Since every vertex in a blossom can be an even vertex, the whole blossom can be shrunk into one even vertex. Note that a blossom may contain other blossoms.

This can also be formulated as a linear program and its dual, but the blossoms require additional handling.

Vertex labeling and equality edges

Let $z_u$ be the vertex labeling of vertex $u$ , with the same meaning as the vertex labeling defined in the $KM$ algorithm. An edge $e(u,v)$ is an “equality edge” if and only if the sum of the labels of $u$ and $v$ equals the weight of $e$ ( $z_u + z_v = w(e)$ ). In this case, the edge label is $z_e = z_u + z_v − w(e) = 0$ .

Linear programming for maximum-weight perfect matching in general graphs

Definition

Since a blossom contains at least three vertices and becomes one vertex after shrinking, let $O$ be the family of odd-sized sets of size $≥3$ (including all blossoms), and let $\gamma(S)$ denote the edges contained in $S$ .

\begin{aligned} & \text{设} S\subseteq V \\ & \gamma(S)=\{(u,v)\in E:u\in S,v\in S\} \\ & O=\{B\subseteq V:|B|\text{是奇数且}|B|\geq3\} \\ \end{aligned}

Dual problem

Primal problem

\begin{aligned} & \max\sum_{e\in E}w(e)x_e \\ & \text{限制：} \\ & x(\delta(u))=1:\forall u\in V \\ & x(\gamma(B))\leq\lfloor\frac{|B|}{2}\rfloor:\forall B\in O \\ & x_e\geq0:\forall e\in E \\ \end{aligned}

We then use the primal-dual method to convert the problem into its dual.

Dual problem

\begin{aligned} & \min\sum_{u\in V}z_u+\sum_{B\in O}\left\lfloor\frac{|B|}{2}\right\rfloor z_B \\ & \text{限制：} \\ & z_B\geq0:\forall B\in O \\ & z_e\geq0:\forall e\in E \\ & \text{设} e=(u,v)，\text{这里} \\ & \begin{array}{lll} z_e & = & z_u + z_v - w(e) + \sum_{\substack{B \in O \\ u,v \in \gamma(B)}} z_B \end{array} \end{aligned}

Edges with $x_e=1$ are matching edges, and edges with $x_e=0$ are non-matching edges. As in bipartite graphs, we must satisfy $x_e\in\{0,1\}:\forall e\in E$ . Therefore, in a maximum-weight perfect matching, all matching edges must be equality edges.

Unlike bipartite graphs, general graphs have the additional $z_B$ variables to handle. We now consider when $z_B$ is greater than $0$ .

It is best to make $z_B=0$ whenever possible, but when necessary we still have to make $z_B>0$ . When $x(\gamma(B)) = \left\lfloor \dfrac{|B|}2 \right\rfloor \text{且} x(\delta(B)) = 1$ , it is enough to let $z_B>0$ , because outside this situation, $z_B>0$ is meaningless.

By the complementary slackness conditions, we have the following correspondences:

For a selected edge $e$ , we must have $z_e=0$ .
$x_e>0 \longrightarrow z_e=0,\quad \forall e\in E$
For a selected set B, $z_B>0 \longrightarrow x(\gamma(B))= \left\lfloor \dfrac{|B|}2 \right\rfloor$ . That is, every set with $z_B>0$ , the set $B$ , has selected half as many edges as the size of the set, so this set $B$ is a blossom, and one edge in the blossom is selected for augmentation. We also add the condition $x(\delta(B))=1$ : only when blossom $B$ has one edge extending outward is $z_B>0$ meaningful.
$z_B>0 \longrightarrow x(\gamma(B))=\left\lfloor\frac{|B|}2\right\rfloor, x(\delta(B))=1\quad \forall B\in O$

Using the concept of equality edges together with the blossom algorithm described earlier, repeatedly augment along paths formed by equality edges. Since every edge used for augmentation is an equality edge, the resulting maximum-weight perfect matching still consists entirely of equality edges.

Handling blossoms

When a blossom is encountered, shrink it into an even vertex. Set all vertices in the blossom to even vertices and set its $z_B=0$ .

Because a shrunk blossom is kept until certain conditions are met before being expanded, blossoms cannot be recorded by the previous method.

Unless otherwise specified, vertices mentioned below also include even vertices formed by shrinking blossoms.

Since a blossom can also be shrunk into a vertex and added to the queue, and the number of blossoms is not fixed, we cannot enumerate every vertex as before to check for an augmenting path. Therefore, during breadth-first search (BFS), all unmatched vertices must be put into the queue.

This produces many alternating trees at the same time.

Four steps of the algorithm

This algorithm can be divided into four steps:

GROW (equality edges): construct an alternating tree using equality edges.
AUGMENT: find an augmenting path and augment the matching.
SHRINK: shrink a blossom into one vertex.
EXPAND: expand a blossom.

general-weight-match-1

During AUGMENT, since all unmatched vertices are on different alternating trees, connecting even vertices from two alternating trees means that an augmenting path has been found.

Failure to find an equality-edge augmentation

As in bipartite graphs, it is possible that no equality-edge augmentation can be found. In that case, vertex labeling must be adjusted.

Adjusting VERTEX LABELING

Vertex labeling must continue to maintain the greater-than-or-equal property, existing equality edges must not be changed, and $z_B$ should be kept as small as possible.

Notation for even and odd vertices

Let $u^−$ denote that $u$ is an odd vertex on an alternating tree.
Let $u^+$ denote that $u$ is an even vertex on an alternating tree.
Let $u^\varnothing$ denote that $u$ is not on any alternating tree.
Every $B$ mentioned below is assumed to be a blossom and also represents the vertex formed after shrinking the blossom.
Blossoms may also be odd or even, so notations such as $B^+$ , $B^−$ , and $B^\varnothing$ also apply.

Suppose there are currently r alternating trees $T_i=(U_{t_i},V_{t_i}):1\leq i\leq r$ . Define

\begin{aligned} d1 &= \min(\{z_e : e = (u^+,v^\varnothing)\}) \\ d2 &= \min(\{z_e : e = (u^+,v^+), ~ u^+ \in T_i, ~ v^+ \in T_j, ~ i \neq j\}) / 2 \\ d3 &= \min(\{z_{B^-} : B^- \in O\}) / 2 \end{aligned}

Note that B here is a vertex after shrinking a blossom, so it can have a parity.

Let $d=min(d1,d2,d3)$ , and set

\begin{aligned} z_{u^+} - &= d \\ z_{v^-} + &= d \\ z_{B^+} + &= 2d \\ z_{B^-} - &= 2d \\ \end{aligned}

If $z_B=0(d=d3)$ occurs, the blossom must be expanded (EXPAND) to prevent $z_B<0$ . After expanding the blossom, keep only the alternating path inside it and set vertices in the blossom that are not on the alternating path to unvisited ( $\varnothing$ ).

This creates an additional equality edge, keeps existing equality edges unchanged, maintains $z_e\geq0:\forall e\in E$ , and increases $z_B$ by the minimum necessary amount, so we can continue searching for an augmenting path.

Maximum-weight matching in general graphs

The above finds a maximum-weight perfect matching. To find a maximum-weight matching, vertex labeling needs one additional constraint: for every matched vertex $u$ , $z_u>0$ .

Initially, set every $z_u=max(\{w(e):e\in E\})/2$ .

Vertices whose vertex labeling is $0$ will eventually become unmatched vertices.

Reference code

For convenience, this implementation multiplies edge weights by $2$ when calculating $z_e$ , avoiding floating-point errors.

Storage

constexpr int INF = INT_MAX;
constexpr int MAXN = 400;

struct edge {
  int u, v, w;

  // (u,v) is an edge with weight w
  edge() {}

  edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

int n, n_x;
// There are n vertices, numbered 1 ~ n
// n_x is the current number of vertices plus blossoms; blossom vertices are numbered n+1 through n_x
edge g[MAXN * 2 + 1][MAXN * 2 + 1];
// The graph is stored as an adjacency matrix; since there are at most n-1 blossoms, its size is MAXN*
vector<int> flower[MAXN * 2 + 1];
// flower[b] records the vertices contained in blossom b
// We record the vertices in a blossom by recording only its outermost nested blossoms

Here is an example of nested blossoms.

general-weight-match-2

Here $\{ 6, 5, 8\} \in b1,\{ b1, 4, 3, 2, 11, 10, 9\} \in b2$ . They are stored as:

flower[b2] = {b1, 4, 3, 2, 11, 10, 9} 
flower[b1] = {6, 5, 8}

general-weight-match-3

flower[b2] = {9, b1, 4, 3, 2, 11, 10} 
flower[b1] = {5, 8, 6}

int lab[MAXN * 2 + 1];
// lab[u] records z_u; lab[b] records z_B
int match[MAXN * 2 + 1], slack[MAXN * 2 + 1], st[MAXN * 2 + 1],
    pa[MAXN * 2 + 1];
// match[x]=y means that (x,y) is a matching edge; x and y may be blossoms
// slack[x]=u means that z(x,u) is the minimum among all edges adjacent to x
// The blossom containing node x is b. If x=b and b<=n, then x
// is an ordinary node (not belonging to any blossom). In the alternating tree, node v's parent is u
int flower_from[MAXN * 2 + 1][MAXN + 1], S[MAXN * 2 + 1], vis[MAXN * 2 + 1];
/*
flower_from[b][x]=xs means that the largest sub-blossom of b containing x is xs
x is a vertex in b, and xs is a blossom or vertex in b; x=xs or x is one of the vertices in xs
*/
// S[u]={-1:unvisited, 0:even, 1:odd}
// vis is used only to check whether a vertex has been visited when finding the lca
queue<int> q;
// Queue used by BFS to find augmenting paths

general-weight-match-4

flower_from[b2][6] = b1 
flower_from[b2][5] = b1 
flower_from[b2][9] = 9 
flower_from[b1][6] = 6 
and so on

int e_delta(const edge &e) {
  // Calculate ze; for convenience, first multiply all edge weights by two
  // Calculating e_delta directly inside a blossom causes errors
  return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;
}

void update_slack(int u, int x) {
  // Update the value of slack[x] using u
  if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) {
    slack[x] = u;
  }
}

void set_slack(int x) {
  // Calculate slack[x]; slack[x]=0 means x is a node in the alternating tree
  slack[x] = 0;
  for (int u = 1; u <= n; ++u) {
    if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) {
      update_slack(u, x);
    }
  }
}

void q_push(int x) {
  // Add x to the queue; we assume that a blossom cannot be pushed directly
  if (x <= n)
    q.push(x);
  else {
    // To push a blossom, all original vertices inside it must be added to the queue
    for (size_t i = 0; i < flower[x].size(); i++) {
      q_push(flower[x][i]);
    }
  }
}

void set_st(int x, int b) {
  // Set the blossom containing x to b
  st[x] = b;
  if (x > n) {
    // If x is also a blossom, set the blossom containing every vertex inside x to b
    for (size_t i = 0; i < flower[x].size(); ++i) {
      set_st(flower[x][i], b);
    }
  }
}

int get_pr(int b, int xr) {
  // xr is a vertex in flower[b]; the return value pr is its position
  // For convenience, we make flower[b][0]~flower[b][pr] the alternating path in the blossom
  int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
  if (pr % 2 == 1) {
    // Check the position inside the blossom. If flower[b][0]~flower[b][pr] is not an alternating path,
    // reverse the whole blossom and recalculate pr
    // Make flower[b][0]~flower[b][pr] the alternating path
    reverse(flower[b].begin() + 1, flower[b].end());
    return (int)flower[b].size() - pr;
  } else
    return pr;
}

general-weight-match-5

If get_pr(b2,11) is used, flower[b2] becomes {9,10,11,2,3,4,b1}, and 2 is returned.

If get_pr(b2,2) is used, flower[b2] becomes {9,b1,4,3,2,11,10}, and 4 is returned.

void set_match(int u, int v) {
  // Set u and v as a matching edge; u and v may be blossoms
  match[u] = g[u][v].v;
  if (u > n) {
    // If u is a blossom
    edge e = g[u][v];
    int xr = flower_from[u][e.u];  // Find which blossom in flower[u] contains e.u
    int pr = get_pr(u, xr);  // Find the position of xr and make 0~pr the alternating path in the blossom
    for (int i = 0; i < pr; ++i) {  // Reverse matching and non-matching edges on the alternating path in the blossom
      set_match(flower[u][i], flower[u][i ^ 1]);
    }
    set_match(xr, v);  // Set (xr,v) as a matching edge
    rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end());
    // Finally set pr as the blossom base. Since flower[u][0] is the blossom base,
    // rotate flower[u][pr] to the front
  }
}

void augment(int u, int v) {
  // Augment u and all its ancestors, and set (u,v) as a matching edge
  for (;;) {
    int xnv = st[match[u]];
    set_match(u, v);
    if (!xnv) return;
    set_match(xnv, st[pa[xnv]]);
    u = st[pa[xnv]];
    v = xnv;
  }
}

int get_lca(int u, int v) {
  // Find the lca of u and v in the alternating tree
  static int t = 0;
  for (++t; u || v; swap(u, v)) {
    if (u == 0) continue;
    if (vis[u] == t) return u;
    vis[u] = t;  // This avoids having to clear the vis array
    u = st[match[u]];
    if (u) u = st[pa[u]];
  }
  return 0;
}

Add an odd blossom

void add_blossom(int u, int lca, int v) {
  // Shrink the blossom u,v,lca into one vertex b
  // The lca of u and v in the alternating tree is the blossom base
  int b = n + 1;
  while (b <= n_x && st[b]) ++b;
  if (b > n_x) ++n_x;
  // Find the number of an unused blossom
  lab[b] = 0;             // Set zB=0
  S[b] = 0;               // The whole blossom is an even vertex
  match[b] = match[lca];  // Set the matching edge of the blossom to the matching edge of its base
  flower[b].clear();
  flower[b].push_back(lca);
  for (int x = u, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  reverse(flower[b].begin() + 1, flower[b].end());
  for (int x = v, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  // Add all vertices in b to flower[b] cyclically, with the blossom base first
  set_st(b, b);  // Set the blossom containing every element in the whole blossom to b
  for (int x = 1; x <= n_x; ++x) {
    g[b][x].w = 0;
    g[x][b].w = 0;
  }
  for (int x = 1; x <= n; ++x) {
    flower_from[b][x] = 0;
  }
  for (size_t i = 0; i < flower[b].size(); ++i) {
    int xs = flower[b][i];
    for (int x = 1; x <= n_x; ++x) {
      // Set the edge adjacent to b and x to the adjacent edge inside b with minimum e_delta
      if (g[b][x].w == 0 || e_delta(g[xs][x]) < e_delta(g[b][x])) {
        g[b][x] = g[xs][x];
        g[x][b] = g[x][xs];
      }
    }
    for (int x = 1; x <= n; ++x) {
      if (flower_from[xs][x]) {
        // If the vertex xs in b contains x,
        // then flower_from[b][x] is xs
        flower_from[b][x] = xs;
      }
    }
  }
  set_slack(b);
  // Finally, b's slack value must be set
}

Expand a blossom

void expand_blossom(int b) {
  // When b is an odd blossom and zB=0, b must be expanded
  // Only b is expanded, so if b contains other blossoms,
  // they do not need to be expanded
  for (size_t i = 0; i < flower[b].size(); ++i) {
    set_st(flower[b][i], flower[b][i]);
    // First set the blossom containing each element in flower[b] to itself
  }
  int xr = flower_from[b][g[b][pa[b]].u];
  // xr is the blossom in flower[b] containing b's parent on the alternating path
  int pr = get_pr(b, xr);  // Find the position of xr and make 0~pr the alternating path in the blossom
  for (int i = 0; i < pr; i += 2) {
    // Expand the alternating path into the alternating tree
    // and put the even vertices on the alternating path into the queue
    int xs = flower[b][i];
    int xns = flower[b][i + 1];
    pa[xs] = g[xns][xs].u;
    S[xs] = 1;
    S[xns] = 0;
    slack[xs] = 0;
    set_slack(xns);
    q_push(xns);
  }
  S[xr] = 1;  // xr is now an odd vertex or odd blossom
  pa[xr] = pa[b];
  for (size_t i = pr + 1; i < flower[b].size(); ++i) {
    // Set all vertices in the blossom that are no longer on the alternating path to unvisited
    int xs = flower[b][i];
    S[xs] = -1;
    set_slack(xs);
  }
  st[b] = 0;
}

Try to augment along an equality edge

bool on_found_edge(const edge &e) {
  // An equality edge e was found during BFS
  // It must be handled as follows
  // Here u is necessarily an even vertex
  int u = st[e.u], v = st[e.v];
  if (S[v] == -1) {
    // v is an unvisited vertex
    pa[v] = e.u;
    S[v] = 1;
    int nu = st[match[v]];
    slack[v] = 0;
    slack[nu] = 0;
    S[nu] = 0;
    q_push(nu);
  } else if (S[v] == 0) {
    // v is an even vertex
    int lca = get_lca(u, v);
    if (!lca) {  // lca=0 means u and v are in different alternating trees, so there is an augmenting path
      augment(u, v);
      augment(v, u);
      return true;  // An augmenting path was found
    } else
      add_blossom(u, lca, v);
    // Otherwise, u and v form a blossom in the same tree, so shrink it
  }
  return false;
}

Augmentation

bool matching() {
  memset(S + 1, -1, sizeof(int) * n_x);
  memset(slack + 1, 0, sizeof(int) * n_x);
  q = queue<int>();  // Clear the queue
  for (int x = 1; x <= n_x; ++x) {
    if (st[x] == x && !match[x]) {
      // Add all unmatched vertices to the queue and set them as even vertices
      pa[x] = 0;
      S[x] = 0;
      q_push(x);
    }
  }
  if (q.empty()) return false;  // All vertices are matched
  for (;;) {
    while (q.size()) {
      // BFS
      int u = q.front();
      q.pop();
      if (S[st[u]] == 1) continue;
      for (int v = 1; v <= n; ++v) {
        if (g[u][v].w > 0 && st[u] != st[v]) {
          if (e_delta(g[u][v]) == 0) {
            if (on_found_edge(g[u][v])) return true;
          } else
            update_slack(u, st[v]);
        }
      }
    }
    // Modify lab values
    int d = INF;
    for (int u = 1; u <= n; ++u) {
      // This prevents lab<0 from occurring
      // Terminate as soon as any lab[u]=0
      if (S[st[u]] == 0) d = min(d, lab[u]);
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
    }
    for (int x = 1; x <= n_x; ++x)
      if (st[x] == x && slack[x]) {
        if (S[x] == -1)
          d = min(d, e_delta(g[slack[x]][x]));
        else if (S[x] == 0)
          d = min(d, e_delta(g[slack[x]][x]) / 2);
      }
    for (int u = 1; u <= n; ++u) {
      if (S[st[u]] == 0) {
        if (lab[u] == d) return false;
        // If lab[u]=0, terminate directly
        lab[u] -= d;
      } else if (S[st[u]] == 1)
        lab[u] += d;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b) {
        if (S[st[b]] == 0)
          lab[b] += d * 2;
        else if (S[st[b]] == 1)
          lab[b] -= d * 2;
      }
    }
    q = queue<int>();  // Clear the queue
    for (int x = 1; x <= n_x; ++x) {
      // Check whether an augmenting path has been created
      if (st[x] == x && slack[x] && st[slack[x]] != x &&
          e_delta(g[slack[x]][x]) == 0)
        if (on_found_edge(g[slack[x]][x])) return true;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      // EXPAND: expand every odd blossom with lab[b]=0
      if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b);
    }
  }
  return false;
}

Main function

pair<long long, int> weight_blossom() {
  // Main function; initialize first
  memset(match + 1, 0, sizeof(int) * n);
  n_x = n;  // There are no blossoms initially
  int n_matches = 0;
  long long tot_weight = 0;
  for (int u = 0; u <= n; ++u) {
    // Initially set the blossom containing each vertex to itself
    st[u] = u;
    flower[u].clear();
  }
  int w_max = 0;
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) {
      // When u is a vertex, the only vertex it contains is itself
      flower_from[u][v] = (u == v ? u : 0);
      w_max = max(w_max, g[u][v].w);
      // Find the maximum edge weight
    }
  for (int u = 1; u <= n; ++u) lab[u] = w_max;
  // Set every lab to the maximum edge weight
  // Since this implementation uses doubled edge weights to calculate ze, division by two is unnecessary
  while (matching()) ++n_matches;
  for (int u = 1; u <= n; ++u)
    if (match[u] && match[u] < u) tot_weight += g[u][match[u]].w;
  return make_pair(tot_weight, n_matches);
}

Initialization

This is important; it must be initialized before use.

void init_weight_graph() {
  // Initialize before inputting edges into the graph
  // Since this is a maximum-weight matching, set nonexistent edges to 0
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) g[u][v] = edge(u, v, 0);
}

Complexity analysis

Each blossom is shrunk or expanded at most once during one BFS. Each shrinking or expansion takes $O(|V|)$ time. There are at most $O(|V|)$ blossoms in total, so blossom handling costs $O(|V|^2)$ time. BFS costs $O(|V| + |E|)$ . Therefore, finding an augmenting path costs $O(|V| + |E|) + O(|V|^2) = O(|V|^2)$ time.

At most $|V|$ BFS runs are performed. Thus, the total time complexity is $O(|V|^3)$ .

Exercises

UOJ #81. Maximum-weight matching in general graphs

Maximum-weight matching in general graphs

Prerequisites

Blossom

Vertex labeling and equality edges

Linear programming for maximum-weight perfect matching in general graphs

Definition

Dual problem

Handling blossoms

Four steps of the algorithm

Failure to find an equality-edge augmentation

Adjusting VERTEX LABELING

Maximum-weight matching in general graphs

Reference code

Complexity analysis

Exercises

References