Checking if a simplified solution matches the real answer is hard even for simple graphs.

The Maximum Cut problem asks you to split a network into two groups to maximize the connections cut between them. Solving this directly is extremely difficult. Instead, computers often use an approximation called a Semidefinite Programming relaxation. Sometimes this shortcut is exact, giving the true best cut and a rank-1 geometric answer. Delorme and Poljak showed that spotting exactness is hard, but only by using huge, exponentially growing edge weights. This left unweighted networks unaddressed. The researchers resolved this puzzle. They proved that checking exactness is strongly NP-hardNP-hardA class of computational problems where no known efficient solution exists for all cases. for weighted networks using manageable, polynomially bounded weights. They also proved it remains hard for simple, unweighted networks by embedding a logic puzzle into overlapping geometric cliques.

Why it matters

This affects computer scientists and engineers who rely on optimization methods. If verifying when a simplification is exact is inherently hard, it impacts how we design and trust these algorithms in practice.

Questions answered