{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}