{"id":"f2a052d0-845e-4f1b-960f-e4c67331aab7","arxiv_id":"2507.12607","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"For Max-Cut with multiple cardinality constraints, an (0.858 - ε)-approximation algorithm is given, improving the previous (0.5 + ε0) guarantee for sparse single-constraint instances.","lead":"This paper presents a new approximation algorithm for Max-Cut with cardinality constraints, achieving a 0.858-quality guarantee for both single and multiple size requirements. It also introduces an approximate kernel technique and improves over a two-decade-old 0.5-level bound for small cuts.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Normalization gap in The proofs of Theorems 4/5: the additive ε^60 SDP loss is not negligible when the kernelized graph has tiny surviving edge weight, so the claimed (αcc−ε)-approximation is unproven.","rationale":"The paper's central claim is Theorem 5, and its proof depends on a chain: approximate kernel, SDP conditioning with an additive loss, RT rounding, and correction. The reader's weakest assumption targets the RT rounding carry-over to block-independent solutions; in my reading that step is plausible and standard, because RT's per-edge cut-probability bound is local and the per-block variance bound is exactly Theorem 11 with W uniform on each block. The genuinely load-bearing soft spot is earlier: the analysis needs the conditioned SDP value to be at least (1−ε)]OPT, but the paper chooses α=ε^60 as an additive loss. Lemma 18(2)/24(2) only proves ]OPT ≥ ε·W(eE), where W(eE) is the surviving kernel edge weight, not ]OPT ≥ ε^59. W(eE) can be arbitrarily small, e.g., a perfect matching with k=1 and huge n. In that regime, the additive loss is not a (1−ε)-multiplicative loss, and no lower bound on the final cut value follows from the written proof. This is a concrete, checkable gap, and it threatens the central claim more directly than the NP-hardness reduction issue or the Lasserre round-count typo, which are real but peripheral. I am not asserting the theorem is false; a separate argument or a fallback algorithm for tiny kernelized optimum might repair the proof. But as written, the central approximation guarantee is not established for all instances, so the paper should be revised to address this gap before acceptance.","tokens_in":17778,"tokens_out":51810,"duration_ms":658613,"concrete_test":"Fix ε=0.1 and take a perfect matching on n>2·10^59 vertices, each edge of weight 2/n (total weight 1), with k=1. Run the kernel of Section 2.1: it retains 10 vertices and merges the rest into s, so W(eE)=20/n and ]OPT=2/n. Verify whether the chain in Section 3.3 is valid: Lemma 18(2) gives ]OPT ≥ ε·W(eE) (true), but the claimed inequality ]OPT−ε^60 ≥ (1−ε)]OPT requires ]OPT ≥ 10^{-59}, which fails. Then search the paper for any other argument that lower-bounds the conditioned SDP value in this regime; if none exists, the proof of Theorem 4 (and hence Theorem 5) is incomplete for this family of instances. This analytic check settles whether the normalization concern lands.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 3.3 Step 2(b) concludes from Lemma 18(2) that ]OPT − ε^60 ≥ (1−ε)]OPT. Lemma 18(2) only yields ]OPT ≥ ε·W(eE), where W(eE) is the total weight of edges surviving the kernel (edges with at least one endpoint among the top k/ε vertices). The desired inference requires ]OPT ≥ ε^59, i.e., W(eE) ≥ ε^58. No such bound holds: for an equal-weight perfect matching with k=1, ε=0.1, and n>2ε^{-59}, the kernel keeps 10 vertices plus the supervertex s; W(eE)=20/n and ]OPT=2/n, both far below ε^59. In this regime the guarantee of Theorem 10 (value ≥ ]OPT−ε^60) is vacuous, so the subsequent RT rounding may have no positive value guarantee. The same inference appears in Lemma 23 via Lemma 24, and it affects both Theorem 4 and the central Theorem 5. This is an internal algebraic gap in the normalization, not a matter of external consensus. A fallback for small W(eE) is absent from the paper, and without one the main approximation claims are unsupported for instances with very small kernelized optimum.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Constrained Max-Cut, in which vertices are partitioned into c parts and a solution must select exactly k_i vertices from each part while maximizing the weight of edges crossing the selected set. The main claimed contribution is an (α_cc − ε)-approximation algorithm for c = O(1), where α_cc ≈ 0.858 is the Raghavendra–Tan constant, running in time O(min{k/ε, n}^{poly(c/ε)} + poly(n)). The approach combines an approximate kernel that reduces the instance to O(k/ε) vertices with a Lasserre SDP and the Raghavendra–Tan correlation rounding technique, extended to a new notion of α-block independence. The paper also gives a 0.5-approximation for Max-Cut under an arbitrary matroid base constraint and proves NP-hardness of deciding whether a feasible solution cuts all edges for an arbitrary number of cardinality constraints. The kernel construction and several of the local lemmas are argued in detail, but the proof of the central approximation theorems contains a normalization error, and the multi-constraint algorithm has an internal inconsistency in the SDP round count; the hardness reduction also does not produce instances matching the paper's own definition of the problem.","tokens_in":18094,"tokens_out":18943,"duration_ms":236822,"significance":"If the main results were fully established, this would be a substantial advance: it would extend the near-optimal Raghavendra–Tan approximation from the balanced regime min{k, n−k} = Ω(n) to all cardinality values and to multiple simultaneous cardinality constraints, and the approximate kernel would be a reusable tool for converting sparse cut instances into dense ones. The paper is also careful in attributing the correlation rounding package to [RT12] and in identifying the exact hypotheses inherited from that work. However, the central approximation claim is not currently supported by the proof as written, because of a concrete algebraic error in the normalization of the SDP loss; this affects both Theorem 4 and Theorem 5. The block-independence extension is plausible, but the paper should explicitly verify that the imported Raghavendra–Tan rounding guarantees apply to solutions that are only block-independent rather than globally α-independent. The matroid 0.5-approximation is a nice contribution, and the hardness result, once repaired to fit the formal problem definition, would be a useful complement.","major_comments":[{"comment":"The inference \"]OPT − ε^60 ≥ (1−ε)]OPT\" is not justified by the cited lemma. Lemma 18(2) states only that ]OPT is at least an ε-fraction of the total edge weight in the kernelized graph eE, i.e., ]OPT ≥ ε·W(eE). The desired inequality requires ]OPT ≥ ε^59, which does not follow. Concretely, take a perfect matching on n vertices with total edge weight normalized to 1, set k=1 and ε=0.1; the kernel keeps 10 vertices plus the supervertex s, so W(eE)=20/n and ]OPT=2/n. For n > 2·10^59 we have ]OPT < ε^59, and the additive loss ε^60 exceeds ]OPT, making the guarantee \"SDP value ≥ ]OPT − ε^60\" vacuous. The same erroneous step appears in Section 4.3 in the proof of Lemma 23 via Lemma 24. Since this step is used to claim that the conditioned SDP value is at least (1−ε)]OPT ≥ (1−5ε)OPT, the subsequent lower bound on the rounded cut value fails for instances with very small kernelized optimum. A separate argument covering the small-]OPT regime is needed for the proofs of Theorems 4 and 5 to go through.","section":"Section 3.3, Step 2(b); Section 4.3, Lemma 24"},{"comment":"The Lasserre level stated in Algorithm 4.1 is inconsistent with Theorem 22. Theorem 22 with α = ε^60 and ℓ = 2 requires an initial (L+ℓ)-round solution with L = 4c^2/α^2 = 4c^2/ε^120, i.e., a total of 4c^2/ε^120 + 2 rounds. Algorithm 4.1 instead states that the algorithm solves a (3 + 4c/ε^120)-round SDP. This differs both in the factor multiplying c and in the additive constant. As written, the algorithm does not supply the level required by the conditioning theorem it invokes, so the multi-constraint analysis is not supported; this must be corrected.","section":"Section 4.1, Algorithm 4.1 Step 2(a); Theorem 22"},{"comment":"The reduction from 3D matching does not produce an instance of Constrained Max-Cut as defined in Definition 1. In Definition 1, the sets V_1, ..., V_c partition all of V and every vertex is subject to exactly one cardinality constraint. In the reduction, the star centers are not assigned to any part V_i and are effectively unconstrained. The completeness and soundness arguments rely on the freedom to place each center either in S or outside S independently of the partition-matroid constraints; no assignment of the centers to parts with prescribed cardinalities reproduces this freedom. Consequently, Theorem 7 is not established for the problem defined in the paper. The proof also writes δ(S)=1 where the decision problem asks for δ(S)=|E|, which is a notational slip but should be fixed.","section":"Section 5.2, Proof of Theorem 7"},{"comment":"The paper states that Algorithm 5.3 of [RT12] preserves vertex biases, cuts each edge with probability at least α_cc times its SDP contribution, and satisfies the variance bound of Theorem 11, and then applies this package to solutions that are only α-block independent. The concentration part is a direct application of Theorem 11 with W uniform on each block, but the edge-cutting guarantee is imported without explicitly checking whether it holds for solutions that are not globally α-independent. The authors should either cite the exact statement from [RT12] that covers the block-independent case or prove that the rounding guarantee extends; as written, this is an unverified load-bearing assumption.","section":"Sections 1.2 and 4, use of Raghavendra–Tan rounding"}],"minor_comments":[{"comment":"In the second case of the proof, the text says \"When x + y ≤ 1\" but the case is actually x + y ≥ 1; the argument then substitutes x′ = 1−x, y′ = 1−y to reduce to the first case. The typo should be corrected.","section":"Appendix B, Lemma 27"},{"comment":"The expression \"u ∈ X ∩ Y ∩ Z\" should read \"u ∈ X ∪ Y ∪ Z\", since every element of the three sets imposes a part constraint in the reduction.","section":"Section 5.2, Proof of Theorem 7"},{"comment":"The proofs use the phrase \"Assume that the constant hidden in the O-notation is 1 for simplicity\". This is acceptable for exposition, but the constants in Chebyshev's inequality and in the final approximation ratio should be tracked more explicitly to avoid any hidden dependence on ε and c in the O(ε) terms.","section":"Section 3.3 and Section 4.3"},{"comment":"The paper defines α-independence with respect to a distribution W and then uses the same notation for the uniform distribution over a block V_j. This is clear in context, but a sentence explicitly stating that block independence is exactly α-independence with respect to each W_j would help the reader.","section":"Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the normalization gap in Sections 3.3 and 4.3: the claim that ]OPT − ε^60 ≥ (1−ε)]OPT is algebraically false under the stated Lemma 18(2)/Lemma 24, and it directly affects the central approximation theorems. This is not a subjective disagreement; it is an internal gap that the authors need to repair, most likely by adding a handling of the regime where the kernelized optimum is very small. The round-count inconsistency in Algorithm 4.1 and the hardness-reduction mismatch with Definition 1 are also concrete and need to be addressed. If these points can be fixed, the paper has a good chance of being a strong contribution; at present it is not ready for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Real improvement here: the O(k/ε) approximate kernel is genuinely new, and combining it with Raghavendra–Tan correlation rounding gives the first αcc−ε approximation for sparse Max-Cutk and for multiple cardinality constraints. The block-independence definition and the conditioning procedure are a natural and convincing extension. The matroid 0.5-approximation is a clean exercise, correctly attributed to the pipage rounding line. These are worthwhile contributions.\n\nThe soft spots, in decreasing order of seriousness. First, the normalization: Step 2(b) of the single-constraint algorithm and the corresponding step in the multi-constraint version claim ]OPT − ε^60 ≥ (1−ε)]OPT from Lemma 18(2). Lemma 18(2) only gives ]OPT ≥ ε·W(eE); the inference needs W(eE) ≥ ε^58. No such bound holds. Concretely, with k=1, ε=0.1, and a perfect matching on n > 2ε−59 vertices, the kernel keeps 10 vertices plus the supervertex, W(eE)=20/n, and ]OPT=2/n. The claimed inequality is false, and the SDP lower bound is vacuous. This affects both Theorem 4 and Theorem 5. The result might still be true in such regimes—in the matching example every feasible solution is near-optimal—but the proof as written does not cover them. A fallback for small surviving edge weight is missing.\n\nSecond, Theorem 7's reduction is not a valid instance of Constrained Max-Cut as defined: the star centers are never placed in any part, yet the problem requires V to be partitioned. This is patchable, but as stated it is a gap.\n\nThird, minor: Algorithm 4.1 solves a (3+4c/ε120)-round Lasserre SDP, while Theorem 22 requires 4c²/ε120 + 2 rounds. Likely a typo, but the c vs c² difference should be fixed. Also, in the hardness proof the text says δ(S)=1 where it clearly means all edges are cut; another typo.\n\nThe RT rounding black box is used in the way the literature normally uses it; the block-independence extension of Theorem 11 to each block is legitimate, not a hidden assumption.\n\nWho this is for: approximation algorithms people working on SDP hierarchies and graph partitioning. It deserves a serious referee; send it to review, but ask for the normalization gap to be addressed before acceptance.","headline":"A solid, novel kernel + RT rounding for sparse constrained Max-Cut, but the main proof has a normalization gap that needs fixing, and the hardness reduction needs patching.","tokens_in":18671,"tokens_out":7923,"would_cite":true,"duration_ms":94687,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C22","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Max-Cut with multiple exact size quotas can be approximated within (0.858 − ε) of optimal in polynomial time whenever the number of quotas is constant.","keywords":["Constrained Max-Cut","cardinality constraints","approximation algorithms","semidefinite programming","Lasserre hierarchy","correlation rounding","kernelization","matroid constraints"],"falsifier":"Construct a small Constrained Max-Cut instance with two groups, solve its Lasserre SDP, enforce $\\varepsilon^{60}$-block independence by conditioning, apply the inherited rounding step, and measure the variance of the number of selected vertices in each group over many trials; if the variance is not $O(\\varepsilon^5)$ relative to the group size, the correction step cannot restore exact quotas without an $O(\\varepsilon)$ cut loss, and Theorems 4 and 5 fail.","tokens_in":17554,"feed_emoji":"✂️","tokens_out":15122,"duration_ms":150305,"temperature":0.7,"pith_summary":"The paper's target is Constrained Max-Cut: choose exactly $k_i$ vertices from each of $c$ given groups so that the number of edges crossing the chosen set is maximized, and show this can be done almost as well as unconstrained Max-Cut. Its main result is a $(0.858-\\varepsilon)$-approximation algorithm that runs in polynomial time whenever the number of groups is constant, for every $\\varepsilon>0$, even when the chosen set is tiny relative to the graph. That improves the old guarantee for a sparse single cardinality constraint, which was only a little above $1/2$, and extends an earlier $0.858$ result that applied only when the chosen set was a constant fraction of the graph. The paper also proves that deciding whether all edges can be cut is NP-hard when the number of constraints is allowed to grow, and that matroid-constrained Max-Cut has a deterministic $1/2$-approximation.","feed_headline":"Max-Cut with exact quotas hits 0.858 approximation","feed_subtitle":"Even sparse target sets and multiple group quotas now reach near-unconstrained cut quality in polynomial time.","key_machinery":"Two mechanisms carry the argument. The first is an approximate kernel: within each group the algorithm keeps only the top $O(k_i/\\varepsilon)$ highest-degree vertices, merges the rest into a super-vertex, and shows that restricting solutions to this core costs at most a $1-4c\\varepsilon$ factor of the optimum. The second is the rounding pipeline: solve a high-level Lasserre SDP (a hierarchy of semidefinite programming relaxations), condition on a few sampled vertices to make the solution $\\alpha$-block independent (average mutual information inside each group at most $\\alpha$), then apply the bias-preserving correlation-rounding procedure of [RT12], which cuts each edge with probability at least $\\alpha_{\\mathrm{cc}}$ times its SDP contribution and makes each group's selected count have variance $O(\\alpha^{1/12})$. A final random correction replaces a small number of vertices per group to meet the quotas exactly with only an $O(\\varepsilon)$ loss.","core_discovery":"On the paper's own terms, the central claim is Theorem 5: for every $\\varepsilon>0$, there is an algorithm that runs in $O(\\min\\{k/\\varepsilon, n\\}^{\\mathrm{poly}(c/\\varepsilon)} + \\mathrm{poly}(n))$ time, where $k=\\sum_i k_i$, and returns a feasible solution with cut value at least $(\\alpha_{\\mathrm{cc}}-\\varepsilon)$ times the optimum, where $\\alpha_{\\mathrm{cc}}\\approx 0.858$. The single-constraint special case $c=1$ gives the same guarantee for Max-Cut$_k$ for every $k$, including the sparse regime $k=o(n)$ that previously had only a $1/2+\\varepsilon_0$ approximation. The same machinery yields a deterministic $1/2$-approximation for Max-Cut under an arbitrary matroid constraint, and an NP-hardness result for the fully general multi-constraint problem: even deciding whether a feasible cut cuts every edge is hard when the number of constraints is unbounded.","pith_inferences":["A consequence the authors leave implicit: the same kernel-plus-rounding recipe may transfer to other constraint satisfaction problems with exact-size constraints, suggesting that sparse quotas need not force the approximation ratio down to $1/2$.","The NP-hardness result hints at a phase transition in $c$—constant is easy, arbitrary is hard—so locating the exact threshold between $\\mathrm{poly}(\\log n)$ and $n$ is a natural next question.","A testable extension the paper does not pursue: on low-degree graphs whose optimal cuts use vertices just below the degree cutoff, the kernel's $(1-4c\\varepsilon)$ retention bound may be loose, and smaller kernels could be possible.","For matroid Max-Cut the $1/2$ factor may be improvable for partition matroids, since the paper's multi-constraint algorithm already reaches $0.858$ for constant $c$; whether stronger SDP relaxations close the gap is left open."],"forward_implications":["The sparse regime of a single cardinality constraint gains the $0.858$ approximation, replacing the previous $1/2+\\varepsilon_0$ bound for all $k$.","When the number of groups $c$ is constant and $\\varepsilon$ is fixed, the algorithm runs in polynomial time, so exact per-group quotas are approximable almost as well as ordinary Max-Cut.","Deciding whether a feasible solution cuts every edge is polynomial-time for constant $c$, quasipolynomial for $c=\\mathrm{poly}(\\log n)$, and NP-hard for arbitrary $c$.","Matroid Max-Cut, which contains the uniform and partition cases, has a deterministic $1/2$-approximation."],"supporting_citations":[{"why":"Supplies the correlation-rounding algorithm with bias preservation, the $\\alpha_{\\mathrm{cc}}$ edge-cut guarantee, and the $O(\\alpha^{1/12})$ balance variance used after kernelization.","marker":"[RT12]"},{"why":"Gives the previous $(1/2+\\varepsilon_0)$-approximation for Max-Cut$_k$ that the single-constraint result improves.","marker":"[FL01]"},{"why":"Provides the pipage rounding method used for the deterministic $1/2$-approximation in matroid Max-Cut.","marker":"[AS04]"},{"why":"Provides the matroid pipage rounding technique used in the LP-based $1/2$-approximation.","marker":"[CCPV11]"},{"why":"Supplies the lemma bounding the loss when a random set is added, used in the exact-cardinality correction step.","marker":"[BFNS14]"},{"why":"Gives the prior $(1/3-\\varepsilon)$-approximation for symmetric submodular maximization under a matroid base constraint, which the matroid result improves.","marker":"[LMNS10]"}],"fun_headline_variants":["Exact quota Max-Cut gets 0.858 approximation","Multiple constraints, one cut: 0.858 guarantee","Matroid Max-Cut: 1/2 approximation","Quota-constrained Max-Cut: 0.858 algorithm","Sparse quotas: Max-Cut reaches 0.858"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a rounding procedure that provably works when the whole graph is nearly uncorrelated still works when the graph is made nearly uncorrelated separately inside each group, so that the paper can shrink the graph and round group-by-group without re-proving the procedure's guarantees.","fun_headline_variants_meta":{"raw":{"variants":["Exact quota Max-Cut gets 0.858 approximation","Multiple constraints, one cut: 0.858 guarantee","Matroid Max-Cut: 1/2 approximation","Quota-constrained Max-Cut: 0.858 algorithm","Sparse quotas: Max-Cut reaches 0.858"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000858,"raw_usage":{"total_tokens":3812,"prompt_tokens":1121,"completion_tokens":2691,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":2606}},"tokens_in":737,"tokens_out":2691,"duration_ms":23987,"temperature":1.0,"reasoning_tokens":2606,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:47:59.053087+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small Constrained Max-Cut instance with two groups, solve its Lasserre SDP, enforce $\\varepsilon^{60}$-block independence by conditioning, apply the inherited rounding step, and measure the variance of the number of selected vertices in each group over many trials; if the variance is not $O(\\varepsilon^5)$ relative to the group size, the correction step cannot restore exact quotas without an $O(\\varepsilon)$ cut loss, and Theorems 4 and 5 fail.","supporting_citations":[],"review_version":1}