{"id":"167d38c5-4d4e-400e-b1a2-148c81c3c104","arxiv_id":"2505.18043","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A primal-dual framework yields (b_local+1)-, 2(b_robust+1)-, and 2(b_global+1)-approximation algorithms for overlapping and robust edge-colored hypergraph clustering, with matching hardness and integrality gap bounds.","lead":"The paper gives faster primal-dual algorithms for three NP-hard edge-colored hypergraph clustering problems, matching or improving prior approximation ratios while running combinatorially fast. It also provides matching hardness and integrality gap results, resolving two open questions from prior work.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the primal-dual proofs are internally consistent and the only caveat is the UGC-conditioned optimality claim for Local ECC.","rationale":"The reader's weakest assumption (UGC dependence) is real but explicitly conditional and does not affect the unconditional algorithmic theorems. I found no internal inconsistency in the primal-dual analyses, the dual-feasibility invariants, the integrality-gap examples, or the hardness reductions. The only unsupported assertion is the experimental remark in Section 4.1 about the LP relaxation giving a better lower bound, which is not load-bearing for the central claim. Therefore the ACCEPT verdict remains appropriate.","tokens_in":25691,"tokens_out":50091,"duration_ms":492593,"concrete_test":"Independently re-derive Lemma C.2 by tracking the dual invariant sum_{e in delta(v)} beta_e,v - alpha_v = lambda through edge-removal events, and verify the algebraic steps leading to ALG <= (2b_robust+2) OPT; a correct re-derivation that preserves the invariant at every event would confirm the Robust ECC ratio.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the three central proofs as in-scope evidence: the Local ECC primal-dual ratio in Lemma B.2, the Robust ECC invariant in Lemma C.2, and the Global ECC bound in Lemma D.2. The dual variables are maintained feasibly: for Robust, the third dual constraint uses the sum over all incident beta, so removing a tight edge from L does not break the equality B_v - alpha_v = lambda; the set R' at termination contains the last-iteration R and has size greater than b_robust, so the split at R'' is valid. The integrality-gap examples in Theorems 3.2, 3.7, and 3.8 satisfy their LP constraints, and the Ek-Vertex-Cover reductions in Appendix B.3 preserve the optima exactly. No circular step or missing proof was found in the theoretical core. The only caveat is that Theorem 3.3's 'essentially best possible' statement relies on UGC through Theorem B.4, so if UGC is false, the optimality claim loses support; the P != NP version and all positive algorithmic results remain intact. Separately, Section 4.1 asserts without proof that the authors' LP relaxation always gives a better lower bound than Crane et al.'s; this is an experimental-methodology claim and does not affect the theorems.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes primal-dual approximation algorithms for three edge-colored hypergraph clustering problems: Local ECC, Robust ECC, and Global ECC. For Local ECC it gives a (b_local+1)-approximation algorithm running in linear time, matching the previous LP-rounding ratio with a purely combinatorial implementation. For Robust ECC and Global ECC it gives true (non-bicriteria) approximation algorithms with ratios 2(b_robust+1) and 2(b_global+1), respectively, in both cases independent of the hypergraph rank. The paper further proves integrality gap lower bounds for the three LP relaxations, UGC-based and P != NP-based inapproximability results for Local ECC, and bicriteria approximation variants. Experiments on six benchmark datasets compare running time and solution quality against prior greedy and LP-rounding algorithms.","tokens_in":25936,"tokens_out":29254,"duration_ms":208193,"significance":"The main algorithmic results are significant: they replace bicriteria guarantees with true approximation ratios for Robust and Global ECC, obtain a linear-time combinatorial algorithm for Local ECC that matches the best known LP-based ratio, and the accompanying hardness results essentially determine the approximability of Local ECC up to a UGC assumption. The primal-dual analyses are detailed and appear sound in the core lemmas, with no fitted parameters and no circular dependence on the results being proved. The experimental evaluation is extensive and consistent with the theoretical findings, showing large practical speedups over LP-rounding and better solution quality than the previous combinatorial greedy algorithm.","major_comments":[{"comment":"The integrality gap construction sets |V| = |E|/(b_local+1), but the argument that any set S of b_local+1 satisfied edges yields a node v_S that must be colored with b_local+1 colors requires V to contain all subsets of E of size b_local+1. With the stated |V|, a chosen set S of satisfied edges need not be one of the labels, so the contradiction does not follow. In fact, if the labels are chosen as a partition of E, each edge is incident to exactly one node and an integral solution can satisfy one edge per node, giving no gap. The proof can be repaired by setting |V| = binom(|E|, b_local+1); the fractional solution then satisfies the edge constraints and the lower bound of |E| - b_local mistakes goes through, yielding a gap converging to b_local+1. As written, however, the proof of the lower bound is invalid.","section":"Appendix B.2 (proof of Theorem 3.2)"},{"comment":"The sentence 'we used our LP relaxation instead since we can prove that our relaxation always yields a better estimate of the true optimum' is unsupported and, for Local and Global ECC, appears to be false: for Local ECC the LP is exactly the one presented in Section 3.1 (the same as Crane et al.'s relaxation), and for Global ECC the paper states in Appendix D.3 that the LP is equivalent to Crane et al.'s. Only for Robust ECC does the added constraint z_v + sum_c x_{v,c} <= 1 strengthen the relaxation. The authors should either prove the claim for each problem or qualify it to Robust ECC; otherwise the relative-error comparisons are presented on an unclear basis.","section":"Section 4.1"}],"minor_comments":[{"comment":"The update line 'l_e <- l_e + min{slack(c), s*} / slack(c) * (w_e - l_e)' divides by slack(c); when slack(c) = 0 the expression is undefined, although in that case no update is needed. Please handle the zero-slack case explicitly.","section":"Appendix B.5 (Algorithm 2)"},{"comment":"Typo: 'LP-rouding algorithm' should be 'LP-rounding algorithm'.","section":"Section 4.3"},{"comment":"The notation budget_L(S) := sum_{v in R} (kappa_L(v) - 1) for S subset of V has an unused argument S; either remove S or define the function as intended over the relevant set.","section":"Appendix D.3 (Lemma D.2)"},{"comment":"The statement begins 'Suppose that b >= 1' but then uses b_robust; please make the variable consistent.","section":"Appendix C.5 (Theorem C.3)"},{"comment":"The proof states that a single iteration runs in O(d_v) and concludes linear total time; it should explicitly mention that the discretized Algorithm 2 performs at most one iteration per vertex, which is why the bound sums to O(sum_v d_v).","section":"Appendix B.1 (Lemma B.3)"},{"comment":"For vertices with chi(delta(v) cap L) = empty, Algorithm 1 assigns the empty set; this is feasible for Local ECC but may be worth stating explicitly, and the arbitrary-color remark used in the other algorithms could be added for consistency.","section":"Section 3.1"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The main algorithmic results appear sound and the paper is a strong contribution to the clustering literature. The proof of Theorem 3.2 has a repairable but load-bearing flaw, and the experimental section contains an unsupported blanket claim about the LP relaxation. Both issues are local and fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers what it promises: the first non-bicriteria approximation algorithms for Robust and Global ECC, with ratios 2(b_robust+1) and 2(b_global+1), plus a linear-time combinatorial (b_local+1)-approximation for Local ECC. The new LP relaxation for Robust ECC is the key move, and it fixes the infinite integrality gap of the prior relaxation. The Local ECC ratio was already known from LP rounding, but the linear-time primal-dual algorithm is new and genuinely useful, and the inapproximability results match the ratio, answering an open question. The reductions from Ek-Vertex-Cover are clean, and the integrality gap constructions are simple and correct.\n\nThe proofs mostly hold up under scrutiny. I checked the primal-dual accounting in Lemmas B.2, C.2, and D.2, and the dual feasibility arguments are sound. The Global ECC analysis has some algebra but the key invariant is legitimate. The hardness results rely on Bansal-Khot and Dinur et al., which is fine. The Theoretical claims are the strength here.\n\nSoft spots are minor but real. The \"essentially best possible\" claim for Local ECC is UGC-dependent; the paper says this clearly, and the P != NP version remains, so that is a caveat, not a flaw. The experiments are the weakest section. The relative error estimates are computed against the authors' own LP lower bound, and Section 4.1 asserts without proof that this relaxation always gives a better lower bound than Crane et al.'s. If that claim is false, the reported relative errors could flatter the proposed algorithms. The experimental comparison also lacks released code, which is a reproducibility issue, though not a mathematical one. There is also a small typo in C.5 where they say Crane et al.'s bicriteria algorithm \"provides a better performance guarantee\" right after proving their own has smaller violation; I assume they meant the opposite. None of this affects the theorems.\n\nOverall, this is a solid theory paper for the edge-colored clustering subfield. It resolves two open questions and the algorithms are at least as good as existing ones in practice, often better. The paper deserves serious peer review and should be accepted after minor revisions, mostly to tighten the experimental methodology and to fix that sentence in C.5.","headline":"A careful, genuinely useful theory paper: first true approximations for Robust and Global ECC, a clean linear-time primal-dual for Local ECC, and honest hardness/gap results; the experiments are the weakest part but the core is solid.","tokens_in":26459,"tokens_out":3022,"would_cite":true,"duration_ms":25792,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single primal-dual framework yields a linear-time optimal-ratio algorithm for Local ECC and the first true approximation algorithms for Robust and Global ECC.","keywords":["edge-colored clustering","hypergraph clustering","overlapping clustering","robust clustering","primal-dual approximation algorithms","integrality gap","inapproximability","linear-time algorithms"],"falsifier":"Enumerate all edge-colored hypergraphs on at most eight vertices, run the proposed algorithms with $b_{\\mathrm{local}}=1$ and $b_{\\mathrm{robust}}=0$, and compare each output against a brute-force optimal coloring; any instance whose mistakes exceed $(b_{\\mathrm{local}}+1)\\cdot\\mathrm{OPT}$ or $2(b_{\\mathrm{robust}}+1)\\cdot\\mathrm{OPT}$ refutes Theorems 3.1 and 3.5.","tokens_in":25501,"feed_emoji":"🧩","tokens_out":11081,"duration_ms":127132,"temperature":0.7,"pith_summary":"The paper tries to settle how well the three NP-hard variants of edge-colored clustering can be approximated without sacrificing speed. It claims that one LP-based combinatorial framework, built on the primal-dual method, achieves a $(b_{\\mathrm{local}}+1)$-approximation in linear time for Local ECC and the first true, non-bicriteria $2(b_{\\mathrm{robust}}+1)$- and $2(b_{\\mathrm{global}}+1)$-approximations for Robust and Global ECC. The same analysis proves matching integrality gaps and, for Local ECC, hardness showing the ratio is essentially best possible under the Unique Games Conjecture. If correct, this replaces budget-violating bicriteria algorithms, answers two open questions from the previous literature, and gives practical algorithms that the experiments show beat the prior greedy method for Local ECC while improving solution quality for Robust and Global ECC at a modest runtime cost.","feed_headline":"Clustering colored hypergraphs gets true approximation algorithms","feed_subtitle":"A primal-dual framework matches LP guarantees at combinatorial speed.","key_machinery":"The load-bearing mechanism is the primal-dual method run as a continuous-time dual increase process. The algorithms maintain a dual-feasible solution $\\alpha,\\beta,\\lambda$ and a set $L$ of loose edges—edges whose constraint $\\sum_{v\\in e} \\beta_{e,v} \\le w_e$ is not yet tight—and increase dual variables at rates controlled by the number of distinct colors among each vertex's incident loose edges, $|\\chi(\\delta(v)\\cap L)|$. The proof works by charging mistakes only to tight edges and comparing the rate at which the output cost grows to the rate at which the dual objective grows; that ratio is exactly what becomes the approximation factor. For Robust ECC, the key new LP constraint $z_v + \\sum_{c\\in C} x_{v,c} \\le 1$ couples deletion and coloring decisions and reduces the integrality gap from infinite to $\\Theta(b_{\\mathrm{robust}})$.","core_discovery":"The paper establishes that all three NP-hard variants of edge-colored clustering admit combinatorial approximation algorithms with LP-certified guarantees. For Local ECC, the proposed algorithm colors each vertex with the colors of its incident loose edges once edge constraints go tight; every mistake is a tight edge, so the output cost can be charged against the dual of a natural LP relaxation, yielding a $(b_{\\mathrm{local}}+1)$-approximation in linear time, an integrality gap converging to the same value, and UGC-based inapproximability matching it. For Robust ECC and Global ECC, a strengthened LP relaxation—the addition of the per-vertex constraint $z_v + \\sum_{c\\in C} x_{v,c} \\le 1$ in the robust case—repairs an integrality gap that was previously infinite and makes possible the first true approximation algorithms, with ratios $2(b_{\\mathrm{robust}}+1)$ and $2(b_{\\mathrm{global}}+1)$. The paper also establishes bicriteria versions whose violation factors are $O(1)$, resolving the previously open question of whether Global ECC admits constant-factor, constant-violation approximation.","pith_inferences":["Because the approximation ratios depend on per-vertex color degree rather than hypergraph rank, one predicts the algorithms will scale well on high-rank hypergraphs such as recipe or co-purchase data; this is testable on the benchmarks with rank far above 2.","The strengthened robust LP constraint suggests a transferable recipe for other outlier-tolerant clustering problems, such as robust correlation clustering, where deletion and labeling decisions are usually handled separately.","A natural next step is to ask whether the factor-two gap between the Local ratio $b_{\\mathrm{local}}+1$ and the Robust/Global ratios $2(b_{\\mathrm{robust}}+1)$ and $2(b_{\\mathrm{global}}+1)$ can be closed by dual fitting or local search; the paper does not address this.","The paper's final remark that the Local ECC algorithm is online could be developed into a streaming version with bounded memory; that extension is only implicit."],"forward_implications":["Local ECC is now settled up to a $(b_{\\mathrm{local}}+1)$ ratio: the algorithm runs in linear time and, under UGC, no polynomial-time algorithm improves on the ratio.","Robust ECC no longer requires bicriteria algorithms that may exceed the deletion budget; a true $2(b_{\\mathrm{robust}}+1)$-approximation exists.","Global ECC has both a true $2(b_{\\mathrm{global}}+1)$-approximation and a bicriteria guarantee with constant factor and constant budget violation, answering the open question.","The benchmark experiments show the Local ECC algorithm beating the previous greedy algorithm in speed and solution quality, and the Robust/Global algorithms producing better solutions while strictly respecting budgets."],"supporting_citations":[{"why":"defines Local, Global, and Robust ECC, supplies the prior greedy and LP-rounding algorithms, the benchmark datasets, and the two open questions answered here.","marker":"[19]"},{"why":"provides the UGC-hardness for uniform hypergraph vertex cover used in the reduction that rules out a $(b_{\\mathrm{local}}+1-\\epsilon)$-approximation for Local ECC.","marker":"[10]"},{"why":"provides the P≠NP-based hardness for uniform hypergraph vertex cover that yields the weaker inapproximability result for Local ECC.","marker":"[23]"},{"why":"introduces the primal-dual method for approximation algorithms on which the proposed framework is based.","marker":"[29]"},{"why":"supplies the general primal-dual algorithmic template for constrained optimization that the algorithms follow.","marker":"[30]"},{"why":"gives the continuous-time 'increase dual variables until an event occurs' perspective used to define and analyze the algorithms.","marker":"[31]"},{"why":"supplies the linear-time selection subroutine that makes the Local ECC algorithm run in linear time.","marker":"[13]"}],"fun_headline_variants":["Fast provable clustering for colored hypergraphs","LP + combinatorics: fast clustering with guarantees","Overlapping and robust clustering gets true algorithms","Two open questions resolved in edge-colored clustering","Primal-dual speed for clustering colored hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the Unique Games Conjecture, a widely used hardness-of-approximation assumption imported through the cited hypergraph vertex-cover result; if the conjecture fails, the claim that the Local ECC ratio is essentially best possible loses its support, though the positive algorithms and the P≠NP-based hardness remain intact.","fun_headline_variants_meta":{"raw":{"variants":["Fast provable clustering for colored hypergraphs","LP + combinatorics: fast clustering with guarantees","Overlapping and robust clustering gets true algorithms","Two open questions resolved in edge-colored clustering","Primal-dual speed for clustering colored hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000312,"raw_usage":{"total_tokens":1814,"prompt_tokens":1022,"completion_tokens":792,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":733}},"tokens_in":638,"tokens_out":792,"duration_ms":5985,"temperature":1.0,"reasoning_tokens":733,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:36:59.514526+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all edge-colored hypergraphs on at most eight vertices, run the proposed algorithms with $b_{\\mathrm{local}}=1$ and $b_{\\mathrm{robust}}=0$, and compare each output against a brute-force optimal coloring; any instance whose mistakes exceed $(b_{\\mathrm{local}}+1)\\cdot\\mathrm{OPT}$ or $2(b_{\\mathrm{robust}}+1)\\cdot\\mathrm{OPT}$ refutes Theorems 3.1 and 3.5.","supporting_citations":[{"cited_title":"Overlapping and robust edge-colored clustering in hypergraphs","cited_arxiv_id":null,"evidence_quote":"defines Local, Global, and Robust ECC, supplies the prior greedy and LP-rounding algorithms, the benchmark datasets, and the two open questions answered here."},{"cited_title":"Inapproximability of hypergraph vertex cover and applications to scheduling problems","cited_arxiv_id":null,"evidence_quote":"provides the UGC-hardness for uniform hypergraph vertex cover used in the reduction that rules out a $(b_{\\mathrm{local}}+1-\\epsilon)$-approximation for Local ECC."},{"cited_title":"A new multilayered PCP and the hardness of hypergraph vertex cover","cited_arxiv_id":null,"evidence_quote":"provides the P≠NP-based hardness for uniform hypergraph vertex cover that yields the weaker inapproximability result for Local ECC."},{"cited_title":"A general approximation technique for constrained forest problems","cited_arxiv_id":null,"evidence_quote":"introduces the primal-dual method for approximation algorithms on which the proposed framework is based."},{"cited_title":"Goemans and David P","cited_arxiv_id":null,"evidence_quote":"supplies the general primal-dual algorithmic template for constrained optimization that the algorithms follow."},{"cited_title":"A primal-dual bicriteria distributed algorithm for capacitated vertex cover","cited_arxiv_id":null,"evidence_quote":"gives the continuous-time 'increase dual variables until an event occurs' perspective used to define and analyze the algorithms."},{"cited_title":"Linear time bounds for median computations","cited_arxiv_id":null,"evidence_quote":"supplies the linear-time selection subroutine that makes the Local ECC algorithm run in linear time."}],"review_version":1}