Graph Partitioning — Bisection

Split the vertices into two equal-size sets so that the number of edges crossing the partition is minimized.

Intuition

The picture

Color every vertex either Red or Blue, with as close to half-half as possible. An edge whose two endpoints have different colors is a "cut" edge — we want as few of those as possible.

Use cases: chip layout (minimize wires crossing zones), parallel computing (assign work to processors so they exchange minimal data), community detection.

External cost, internal cost, and the gain of a swap

For each vertex a:

E(a) = number of neighbors in the other set (external)
I(a) = number of neighbors in the same set (internal)
Diff(a) = E(a) − I(a) — if you move a to the other set, the change in cut edges = −Diff(a) (it adds I(a) new cuts and removes E(a) old ones)

Gain of swapping two vertices a and b (one from each set):

Gain(a, b) = Diff(a) + Diff(b) − 2·c(a,b)

where c(a,b) = 1 if there is an edge between a and b, else 0.

The −2 c(a,b) corrects for the fact that the edge a-b is "double-counted":
if it exists, before the swap it was a cut edge (counted in E(a) and E(b));
after the swap, both vertices flip sides, so the edge a-b becomes a non-cut
internal edge in the new layout.

Positive Gain → fewer cut edges after the swap (good). Negative Gain → more cuts (bad).

Greedy + random algorithm (from your course)

Compute E and I for every vertex.
S_old ← initial random partition;  C_old ← cut(S_old)
S_best ← S_old;  C_best ← C_old
Prob ← 0.8                         // probability of accepting a bad swap
do {
    for counter = 1..length:        // length = 100 per outer iter.
        v_i ← random vertex in Set 1
        v_j ← random vertex in Set 2
        swap them tentatively; compute C_new
        Diff = C_new − C_old
        if Diff < 0:                // fewer cuts — accept
            S_old ← S_new; C_old ← C_new
            if C_new < C_best:
                S_best ← S_new; C_best ← C_new
        else:                       // more cuts — accept with prob
            if random(0,1) < Prob:
                S_old ← S_new; C_old ← C_new
            else: revert
    Prob ← 0.9 * Prob               // cool down
} while (Prob > 0.001)
return S_best

Notice: this is essentially simulated annealing with Prob playing the role of temperature.

Worked example (5-vertex graph)

Edges: 1–2, 1–5, 2–5, 3–4, 1–3 (5 edges). Initial: Set1 = {1, 3}, Set2 = {2, 4, 5}, cuts = 3.

Iter  Swap     New sets                 Cuts   Verdict
1     1↔2      {2,3}/{1,4,5}             4      bad; rnd 0.6 < 0.8 → accept
2     3↔4      {2,4}/{1,3,5}             3      same (Diff=0 not < 0) → accept-no-improvement
2     3↔4      {2,4}/{1,3,5}             3      good move
3     4↔5      {2,5}/{1,3,4}             2      better → accept; new best = 2
4     5↔1      {1,2}/{3,4,5}             3      bad; rnd 0.5 < 0.8 → accept
5     1↔3      {2,3}/{1,4,5}             5      bad; rnd 0.7 < 0.8 → accept
6     2↔4      {3,4}/{1,2,5}             1      better → accept; new best = 1   ✓

Interactive demo

Generate a random graph, run the algorithm and watch cuts decrease over time.

Cuts: -

Exam tips

Frequently asked

"Compute E(v), I(v), Diff(v) for each vertex" — count carefully; mark which neighbors are in same set vs other.
"Compute Gain(a, b)" — use Diff(a) + Diff(b) − 2·c(a,b).
"Show one iteration of greedy+random" — pick two vertices, compute change in cuts, decide accept/reject (deterministic if improving; probabilistic if not).
"Why decrease Prob?" — early on we allow exploration; later we want convergence.