Max-Cut with Multiple Cardinality Constraints

We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph $G=(V, E)$, a partition of the vertices into c disjoint parts V₁, …, Vc, and cardinality parameters k₁, …, kc, the goal is to select a set S ⊆ V such that |S ∩ Vᵢ| = kᵢ for each i ∈ [c], maximizing the total weight of edges crossing S (i.e., edges with exactly one endpoint in S). By designing an approximate kernel for Constrained Max-Cut and building on the correlation rounding technique of Raghavendra and Tan (2012), we present a (0.858 - ε)-approximation algorithm for the problem when $c = O(1)$. The algorithm runs in time O(min/ε, n\(c/ε) + (n)), where k = ∑i ∈ [c] kᵢ and $n=|V|$. This improves upon the (1/2 + ε₀)-approximation of Feige and Langberg (2001) for ₖ (the special case when c=1, k₁ = k), and generalizes the (0.858 - ε)-approximation of Raghavendra and Tan (2012), which only applies when min,n-k\=Ω(n) and does not handle multiple constraints. We also establish that, for general values of c, it is NP-hard to determine whether a feasible solution exists that cuts all edges. Finally, we present a $1/2$-approximation algorithm for Max-Cut under an arbitrary matroid constraint.