Max-Cut is NP-hard. Given a graph with weighted edges, partition the vertices into two sets to maximize the total weight of edges crossing the partition. For arbitrary weights on arbitrary graphs, no polynomial-time algorithm finds the optimal solution unless P equals NP. The problem is generic, the hardness is generic, and the best approximation algorithms exploit semidefinite programming to get within a factor of about 0.878.
Maric (arXiv:2603.08876, March 2026) adds a single constraint to the weights and the hardness evaporates. Assign each edge a weight that decreases geometrically with its index: the i-th edge gets weight r^(N−i), where N is the total number of edges and r is a parameter between 0 and 1. On a complete graph, this creates a strict hierarchy — some edges matter exponentially more than others. The question is no longer which cut is optimal, but how the optimal cut changes as r varies.
The answer is a clean phase diagram. For each value of r, the optimal cut is an “isolated cut” — a partition of the form {1,...,k} versus {k+1,...,n}, where the vertices are ordered by their edge weights. As r increases from 0 toward 1, the optimal partition shifts from separating one vertex to separating two, then three, and so on. The transitions between regimes are governed by threshold polynomials whose roots are strictly decreasing. The phase diagram is monotone, hierarchical, and algebraically tractable.
The conjecture — verified computationally up to 100 vertices — is that for n ≥ 7, isolated cuts are globally optimal among all 2^(n−1) possible partitions. If true, the combinatorial explosion collapses to a linear search: instead of evaluating exponentially many cuts, you evaluate n−1 isolated cuts and pick the best. The geometric weighting doesn't just simplify the problem; it selects a structured solution space where the optimal answer always lives.
The mechanism is worth stating plainly. The geometric weights break the symmetry that makes Max-Cut hard. In the unweighted problem, every edge is interchangeable, so every partition must be considered. With geometric weights, the exponential hierarchy among edges means that the heaviest edges dominate, and the optimal cut must respect their arrangement. The solution is forced to align with the weight ordering, and the weight ordering is simple.
NP-hardness describes the worst case over all instances. The geometric weighting eliminates the worst cases by imposing structure that the hardness proof relies on being absent. The problem isn't solved in the general sense — it's restricted to a regime where the hardness doesn't apply. The intractability was in the disorder of the weights, and the geometric assignment removes exactly that disorder.
Maric, "Hierarchical threshold structure in Max-Cut with geometric edge weights," arXiv:2603.08876 (March 2026).