Introduction

Picture a network: dots (call them nodes) connected by lines (call them edges). It could be servers wired together, friends on a social app, or transistors on a chip. Now you have to split it in two, putting half the nodes on each side.

There is a catch. Every edge that ends up with one endpoint on the left and the other on the right gets cut — and cuts are expensive. Two servers that must keep talking across the divide eat network bandwidth; two chip components on opposite sides of a board need a long, slow wire. So your goal is to split the nodes into two balanced halves while cutting as few edges as possible.

It sounds like something you could eyeball. For five nodes, sure. But as the network grows, the number of ways to split it explodes, and finding the truly minimal cut becomes one of the genuinely hard problems in computer science.

Make the Cut

Below is a small graph. Each node sits on the left or right side; click a node to flip it across. Edges that cross the divide turn red — those are the ones you cut. The counter shows how many edges you're cutting and whether the two sides are balanced.

<p class="hint">Click a node to flip it to the other side. Edges that cross the divide turn <b>red</b> &mdash; those are the ones you <b>cut</b>. Keep the two sides balanced while making the cut as small as you can.</p>
<svg id="graph" viewBox="0 0 360 220" class="graph"></svg>
<div class="status" id="status"></div>
<div class="btns">
  <button id="best" type="button">Best split</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.graph { width: 100%; height: auto; background: #f4f7fa; border-radius: 10px;
         border: 1px solid #dde5ec; display: block; touch-action: manipulation; }
.divider { stroke: #9aa7b4; stroke-width: 1.5; stroke-dasharray: 5 5; }
.edge { stroke: #9fb0bf; stroke-width: 2.5; }
.edge.cut { stroke: #e63946; stroke-width: 3; }
.node { cursor: pointer; }
.node circle { stroke: #fff; stroke-width: 2; transition: fill .12s; }
.node.left circle  { fill: #1d3557; }
.node.right circle { fill: #2a9d8f; }
.node text { fill: #fff; font: 700 13px ui-monospace, monospace;
             text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.label { font: 700 11px system-ui, sans-serif; text-anchor: middle; fill: #5a6b7b; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status .ok  { color: #0a7d33; }
.status .bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Balanced graph partitioning ("minimum bisection"): split the nodes into two
    // equal halves while cutting as few edges as possible. Counting the cut of one
    // split is instant; finding the optimal balanced split is NP-hard, so "Best
    // split" here brute-forces every balanced division (fine for 6 nodes, hopeless
    // as the graph grows since the number of splits roughly doubles per node).
const NS = 'http://www.w3.org/2000/svg';
// 6 nodes laid out in two loose clusters; side = 0 (left) or 1 (right).
const NODES = [
  { id: 'A', x: 90,  y: 55  },
  { id: 'B', x: 70,  y: 130 },
  { id: 'C', x: 130, y: 95  },
  { id: 'D', x: 230, y: 95  },
  { id: 'E', x: 290, y: 55  },
  { id: 'F', x: 270, y: 130 },
];
// Two tight triangles (A-B-C, D-E-F) joined by a single bridge C-D.
const EDGES = [ ['A','B'],['A','C'],['B','C'],['C','D'],['D','E'],['D','F'],['E','F'] ];
const idx = {}; NODES.forEach((n,i)=>idx[n.id]=i);
let side = [0,0,0,1,1,1]; // initial split: ABC | DEF (the natural minimum)

function cutCount(s){ let c=0; for(const [u,v] of EDGES) if(s[idx[u]]!==s[idx[v]]) c++; return c; }
function balance(s){ const l=s.filter(x=>x===0).length; return { l, r:s.length-l }; }

function render(){
  const svg=document.getElementById('graph'); svg.innerHTML='';
  const div=document.createElementNS(NS,'line');
  div.setAttribute('x1',180); div.setAttribute('y1',8);
  div.setAttribute('x2',180); div.setAttribute('y2',212); div.setAttribute('class','divider');
  svg.appendChild(div);
  const lab=(x,t)=>{ const e=document.createElementNS(NS,'text'); e.setAttribute('x',x);
    e.setAttribute('y',204); e.setAttribute('class','label'); e.textContent=t; svg.appendChild(e); };
  lab(60,'LEFT'); lab(300,'RIGHT');
  // edges first so nodes draw on top
  for(const [u,v] of EDGES){ const a=NODES[idx[u]], b=NODES[idx[v]];
    const ln=document.createElementNS(NS,'line');
    ln.setAttribute('x1',a.x); ln.setAttribute('y1',a.y);
    ln.setAttribute('x2',b.x); ln.setAttribute('y2',b.y);
    ln.setAttribute('class','edge'+(side[idx[u]]!==side[idx[v]]?' cut':''));
    svg.appendChild(ln); }
  NODES.forEach((n,i)=>{ const g=document.createElementNS(NS,'g');
    g.setAttribute('class','node '+(side[i]===0?'left':'right'));
    const c=document.createElementNS(NS,'circle');
    c.setAttribute('cx',n.x); c.setAttribute('cy',n.y); c.setAttribute('r',18);
    const t=document.createElementNS(NS,'text');
    t.setAttribute('x',n.x); t.setAttribute('y',n.y); t.textContent=n.id;
    g.appendChild(c); g.appendChild(t);
    g.addEventListener('click',()=>{ side[i]=1-side[i]; render(); });
    svg.appendChild(g); });
  status();
}

function status(){
  const b=balance(side), cut=cutCount(side);
  const ok = b.l===b.r;
  const balTxt = ok
    ? fmt('<span class="ok">balanced (%l% vs %r%)</span>', { l: b.l, r: b.r })
    : fmt('<span class="bad">unbalanced (%l% vs %r%)</span>', { l: b.l, r: b.r });
  document.getElementById('status').innerHTML =
    fmt('Cut size: <b>%cut%</b> %v% &middot; %balTxt%', { cut: cut, v: cut===1?'edge':'edges', balTxt: balTxt });
}

// Brute force every balanced split (exactly n/2 on each side) and keep the min cut.
function best(){
  const n=NODES.length, half=n/2; let bestCut=Infinity, bestS=null, checked=0;
  for(let mask=0; mask<(1<<n); mask++){
    let ones=0; for(let i=0;i<n;i++) if(mask&(1<<i)) ones++;
    if(ones!==half) continue;                 // only balanced splits
    checked++;
    const s=[]; for(let i=0;i<n;i++) s.push((mask>>i)&1);
    const c=cutCount(s);
    if(c<bestCut){ bestCut=c; bestS=s.slice(); }
  }
  side=bestS; render();
  document.getElementById('status').innerHTML +=
    " " + fmt('&mdash; <span class="ok">optimum = %bestCut% (checked %checked% balanced splits)</span>', { bestCut: bestCut, checked: checked });
  console.log('Best balanced cut =', bestCut, 'over', checked, 'balanced splits');
}
document.getElementById('best').addEventListener('click',best);
document.getElementById('reset').addEventListener('click',()=>{ side=[0,1,0,1,0,1]; render(); });
render();
Result
Console

Try to get the smallest possible cut while keeping the sides even. Notice the tension: moving a node to balance the count often breaks more edges. Press Best split and the demo brute-forces every balanced division to reveal the true minimum — for this little graph it's quick, but the number of splits it must check doubles with every node you add.

The Real Complexity

Why is dividing a graph so hard? The trouble is that local choices have global consequences.

  • Checking a proposed split is instant: walk every edge and count the ones whose endpoints landed on different sides.
  • Brute force tries every way to put half the nodes on each side. For 2n nodes that is a colossal number of balanced splits, doubling roughly with each extra node — hopeless beyond a few dozen.
  • It's NP-hard. The balanced version, called minimum bisection, is NP-hard: there is no known algorithm that always finds the optimal balanced cut in time that scales reasonably with the graph. Even approximating it well is notoriously difficult.
  • The unbalanced cousin is easy. If you drop the balance requirement, plain minimum cut can be solved efficiently. It is the demand for equal sides that tips the problem into intractability — the same kind of jump you see going from 2-SAT to 3-SAT.

In practice, engineers don't chase the perfect cut. Heuristics like Kernighan-Lin (1970) and multilevel solvers (METIS) swap nodes back and forth to shrink the cut, settling for excellent-but-not-provably-optimal splits — exactly the bargain forced on us by problems near P vs NP.

Where It Matters

"Divide the work evenly while minimizing the talk between parts" is one of the most valuable shapes a problem can take, and graph partitioning is its purest form:

  • Parallel computing: to split a giant simulation across thousands of processors, you partition the data so each core gets an equal load and the cross-core communication (the cut) stays minimal.
  • Chip design (VLSI): placing components so that few wires cross between regions of a chip is a balanced-partition problem; shorter cuts mean faster, cooler hardware.
  • Scientific simulation: weather, fluids and crash models are meshes that must be carved into balanced chunks for distributed solvers.
  • Image segmentation and clustering: "normalized cut" partitions an image graph into coherent regions, and the same idea finds communities in social networks.

Master why a clean balanced cut is hard and you've met the core obstacle behind making big computations run in parallel at all.

Conclusion

Graph partitioning is one of those problems that hides its difficulty behind an everyday picture: just draw a line and split the dots. Yet demanding balanced halves with the fewest cut edges turns that line into a minimum-bisection problem that is NP-hard — easy to check, brutal to solve perfectly.

So when a supercomputer divides a simulation, or a chip designer lays out a board, nobody waits for the optimal cut. They run clever heuristics, accept a split that is excellent rather than perfect, and move on. The next time you slice a network in two, remember: you're playing with a piece of P vs NP, and "good enough" is often the wisest answer.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graph-partitioning/Content licensed under CC BY-NC 4.0.