{"ID":2894123,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12607","arxiv_id":"2507.12607","title":"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, \\ldots, V_c$, and cardinality parameters $k_1, \\ldots, 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 - \\varepsilon)$-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} + \\varepsilon_0)$-approximation of Feige and Langberg (2001) for $\\maxcut_k$ (the special case when $c=1, k_1 = k$), and generalizes the $(0.858 - \\varepsilon)$-approximation of Raghavendra and Tan (2012), which only applies when $\\min\\{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.","short_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, \\ldots, V_c$, and cardinality parameters $k_1, \\ldots, k_c$, the goal is to select a set $S \\subseteq V$...","url_abs":"https://arxiv.org/abs/2507.12607","url_pdf":"https://arxiv.org/pdf/2507.12607v1","authors":"[\"Yury Makarychev\",\"Madhusudhan Reddy Pittu\",\"Ali Vakilian\"]","published":"2025-07-16T19:54:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}