We tackle the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and show that low-rank structure in the objective matrix can be exploited to build algorithms that are faster and more parallelizable than classical semidefinite programming (SDP) relaxations. We propose algorithms for maximizing these quadratic forms over a domain of size \(K\) that enumerate and evaluate a set of \(\mathcal{O}(n^{2r-1})\) candidate solutions, where \(n\) is the number of graph nodes and \(r\) is the rank of a low-rank approximation of the objective. When \(K=3\) and the objective is exactly low-rank, our candidate set is guaranteed to contain the exact maximizer. For approximately low-rank objectives, we prove multiplicative approximation guarantees that degrade gracefully with the perturbation magnitude. Experimentally, our Rank-1 algorithm achieves up to a 74× speedup over heuristic methods while preserving solution quality on structured graph instances, and scales to graphs with tens of thousands of nodes.

Partitioning a network into groups to maximize cross-group connections arises everywhere: circuit layout, social network analysis, clustering, and even quantum computing benchmarks. Max-3-Cut—splitting a graph's vertices into three sets to maximize cut edges—is NP-hard, and the best-known polynomial-time approximation ratio of 0.836 comes from semidefinite programming (SDP). SDP solvers are expensive (at least \(\mathcal{O}(n^{3.5})\)) and more importantly hard to parallelize, while heuristic methods like genetic algorithms lack provable guarantees.

Our key insight is simple: many real-world graphs have Laplacians whose spectra decay rapidly, meaning most of the "cut information" lives in a few top eigenvalues. By projecting the problem onto a low-rank approximation of the Laplacian, we convert Max-3-Cut into an exact discrete quadratic maximization that can be solved in polynomial time for fixed rank. This yields a family of algorithms—Rank-1, Rank-2, Rank-3—that trade off between speed and solution quality, are embarrassingly parallel, and come with provable approximation guarantees for the full-rank case.

The Max-\(K\)-Cut problem has a rich algorithmic landscape:

• SDP relaxations: Goemans–Williamson (1995) introduced the celebrated 0.878-approximation for Max-2-Cut. Frieze–Jerrum (1997) and Goemans–Williamson (2001) extended this to Max-3-Cut, achieving an optimal ratio of 0.836 under the Unique Games Conjecture.
• Heuristic methods: Genetic algorithms, memetic search, and breakout local search have been applied to Max-3-Cut on large benchmarks, often achieving near-optimal cuts but without provable guarantees.
• Learning-based approaches: GNN-based and reinforcement-learning methods have shown promise on combinatorial optimization but remain data-hungry black boxes.
• Low-rank approaches for Max-Cut: The Burer–Monteiro factorization enforces low rank on the SDP solution, while low-threshold-rank methods study graphs whose adjacency matrices have few large eigenvalues. Neither exploits low rank in the Laplacian itself.

Our work is the first to exploit low-rank structure in the graph Laplacian directly, yielding exact polynomial-time algorithms for fixed rank that extend to any alphabet size \(K\).

Given a graph with Laplacian \(\mathbf{Q}^{\star} \in \mathbb{C}^{n \times n}\), we seek the assignment vector \(\mathbf{z} \in \mathcal{A}_K^n\) that maximizes the complex quadratic form:

where \(\mathcal{A}_K = \{ e^{2\pi i k / K} : k = 0, 1, \ldots, K{-}1 \}\) are the \(K\)-th roots of unity. For \(K = 3\), this is exactly the Max-3-Cut problem: two nodes in the same partition contribute 0 to the objective, while nodes in different partitions contribute \(\frac{3}{2} w_{ij}\). When \(\mathbf{Q}^{\star}\) has rank \(r \ll n\), we decompose it as \(\mathbf{Q}^{\star} = \mathbf{V}\mathbf{V}^{\dagger}\) and work directly with the \(n \times r\) factor \(\mathbf{V}\).

The core idea is to reformulate the discrete maximization as a double optimization over an auxiliary angular parameter that scans a continuous space. As this parameter sweeps through a hypercube, the optimal assignment for each node changes only at specific decision boundaries—hypersurfaces in the parameter space. These hypersurfaces partition the search space into cells, each corresponding to a distinct candidate cut. Instead of searching over all \(K^n\) possible assignments, we only need to visit the vertices of this partition.

Left: Three decision-boundary hypersurfaces in the auxiliary parameter space \((\varphi_1, \varphi_2, \varphi_3)\) for rank \(r=2\). Their intersection defines a vertex of the cell partition. Right: The same arrangement with seven labeled regions; each region maps to a distinct candidate assignment vector.

Our algorithms work in three stages:

• Rank-1: For a rank-1 Laplacian approximation \(\mathbf{Q}_1 = \lambda \mathbf{q}\mathbf{q}^{\dagger}\), the problem reduces to maximizing \(|\mathbf{z}^{\dagger}\mathbf{q}|^2\). We introduce a single rotation angle \(\varphi\) and scan \(n+1\) boundary points to find the optimal assignment in \(\mathcal{O}(n^2)\) time.
• Rank-r: For rank \(r\), we introduce \(2r{-}1\) auxiliary angles. The search space becomes a \((2r{-}1)\)-dimensional hypercube partitioned by \(n B_K\) hypersurfaces (where \(B_K = K\) for odd \(K\)). Each vertex is found by solving a small \((2r{-}1) \times 2r\) linear system. The algorithm enumerates \(\mathcal{O}(r \cdot n^{2r-1})\) candidates and runs in \(\mathcal{O}(r \cdot n^{2r+1})\) time.
• Approximate (full-rank graphs): For a general graph, we compute the top-\(r\) eigendecomposition of the Laplacian, form the rank-\(r\) approximation, and run the exact solver on it. This gives an approximate solution with provable quality bounds.

Crucially, the candidate enumeration and evaluation steps are embarrassingly parallel: each vertex can be processed independently, making the algorithm well-suited for GPU acceleration and distributed computing.

We establish three types of guarantees:

• Exactness for low-rank objectives: When the objective matrix has rank \(r\), our rank-\(r\) algorithm is guaranteed to find the global maximizer (Theorem 2).
• Additive bound under perturbation: When the observed matrix is \(\mathbf{Q} = \mathbf{Q}^{\star} + \mathbf{H}\), our rank-\(r\) approximation satisfies:

where \(\lambda_j^{\star}\) are the eigenvalues of \(\mathbf{Q}^{\star}\) and \(\delta^{\star}\) is the eigengap. The first term is the price of truncating to rank \(r\); the second captures the effect of noise.

• Multiplicative bound: Under an incoherence condition on the leading eigenvector, we obtain:

This shows that when the noise is small relative to the spectral gap, the low-rank algorithm recovers a near-optimal cut.

We evaluate our algorithms on synthetic random graphs and the GSet benchmark, comparing against Frieze–Jerrum (SDP), Greedy, and Genetic baselines.

Small-Scale Results

Empirical approximation ratios on 5-regular graphs (left) and Erdős–Rényi graphs with \(n=100\) (right). Our Rank-3 algorithm achieves the highest average ratio on small graphs; Rank-2 matches or exceeds Greedy across all densities.

• On 5-regular graphs with 20–50 nodes, our Rank-3 algorithm achieves the highest average empirical approximation ratio, while Rank-2 effectively matches Greedy.
• On Erdős–Rényi graphs with \(n=100\), Rank-2 performance improves with graph density, converging to Greedy quality at high edge probabilities and outperforming Frieze–Jerrum at all densities.
• Rank-1 is fastest but can underperform on sparse, unstructured graphs where a single eigenvector does not capture the cut structure.

Large-Scale GSet Benchmark

The table below compares our Rank-1 algorithm against Greedy and MOH (a state-of-the-art heuristic) on selected GSet instances. Runtimes are in seconds.

Bold rows highlight instances where Rank-1 matches the theoretical optimum. MOH runtimes are not compared due to hardware differences. Greedy times out at 30 minutes on graphs with \(n \geq 10{,}000\).

• On unweighted toroidal graphs (G48, G49), Rank-1 finds the theoretically optimal cut value of 6000, matching MOH and slightly outperforming Greedy, while running 57–74× faster.
• On the largest instances (G67, G81), Greedy fails to converge within 30 minutes; Rank-1 finishes in 76 and 352 seconds, respectively.
• On less structured graphs (Erdős–Rényi, skew), Rank-1 trades some solution quality for dramatically lower runtime—about 15–23× faster on 800-node instances.

Very Large Graphs

To push the limits of our approach, we tested Rank-1 on random 3-regular graphs with 50,000 and 100,000 nodes using 800 parallel workers. On the 100,000-node graph, Rank-1 finds a cut value of 137,796 in about 17 hours, compared to 100,781 for random search. Most of the runtime is spent computing the principal eigenvector of the Laplacian.

We introduce a family of algorithms for Max-3-Cut that exploit low-rank Laplacian structure to build polynomially-sized candidate sets guaranteed to contain the exact maximizer. Our approach provides a principled middle ground between expensive SDP solvers (strong guarantees, slow) and heuristics (fast, no guarantees), and is inherently parallelizable. The Rank-1 algorithm, in particular, scales to graphs with tens of thousands of nodes while finding optimal or near-optimal cuts on structured instances.

• GPU-accelerated higher-rank solvers: Our Rank-2 and Rank-3 algorithms are embarrassingly parallel. A GPU implementation (already prototyped) dramatically accelerates the candidate enumeration, reducing Rank-3 on \(n=50\) from 30 minutes to 23 seconds.
• Warm-starting local search: Using Rank-1 solutions to initialize genetic or breakout algorithms could combine our speed advantage with the fine-grained optimization of heuristics.
• Quantum applications: Max-3-Cut is a standard benchmark for QAOA. Our low-rank solutions could provide warm starts for quantum algorithms.
• Randomized candidate sampling: Can sampling a random subset of the candidate set yield near-optimal solutions with high probability, further reducing runtime?
• Extensions to Max-K-Cut for \(K \geq 4\): The complex quadratic form does not correspond to Max-\(K\)-Cut for \(K \geq 4\), but alternative formulations using higher-dimensional simplices may bridge this gap.

This work was supported in part by the National Science Foundation under CAREER award no. 2145629 and a Ken Kennedy Institute award at Rice University.

@article{Stevens2025maxkcut,
  title   = {Exploiting Low-Rank Structure in Max-$K$-Cut Problems},
  author  = {Stevens, Ria and Liao, Fangshuo and Su, Barbara and Li, Jianqiang and Kyrillidis, Anastasios},
  journal = {arXiv preprint arXiv:2602.20376},
  year    = {2025}
}