Max-Cut with Multiple Cardinality Constraints

A key technical contribution of our work is the construction of an approximate kernel for $\mathrm{Constrained}\mathrm{Max}-\mathrm{Cut}$. Specifically, for any cardinality constraint $k$, we sort the vertices by their (weighted) degrees as $v_1,\mathrm{\dots },v_n$, and define $\tilde{V}$ as the top $O(k/\epsilon )$ vertices. While the graph $G$ remains unchanged, we restrict our attention to solutions contained entirely within $\tilde{V}$. Then, an optimal solution $\tilde{S}$ to ${\mathrm{Max}-\mathrm{Cut}}_k$ over $\tilde{V}$ achieves a cut value that is at least a $(1-\epsilon )$ fraction of the true optimum. In other words,

See Theorem 12 in Section 2 for the formal statement.

This reduction is particularly useful because it allows us to focus on problem instances where $k=\mathrm{\Omega }(n)$. Conceptually, we can contract the vertices in $V\setminus \tilde{V}$ into a single super vertex $s$, and then restrict the solution to exclude $s$. This transforms the sparse regime into one where the effective solution size is a constant fraction of the (reduced) vertex set, enabling the use of correlation rounding techniques that require $k=\mathrm{\Omega }(n)$.

In contrast, prior work by [24] uses kernelization to design fixed-parameter algorithms for ${\mathrm{Max}-\mathrm{Cut}}_k$, but their parameter is the value of the optimal solution itself, and they aim for an exact kernel. As a result, their kernel size is polynomial in $k$, which is insufficient for our purposes. Moreover, their kernelization is sequential and adaptive, while ours is non-adaptive. Our approximate kernel also extends to $\mathrm{Constrained}\mathrm{Max}-\mathrm{Cut}$ with multiple constraints ($c>1$), as formalized in Theorem 14.

Once we reduce to an instance with $k=\mathrm{\Omega }(n)$, we apply the Raghavendra–Tan algorithm [22] to obtain a subset of vertices of size $k^{\prime }\in k\cdot [1-\epsilon ,1+\epsilon ]$, achieving a cut value that is at least an ${\alpha }_{cc}$-fraction of the optimum. We then perform a random correction step: adjusting the solution by randomly adding or removing at most $\epsilon k$ vertices to exactly match the required size $k$, incurring only a negligible loss in cut value.

When $c>1$, however, the rounding procedure of [22] does not directly apply. To handle the setting with multiple constraints, we introduce the notion of $\alpha$-block independence for SDP solutions, which generalizes the standard notion of $\alpha$-independence. Informally, an SDP solution is $\alpha$-block independent if, within each partition $V_i$, the average correlation between pairs of vertices is at most $\alpha$.

We first show how to efficiently construct a block-independent solution. Then, by applying the rounding algorithm of [22], we obtain a subset $S$ that approximately satisfies each group constraint: for each $i\in [c]$, the size $k_i^{\prime }=|S\cap V_i|$ lies in the range $[(1-\epsilon )k_i,(1+\epsilon )k_i]$. Finally, we apply a random correction step within each group to enforce exact feasibility, while ensuring that the cut value degrades by only a negligible amount.

For matroid Max-Cut, we combine techniques from [1] and [7] to design a linear programming relaxation with integrality gap at most $0.5$, which can be solved efficiently. Applying pipage rounding to this relaxation yields a deterministic $0.5$-approximation algorithm.

We use $\mu ={\{{\mu }_S\}}_{|S|\le \mathrm{\ell }}$ to denote a level-$\mathrm{\ell }$ Lasserre pseudo-distribution, where ${\mu }_S:{\{-1,1\}}^S\to [0,1]$ is a distribution over partial assignments to the subset $S\subseteq V$. Let $X_S$ denote the random variables jointly distributed according to ${\mu }_S$, and $X_i$ the marginal variable for $i\in V$ under ${\mu }_{\{i\}}$. We write ${\mathbb{P}}_{{\mu }_S}[X_S\in A]$ to denote the pseudo-probability that the assignment to $S$ lies in the event $A\subseteq {\{-1,1\}}^S$. In particular, conditional pseudo-probabilities are expressed as ${\mathbb{P}}_{{\mu }_{S\cup \{i\}}}[X_i=1\mid X_S=\alpha ]$, which denotes the pseudo-probability that $X_i=1$ given that $X_S=\alpha$ for some $\alpha \in {\{-1,1\}}^S$.

To leverage the correlations between vertices, [22] employ an $\mathrm{\ell }$-round Lasserre SDP for ${\mathrm{Max}-\mathrm{Cut}}_k$ with a sufficiently large constant $\mathrm{\ell }$, formally described in Equation 2.

One method to assess the correlation between two random variables $X_i$ and $X_j$ is through mutual information, defined as $I_{{\mu }_{\{i,j\}}}(X_i;X_j)=H(X_i)-H(X_i\mid X_j)$, where $X_i$ and $X_j$ are sampled according to the local distribution ${\mu }_{\{i,j\}}$. An SDP solution is $\alpha$-independent if the average mutual information between uniformly random vertex pairs is at most $\alpha$, i.e., ${𝔼}_{i,j\in V}[I(X_i;X_j)]\le \alpha$.

For many standard rounding schemes, such as halfspace rounding, the variance in the balance of the resulting cut is directly linked to the average correlation among random vertex pairs. Specifically, if the rounding scheme is applied to an $\alpha$-independent solution, the variance in the cut’s balance is bounded by a polynomial function of $\alpha$.

If all vertices in a $t$-round Lasserre SDP solution are highly correlated, conditioning on the value of one vertex reduces the entropy of the rest. Formally, if the solution is not $\alpha$-independent (i.e., ${𝔼}_{i,j\in V}[I(X_i;X_j)]>\alpha$), then conditioning on a randomly chosen vertex $i$ and its value $b$ decreases the average entropy of the remaining variables by at least $\alpha$. Repeating this process $1/\alpha$ times suffices to obtain an $\alpha$-independent solution. Thus, starting from a $t$-round Lasserre SDP solution, this process results in a $(t-\mathrm{\ell })$-round $\alpha$-independent solution for some $\mathrm{\ell }=O(1/\alpha )$.

Given an $\alpha$-independent SDP solution, many natural rounding schemes ensure that the balance of the output cut is concentrated around its expectation. Hence, it suffices to construct rounding schemes that preserve the expected balance. Raghavendra and Tan [22] present a simple rounding procedure that preserves the individual bias of each vertex, thereby ensuring the global balance property.

An elegant probabilistic argument from [22] shows how to convert an $(\mathrm{\ell }+4/{\alpha }^2+1)$-round Lasserre SDP solution into an $\alpha$-independent $\mathrm{\ell }$-round solution, while losing only an additive factor of $\alpha$ in the objective value (assuming the optimum is normalized to at most $1$).

Lemma 9 implies the existence of a $t\le 1/\alpha +1$ such that conditioning on the joint assignment to $t$ randomly sampled vertices reduces the average mutual information between other pairs to at most $\alpha$.

Theorem 10 implies that there exists $t=O(1/{\alpha }^2)$ such that conditioning on $t$ vertices yields an $\alpha$-independent solution with probability at least $\alpha /2$. Since the sampling procedure preserves the marginal biases of the vertices, the SDP objective remains close to optimal in expectation. By Markov’s inequality, the value of the conditioned solution is at least $\text{OPT}-\alpha$ with probability at least $1/(1+\alpha )$. Thus, there exists a small subset of vertices such that conditioning on them yields an $\alpha$-independent solution with near-optimal value.

Algorithm 5.3 of [22] is a rounding scheme that preserves the bias (according to the SDP solution) of every vertex while also approximately preserving the pairwise correlations up to polynomial factors. Using numerical techniques, they show that the probability of an edge being cut is at least ${\alpha }_{cc}\approx 0.858$ times its contribution to the SDP objective, implying that the total cut value is at least ${\alpha }_{cc}$ times the SDP value.

By applying Chebyshev’s inequality to Theorem 11, the number of vertices in the cut lies in the range $k\pm n\cdot O({\alpha }^{1/24})$ with high probability. When $k/n=\mathrm{\Omega }(1)$, we can choose $\alpha =\mathrm{\Omega }(1)$ small enough so that the relative deviation is within $\epsilon k$. A post-processing step can then adjust the set size to exactly $k$ (e.g., by swapping a small number of vertices), which incurs only an $O(\epsilon )$ fractional loss in cut value. However, when $k=o(n)$, the additive error term $n\cdot O({\alpha }^{1/24})$ may significantly exceed $k$, making it difficult to ensure cardinality feasibility without substantially affecting the objective.

For any subset $S\subseteq V$ and vertex $i\in V$, we write $S+i:=S\cup \{i\}$ and $S-i:=S\setminus \{i\}$. Let $G=(V,E)$ be a graph with non-negative edge weights $w:E\to {ℝ}_{\ge 0}$. For a parameter $r\in \mathbb{N}$, let $H_r\subseteq V$ denote the set of the $r$ highest-degree vertices in $G$ under weight function $w$. If the vertex set $V$ is partitioned into $c$ disjoint groups, $V={⨄}_{i\in [c]}{V}_i$, then $H_r^{(i)}\subseteq V_i$ denotes the $r$ highest-degree vertices in part $V_i$. When the weight function is clear from context, we abbreviate the weighted degree of a vertex $v$ as $\delta (v)$ instead of ${\delta }_w(v)$.

We now describe the approximate kernel construction for the single-group ${\mathrm{Max}-\mathrm{Cut}}_k$ problem.

Input: Graph $G=(V,E)$, cardinality parameter $k$, and approximation parameter .
Output: Reduced graph $\tilde{G}=(\tilde{V},\tilde{E})$.

1. 1.

   If $k/\epsilon \ge n$, return $G$.

2. 2.

   Otherwise, sort the vertices of $G$ in decreasing order of weighted degree, and retain only the top $k/\epsilon$ vertices. Merge the rest of vertices into a super vertex $s$, and return the resulting graph $\tilde{G}$.

Note that the super vertex $s$ appears in the output graph $\tilde{G}$ only if $k/\epsilon +1\le n$.

Let $h:=k/\epsilon$, and recall from the notation in the preliminaries that $H_h$ is the set of the $h$ highest-degree vertices in $G$. Let $S^{\ast }$ be an optimal solution of size $k$ in $G$ with cut value $\delta (S^{\ast })=\text{OPT}$. We will construct a set $S_T\subseteq H_h$ of size $k$ with value close to OPT.

We iteratively transform $S^{\ast }$ into a set within $H_h$ by applying Lemma 13 up to $k$ times. At each step $t$, we replace a vertex $j_t\in S_{t-1}\setminus H_h$ with a vertex $i_t\in H_h\setminus S_{t-1}$ such that:

Since each step increases $|S_t\cap H_h|$ by one, the process terminates in at most $T\le k$ steps. Therefore,

Substituting $h=k/\epsilon$, we get

where the final bound assumes $\epsilon \le 1/2$. $◀$

Since $S\setminus H_h\ne \mathrm{\varnothing }$ and $|S|\le h$, we have $H_h\setminus S\ne \mathrm{\varnothing }$. Let $i\in H_h\setminus S$ be the vertex minimizing $\delta (S,\{i\})$, the total weight of edges between $i$ and $S$. Let $j$ be any vertex in $S\setminus H_h$.

We use the submodularity of the cut function:

Rearranging:

Now we bound $\delta (S,\{i\})$. Since $i$ minimizes $\delta (S,\cdot )$ among $H_h\setminus S$, we have:

which implies:

Putting everything together:

completing the proof. $◀$

We now describe the kernelization procedure for the $\mathrm{Constrained}\mathrm{Max}-\mathrm{Cut}$ problem with multiple vertex groups.

Input: Graph $G=(V={⨄}_{i\in [c]}{V}_i,E)$, cardinality constraints $k_1,\mathrm{\dots },k_c$, and approximation parameter .
Output: Reduced graph $\tilde{G}=(\tilde{V}={⨄}_{i\in [c]}{\tilde{V}}_i,\tilde{E})$.

1. 1.

   For each $i\in [c]$, if $k_i/\epsilon +1\le n_i:=|V_i|$, retain the top $k_i/\epsilon$ vertices in $V_i$ by weighted degree and merge the remaining vertices into a super vertex $s_i$.

2. 2.

   Return the resulting graph $\tilde{G}$.

Note that a super vertex $s_i$ appears in the output graph $\tilde{G}$ only if $k_i/\epsilon +1\le n_i$. Let $S_{\text{super}}:=\{s_i\mid s_i\text{ exists in }\tilde{G}\}$ denote the set of all super vertices.

Let $S^{\ast }$ be an optimal solution to the original instance with $\delta (S^{\ast })=\text{OPT}$. For each part $i\in [c]$, define $H_i:=H_{k_i/\epsilon }^{(i)}$ as the top $k_i/\epsilon$ vertices in $V_i$ by weighted degree (as defined in the preliminaries).

We will transform $S^{\ast }$ into a solution $S_T$ such that $S_T\cap V_i\subseteq H_i$ for every $i\in [c]$ while losing only a small fraction of the cut value. At each step $t$, identify the smallest index $p\in [c]$ for which $S_t\cap V_p⊈H_p$, and apply the local exchange from Corollary 16 to swap a vertex $j\in (S_t\cap V_p)\setminus H_p$ with a vertex $i\in H_p\setminus (S_t\cap V_p)$, yielding a new set $S_{t+1}$ with

For each $i\in [c]$, we perform at most $k_i$ such exchanges in $V_i$. Hence, the total cut value at the end satisfies:

Using the inequality ${(1-x)}^m\ge 1-mx$, we get

where the final bound assumes $\epsilon \le 1/2$. $◀$

The proof is identical to that of Lemma 13. It proceeds by selecting $i$ to minimize $\delta (S,\{i\})$ over $H\setminus S$ and applying cut submodularity to bound the loss when replacing $j\in S\setminus H$. $◀$

Using $H=(S\backslash V_p)\cup H_h^{(p)}$ in Lemma 15, and the fact that $H\backslash S=H_h^{(p)}\backslash (S\cap V_p)$ finishes the proof. $◀$

Using Lemma 18 (1), the optimal value on the kernelized instance $\tilde{G}$ is at least $(1-4\epsilon )\text{OPT}$. After solving the SDP, we obtain a value at least $(1-\epsilon )\widetilde{\text{OPT}}\ge (1-5\epsilon )\text{OPT}$.

The expected size of $\widehat{S}$ is exactly $k$ since Algorithm 5.3 from [22] preserves the bias of each vertex. Using Theorem 11, the variance of the balance $|\widehat{S}|/|\tilde{V}|$ is at most $O({\epsilon }^{60/12})=O({\epsilon }^5)$ (Assume that the constant hidden in the $O$-notation is $1$ for simplicity. One can absorb the constant into the $\epsilon$ in general). By Chebyshev’s inequality, the event $ℰ$ occurs with probability at least $1-\epsilon$.

The expected cut value conditioned on $ℰ$ satisfies:

Let $S$ be the final corrected set. Then:

Steps 1 and 4 take $O(|E|\log |E|)$ and $O(|V|)$ time, respectively. Steps 2 and 3, which involve solving the Lasserre SDP and rounding, dominate the runtime and require $O{(|\tilde{V}|)}^{\mathrm{poly}(1/\epsilon )}$ time. $◀$

Part (1) follows from Theorem 12. For part (2), we show that a uniformly random subset of $V\setminus \{s\}$ of size $k$ cuts any edge with probability at least $\epsilon$.

Let $n^{\prime }:=|\tilde{V}\setminus \{s\}|$. Then $2k\le n^{\prime }\le k/\epsilon$. If edge $e$ is adjacent to $s$, it is cut with probability $k/n^{\prime }\ge \epsilon$. Otherwise, the cut probability is $2k(n^{\prime }-k)/(n^{\prime }(n^{\prime }-1))\ge k/n^{\prime }\ge \epsilon$. $◀$