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 (\k/, n\^ (c/) + (n) ), where k = ₈ ₂ kᵢ and n=|V|. This improves upon the (12 + ₀) -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 \k, 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.
Makarychev et al. (Wed,) studied this question.