Graph Partitioning

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.

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">{{hint}}</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">{{btn_best}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

"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.

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.