{"id":"18c1e5c1-13d8-497e-b36a-0b6c7dcc2900","arxiv_id":"2504.19842","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"HeiCut combines exact hypergraph reductions with a relaxed binary integer program to compute near-optimal minimum cuts in large hypergraphs, reporting exact cuts on over 85% of tested instances.","lead":"HeiCut is a new solver for the hypergraph minimum cut problem that shrinks the input with contraction rules claimed to preserve the optimum, then solves a relaxed integer program on the remainder. On over 500 real-world hypergraphs the authors report exact cuts in more than 85% of instances and speedups of up to five orders of magnitude over a reimplemented state-of-the-art baseline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 returns λ=0 whenever all hyperedges are contracted away, which is wrong even for a single weighted hyperedge; this breaks the exactness claim as written.","rationale":"The reader identified a missing invariant about reductions destroying minimum cuts and the pipeline not combining λhat with the BIP result. The two-vertex single-edge counterexample shows this is not merely an unproved invariant: the published Algorithm 1 has a concrete branch that returns a value provably different from the input's minimum cut. Any exactness or near-exactness claim fails on this instance. The fix is simple in spirit—always return min(λhat, reduced optimum), or return λhat when the reduction is fully collapsed—but it must appear in pseudocode, implementation, and correctness proof. Until that is done, the central claim 'exact reductions alone compute the exact minimum cut in over 85% of instances' is not supported, because the algorithm as written can return 0 on instances with positive minimum cut.","tokens_in":15127,"tokens_out":9206,"duration_ms":106902,"concrete_test":"Execute Algorithm 1 exactly as written on H=({u,v}, {e={u,v}}) with ω(e)=5 and no other hyperedges. Trace: λhat=5; Rule 2 contracts e because 5≥5; the reduced hypergraph has |E|=0, so line 10 returns 0. Compare with the independently computed true minimum cut 5. If the implementation instead returns 5 or λhat in this case, then the pseudocode misstates the implemented algorithm and the exactness claim depends on that undocumented correction, which should still be stated and proved.","verdict_should_be":"REJECT","load_bearing_attack":"The pseudocode and the proof of Reduction Rule 2 combine to produce an incorrect output on a trivial valid instance. Let H have vertices {u,v}, one hyperedge e={u,v} with weight ω(e)=5, and no other hyperedges. The true minimum cut value is λ(H)=5, realized by either singleton cut. Algorithm 1 initializes λhat←min_v dω(v)=5. Reduction Rule 2 applies because |e|=2 and ω(e)=5≥λhat. After contracting e, H has one vertex w, zero hyperedges, and δω(H)=0, so λhat is updated to 0. Then line 10 fires: |E|=0, so the algorithm returns λ←0. This is not the minimum cut of the input hypergraph. The proof of Rule 2 only establishes that a cut crossing e has value at least λhat; when the true minimum equals λhat, every minimum cut may cross e, so contracting e and outputting the reduced graph's min cut is unsafe. The algorithm must retain λhat as a candidate answer, e.g., return min(λhat, SolveRelaxedBIP(H)) or return λhat upon full reduction. As written, the fully-reduced branch discards the only correct upper bound and returns a value that can be arbitrarily far from the true cut. This is a sharper, concretely falsifying instance of the reader's concern: the pipeline's final output does not combine the maintained upper bound with the reduced-instance optimum.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents HeiCut, a solver for the (near-optimal) minimum cut problem in weighted and unweighted hypergraphs. HeiCut interleaves seven contraction rules, some adapted from graph algorithms and some novel for hypergraphs, with an optional label-propagation heuristic, and then solves a relaxed binary integer program (BIP) on the reduced hypergraph. The authors report that the exact reductions alone fully reduce 85--95% of the instances in the MHG and LHG benchmarks, and that HeiCut outperforms a reimplementation of the Chekuri--Xu Trimmer algorithm and a standalone Gurobi-based relaxed BIP on more than 500 real and synthetic instances, by up to five orders of magnitude in runtime.","tokens_in":15404,"tokens_out":18862,"duration_ms":181968,"significance":"If the correctness issues described below are repaired, this is a useful algorithmic-engineering contribution: it combines safe-contraction ideas with a relaxed BIP to extend the scale on which hypergraph minimum cuts can be computed, and it provides a broad benchmark, including a new synthetic k-core family, with three baselines. The paper is honest that the BIP relaxation is inexact, and the experimental evaluation is broad and internally consistent. The exactness claims for the reduction rules are, however, load-bearing and currently not supported by the pseudocode and proofs as written.","major_comments":[{"comment":"The algorithm returns the wrong value on a trivial instance. Let H have V={u,v}, one hyperedge e={u,v} with omega(e)=5, and no other hyperedges. The true minimum cut is lambda(H)=5. The algorithm initializes lambda_hat to min_v d_omega(v)=5, Reduction Rule 2 applies because omega(e)>=lambda_hat, and after contracting e the hypergraph has one vertex and no hyperedges. Line 9 then sets lambda_hat <- min(5, delta_omega(H))=0, and line 10 fires, returning lambda=0. This is not even a valid cut value of the input hypergraph. The update in line 9 is invalid when the reduced hypergraph has one vertex, because the singleton 'cut' of a one-vertex hypergraph corresponds to the empty or full vertex set of the original hypergraph. The fully-reduced branch must not return 0 before considering the case |V|=1, and lambda_hat must not be lowered using a one-vertex reduced graph.","section":"Algorithm 1, lines 9-13"},{"comment":"The proofs of Rules 2, 3, and 7 only establish that a cut crossing the contracted structure has value at least lambda_hat. They do not establish that every minimum cut of the original hypergraph is represented by a minimum cut of the reduced hypergraph, and the final output can therefore be strictly larger than the true optimum. Concretely, take vertices a,b,c,d,e with hyperedges {a,b} of weight 5, {a,c} of weight 10, and {c,d}, {d,e}, {e,c} of weight 6. The minimum cut is 5, realized by {b} versus the rest, and lambda_hat = d_omega(b)=5. Rule 2 contracts {a,b}, producing a reduced hypergraph whose minimum cut is 10 (the cut {w} versus {c,d,e}, where w is the contracted vertex). Since line 15 returns SolveRelaxedBIP(H) rather than min(lambda_hat, SolveRelaxedBIP(H)), HeiCut would report 10. The correct invariant for this style of contraction is that every cut of value strictly below lambda_hat survives, and the output must be the minimum of the maintained upper bound and the reduced-instance optimum. As written, the final solution of the reduced instance is used alone, which contradicts the claim that the reductions preserve the minimum cut.","section":"Section 3.1, Reduction Rule 2; Algorithm 1, line 15"},{"comment":"The statement that the reductions 'provably preserve the value of the minimum cut' is too strong for the rules as proved. The text says contractions preserve correctness because 'any minimum cut of the reduced hypergraph remains valid on the input hypergraph'; the counterexample in the previous comment shows this implication fails. What the proofs support is the weaker and standard statement that no cut of value less than lambda_hat is destroyed. This distinction matters for the claimed exactness of the 85-95% of instances that are fully reduced: for those instances the algorithm currently returns either 0 or the relaxed-BIP value of the reduced hypergraph, not the maintained upper bound. The experiments should be re-examined after fixing the algorithm to see how many instances were affected by this bug.","section":"Section 3.1, first paragraph; Section 4.1"}],"minor_comments":[{"comment":"The relaxed BIP section should explicitly state that no approximation guarantee is claimed for the rounding step; the sentence 'the practical difference is negligible' is an empirical observation, not a theorem, and should be phrased as such.","section":"Section 3.2"},{"comment":"There is a typo in 'fiveorders of magnitude'; a space is missing.","section":"Abstract"},{"comment":"The paragraph 'If the hypergraph is reduced to a single vertex or a set of isolated vertices, the minimum cut value has been determined' should be qualified: for a set of isolated vertices the value is 0, while for a single vertex after contractions the value is lambda_hat, not 0.","section":"Section 3.1"},{"comment":"Because Trimmer is a reimplementation without a public reference implementation, it would strengthen the paper to state clearly which parts of the comparison could be affected by implementation differences, and to make the HeiCut and Trimmer code available at least as supplementary material.","section":"Section 4, Baselines"}],"recommendation":"major_revision","confidential_remarks":"The counterexample in the first major comment is real and appears in the simplest possible instance, so the correctness issue cannot be dismissed as an implementation detail. The fix (carry lambda_hat to the final output and guard the one-vertex update) is local in scope, which is why I recommend major revision rather than rejection. The authors should also re-run the experiments after the fix and report whether the 85-95% 'exact without BIP' numbers change."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this one for the reductions and the benchmark, not for the correctness proof as written. The paper has a concrete bug: on a hypergraph with vertices {u,v} and one hyperedge of weight 5, Rule 2 contracts the edge (since 5 ≥ λ̂ = 5), leaving one isolated vertex and zero hyperedges. Line 10 then fires and returns λ = 0. The true minimum cut is 5. The fully-reduced branch throws away the only valid upper bound. The fix is trivial — return min(λ̂, SolveRelaxedBIP(H)) everywhere, or return λ̂ on full reduction — but as written the exactness claim is false.\n\nThat said, there is real substance here. Rules 3 (HeavyOverlap) and 4 (NestedSubstructure) are genuinely hypergraph-specific and new, and the idea of using a maintained upper bound to drive aggressive contractions is sensible. The evaluation is broad — over 500 instances, three baselines, performance profiles — and the new (k,2)-core synthetic benchmark is a useful contribution for future work. The paper is also honest about the relaxed BIP being inexact; the \"near-optimal\" framing is not overstated.\n\nThe softer problems: the proofs for Rules 2, 3, and 7 only show that a cut crossing the contracted structure has value at least λ̂; they never explicitly argue that a minimum cut avoiding the contracted set exists. The counterexample above shows this is not a pedantic gap — the invariant is genuinely needed. The Trimmer baseline is a reimplementation without public code, which weakens the state-of-the-art comparison slightly, though the authors disclose this. Code is promised only on acceptance.\n\nBottom line: the empirical story is plausible and the engineering is solid, but the load-bearing correctness claim has a hole. A serious referee should ask for the simple fix plus a proper invariant-style proof that the reductions preserve at least one minimum cut. If that lands, this becomes a very useful paper. I would not cite the exactness claim in its current form, but I would keep it on the reading list to discuss the counterexample and the reduction rules.\n\nRecommendation: send to peer review, but expect major revision before acceptance.","headline":"A genuinely useful engineering paper with a real correctness bug in the fully-reduced branch: as written, Algorithm 1 returns 0 on a single weighted hyperedge, so the exactness claim needs a fix before the results can be trusted.","tokens_in":15947,"tokens_out":1649,"would_cite":false,"duration_ms":17387,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A new solver, HeiCut, claims that exact contraction rules guided by an upper bound can find the minimum cut of most real hypergraphs directly, with a relaxed binary program covering the rest.","keywords":["HeiCut","hypergraph minimum cut","exact reductions","contraction rules","relaxed binary integer program","label propagation","cut enumeration","large-scale hypergraph analysis"],"falsifier":"Enumerate all small hypergraphs (say, up to seven vertices with unit or small integer weights), compute the true minimum cut by brute force, and run HeiCut's exact-reduction pipeline on each; any instance where the reduced hypergraph's minimum cut exceeds the original minimum cut—especially one where Rule 2 contracts a hyperedge of weight exactly $\\hat{\\lambda}$ while the unique minimum cut separates its endpoints—would falsify the claim that the reductions are exact.","tokens_in":14911,"feed_emoji":"✂️","tokens_out":7721,"duration_ms":72755,"temperature":0.7,"pith_summary":"HeiCut is a solver for the hypergraph minimum cut problem—splitting vertices into two nonempty blocks to minimize the total weight of hyperedges crossing the split. The paper claims that a small set of provably exact contraction rules, guided by an upper bound $\\hat{\\lambda}$ on the minimum cut, shrinks most real hypergraphs to a trivial instance: in over 85% of the 500+ tested instances the exact minimum cut is found by reduction alone. Only when reductions stall does HeiCut solve a relaxed binary integer linear program on the reduced hypergraph, producing a near-optimal cut. If these claims hold, HeiCut makes exact or near-exact hypergraph min-cuts practical on instances that previous solvers cannot finish, while also handling weighted hypergraphs that the leading unweighted method cannot.","feed_headline":"Hypergraph min-cuts found exactly 85% of the time","feed_subtitle":"Exact reductions shrink most instances to triviality; a relaxed solver handles the rest, beating the prior state of the art.","key_machinery":"The load-bearing mechanism is the pair $(\\hat{\\lambda}, \\text{contraction rules})$: $\\hat{\\lambda}$, initialized to the minimum weighted vertex degree and tightened after each contraction, is the threshold below which a cut would have to be interesting. Each exact reduction rule identifies a set of vertices—a heavy hyperedge, an overlap of hyperedges, a nested substructure, or a graph-style heavy neighborhood—whose separation would force a cut of weight at least $\\hat{\\lambda}$, so contracting it cannot raise the true minimum cut. Three rules (ImbalancedVertex, ImbalancedTriangle, HeavyNeighborhood) come from the graph reduction literature and are applied to size-2 hyperedges; the paper notes one must use a strict inequality in ImbalancedVertex because a non-strict version can contract two equal-weight edges sharing a vertex and destroy the minimum cut. The final stage is a relaxed BIP on the reduced instance, which the reductions make unnecessary for most inputs.","core_discovery":"The paper's central claim is that aggressive but safe contraction can reduce hypergraph minimum cut computation to a tiny residual problem. HeiCut initializes an upper bound $\\hat{\\lambda}$ from the minimum weighted vertex degree and applies seven reduction rules—removing trivial hyperedges, contracting heavy hyperedges, heavy overlaps, nested substructures, and three rules adapted from graph cuts—each designed so that any cut crossing the contracted structure has value at least $\\hat{\\lambda}$ and therefore cannot improve on the best cut already known. On real-world and synthetic hypergraphs, this pipeline alone fully reduces 85–95% of instances, meaning the exact minimum cut is known without any optimization. For the remainder, a relaxed BIP (binary variables allowed to take near-binary float values, then rounded) computes a cut the experiments show matches the exact value on every instance where an exact baseline could be compared. The paper further claims that HeiCut solves over twice as many instances as the prior state of the art within fixed time and memory limits, and is up to five orders of magnitude faster.","pith_inferences":["If the reduction rules are as effective as reported, then the difficulty of hypergraph min-cut is concentrated in a small 'core' that survives contraction; studying the structure of those cores could yield even stronger reductions.","The near-exactness of the relaxed BIP suggests the LP relaxation of the cut formulation may be integral or near-integral on real instances; a systematic integrality-gap study on the reduced cores would be a natural next test.","The same reduction framework might transfer to related problems such as sparsest cut, s-t min-cut, or hypergraph clustering, since the reductions only rely on lower bounds for crossing cuts.","A formal invariant stating that every destroyed minimum cut is represented either by $\\hat{\\lambda}$ or by a cut in the reduced hypergraph would turn the empirical exactness into a theorem; Figure 2's counterexample shows the subtlety of such proofs."],"forward_implications":["Exact hypergraph minimum cuts become routinely computable on the 85–95% of instances that fully reduce, since no optimization solver is needed after contraction.","Weighted hypergraphs, which the previous k-trimmer baseline cannot handle, become solvable by the same pipeline.","On large hypergraphs, HeiCut scales to about twice as many instances as the state of the art under the same time and memory limits, and runs up to five orders of magnitude faster.","The label-propagation variant trades a little solution quality for lower memory on hard instances, and is faster than plain HeiCut on the synthetic (k,2)-core benchmark.","The new (k,2)-core hypergraph dataset gives future work instances where the minimum cut is genuinely smaller than the trivial degree cut."],"supporting_citations":[{"why":"Supplies the k-trimmer certificate algorithm and defines the Trimmer baseline that HeiCut must outperform.","marker":"[6]"},{"why":"VieCut is the source of the graph-based reduction rules (Rules 5–7) and the label-propagation contraction idea adapted here.","marker":"[14]"},{"why":"Padberg and Rinaldi provide the original correctness arguments behind the imbalanced-vertex, imbalanced-triangle, and heavy-neighborhood reductions.","marker":"[27]"},{"why":"The maximum-adjacency ordering is the exact solver engine used inside the Trimmer implementation and in hypergraph min-cut algorithms.","marker":"[25]"},{"why":"Provides the MHG and LHG benchmark hypergraph collections on which the experimental claims are measured.","marker":"[9]"},{"why":"One of the vertex-ordering based exact hypergraph min-cut solvers the paper builds on and compares with.","marker":"[24]"}],"fun_headline_variants":["HeiCut solves 85% of hypergraph min-cuts exactly","Exact hypergraph min-cuts up to 100,000x faster","Proven reductions shrink hypergraphs, speeding cuts","Over 85% exact min-cuts in hypergraphs via HeiCut","Scale hypergraph min-cuts with exact-safe reductions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"A contracted set might, in principle, be separated by every genuinely minimum cut, and the paper does not fully prove that this never happens; if it did, the reduced instance could have a larger minimum cut than the original hypergraph.","fun_headline_variants_meta":{"raw":{"variants":["HeiCut solves 85% of hypergraph min-cuts exactly","Exact hypergraph min-cuts up to 100,000x faster","Proven reductions shrink hypergraphs, speeding cuts","Over 85% exact min-cuts in hypergraphs via HeiCut","Scale hypergraph min-cuts with exact-safe reductions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1438,"prompt_tokens":934,"completion_tokens":504,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":415}},"tokens_in":550,"tokens_out":504,"duration_ms":5176,"temperature":1.0,"reasoning_tokens":415,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:44:47.469118+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all small hypergraphs (say, up to seven vertices with unit or small integer weights), compute the true minimum cut by brute force, and run HeiCut's exact-reduction pipeline on each; any instance where the reduced hypergraph's minimum cut exceeds the original minimum cut—especially one where Rule 2 contracts a hyperedge of weight exactly $\\hat{\\lambda}$ while the unique minimum cut separates its endpoints—would falsify the claim that the reductions are exact.","supporting_citations":[{"cited_title":"C omputing M inimum C uts in H ypergraphs","cited_arxiv_id":null,"evidence_quote":"Supplies the k-trimmer certificate algorithm and defines the Trimmer baseline that HeiCut must outperform."},{"cited_title":"Padberg and G","cited_arxiv_id":null,"evidence_quote":"Padberg and Rinaldi provide the original correctness arguments behind the imbalanced-vertex, imbalanced-triangle, and heavy-neighborhood reductions."},{"cited_title":"C omputing E dge-connectivity in M ultigraphs and C apacitated G raphs","cited_arxiv_id":null,"evidence_quote":"The maximum-adjacency ordering is the exact solver engine used inside the Trimmer implementation and in hypergraph min-cut algorithms."}],"review_version":1}