Id: arxiv/2608.08499 Url: https://arxiv.org/abs/2608.08499 Tags: math.OC Score: 0 Title: Max-$k$-Cut via Node Features Domain: math.OC Source: arxiv Authors: Avinash Bhardwaj, Hritiz Gogoi, Vishnu Narayanan Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-09 Page: https://delphi.science/r/arxiv/2608.08499 We study the Max-$k$-Cut problem from a node-feature perspective, where each vertex is associated with a feature vector and edge weights are given by pairwise inner products. We first examine the semidefinite relaxation of Max-$k$-Cut from this perspective. Using a normal-cone argument, we derive a general sufficient condition for exactness of the Frieze--Jerrum relaxation and show that it is satisfied in two feature-structural regimes: perfect feature balance, where the aggregate feature vectors of the parts are equal, and feature dominance, where a small set of large nonnegative feature…