Max-Cut with Multiple Cardinality Constraints

Abstract

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_1,\dots ,V_c$, and cardinality parameters $k_1,\dots ,k_c$, the goal is to select a set $S\subseteq V$ such that $|S\cap V_i|=k_i$ for each $i\in [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-\epsilon )$-approximation algorithm for the problem when $c=O(1)$. The algorithm runs in time $O\left(\min\{k/\varepsilon, n\}^{\poly(c/\varepsilon)} + \poly(n)\right)$, where $k={\sum }_{i\in [c]}{k}_i$ and $n=|V|$. This improves upon the $(\frac{1}{2}+{\epsilon }_0)$-approximation of Feige and Langberg (2001) for $\maxcut_k$ (the special case when $c=1,k_1=k$), and generalizes the $(0.858-\epsilon )$-approximation of Raghavendra and Tan (2012), which only applies when $\min \{k,n-k\}=\hat{I}\text{c◯}(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.