{"id":"393a214b-61cd-4411-b2c9-63bc1582b7e2","arxiv_id":"1908.04141","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An engineered branch-and-reduce solver with data reductions is orders of magnitude faster than an ILP on multiterminal cut, but a key reduction's proof has a serious gap.","lead":"This paper presents a fast exact algorithm for the multiterminal cut problem, which splits a graph into k parts each holding one designated terminal while cutting the fewest edge weights. It combines graph-shrinking rules with search and integer programming, reporting speedups of up to four orders of magnitude over the previous standard approach.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"HighConnectivity reduction is load-bearing and its proof is invalid: Appendix A's Claim 2 is false and Lemma 3's proof contains a false equality, so exactness is unproven as written.","rationale":"The paper is a serious engineering effort with standard reductions and a branch-and-reduce framework, and some of the smaller reductions are clearly safe. However, the central theoretical linchpin is the HighConnectivity rule: if it is unsafe, the returned 'exact' cut can be suboptimal, invalidating both the exactness and the 'fastest known exact' claims. The reader correctly identified this as the weakest assumption. Our independent reading of Appendix A confirms the proof is invalid: Claim 2 fails already in the k=2 case, and the proof of Lemma 3 contains a false equality involving the sum of block degrees after removing the two largest values. These are not merely typos in a peripheral lemma; the reduction is used in the main experiments of Section 8.5. We also note that our own analysis of the k=3 case suggests Lemma 3 may be salvageable, so the concern is a missing proof rather than a demonstrated counterexample. That distinction does not change the verdict: the submitted manuscript does not establish correctness, and the absence of released code or data prevents the experiments from independently certifying that HighConnectivity never changes the optimum. The current version should remain rejected, though conditional acceptance would be reasonable if the authors supply a correct proof and ideally the code.","tokens_in":16566,"tokens_out":39962,"duration_ms":413784,"concrete_test":"Enumerate all connected weighted graphs with n<=7 and k=3,4 terminals; for every edge (u,v), compute lambda(u,v), all isolating cuts lambda_i, and the optimum W(G) by brute force, and check whether lambda(u,v)+sum_{i not in top2}lambda_i/4 > W holds while (u,v) are separated in every optimal multiterminal cut. If such an instance exists, HighConnectivity can contract an unsafe edge and the exactness claim fails; if none exists, the reduction is empirically safe and the remaining issue is the missing corrected proof of Lemma 3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exactness claim depends on the HighConnectivity rule (Section 4.1, Eq. 1), which contracts edges when a connectivity lower bound satisfies Eq. 1. The rule's safety rests entirely on Lemma 3, whose proof in Appendix A is not valid. Claim 2 is false: for k=2 with terminals s and t joined by an edge of weight 10, we have W=10, lambda(s,t)=10, and delta_s=delta_t=10, so Claim 2 would require 10 + (10+10)/4 = 15 <= 10. The proof of Lemma 3 also contains the false equality sum_{i not in max2} delta(R(t_i))/2 = W(G); the sum omits the two largest block degrees, so it cannot equal W. These are not cosmetic slips: the reduction is enabled in the main speedup experiments (Section 8.5), and no code or data is released, so the experiments cannot independently establish that HighConnectivity never discards the optimum. Even if a correct proof of Lemma 3 exists, the submitted manuscript does not provide one, and the 'exact algorithm' claim is therefore unsubstantiated as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript presents a shared-memory branch-and-reduce algorithm for the NP-hard multiterminal cut problem. It combines known and newly engineered kernelization rules (Low, High, Triangle, and a new HighConnectivity rule) with edge-branching, a priority-queue problem ordering, shared-memory parallelism, and a hybrid that first kernelizes and then solves the reduced instance with an ILP. The experimental sections report speedups of up to three orders of magnitude over a Gurobi ILP baseline, report termination with optimal solutions on graphs with more than a million vertices, and include component ablations for branching rules, queue comparators, and kernelization variants.","tokens_in":16801,"tokens_out":14850,"duration_ms":159073,"significance":"If the exactness guarantees were established, this would be a significant practical contribution to exact multiterminal cut solving: it would provide the first implemented parameterized-style exact solver on large graphs, with a careful experimental comparison and a clear separation of reduction and ILP components. The paper deserves credit for the breadth of experiments, the explicit evaluation of algorithmic choices, and the fact that no parameters are fitted to the reported data. However, the central exactness claim rests on Lemma 3, whose proof in Appendix A is invalid; the appendix contains inequality steps that do not follow and a false equality. Until a correct proof is supplied, the claimed exactness and the 'fastest known exact algorithm' statement are not yet substantiated.","major_comments":[{"comment":"The derivation of Claim 2 from Claim 1 is invalid. Claim 1 states lambda(u,v) <= (1/4) * sum_i delta(R(t_i)) + (delta(R(u)) + delta(R(v))) / 4. Adding (1/4) * sum_i delta(R(t_i)) to both sides gives lambda(u,v) + (1/4) * sum_i delta(R(t_i)) <= (1/2) * sum_i delta(R(t_i)) + (delta(R(u)) + delta(R(v))) / 4, not the claimed bound (1/2) * sum_i delta(R(t_i)). The claimed bound is also false as stated: for k=2 with terminals s and t joined by an edge of weight 10, W=10, lambda(s,t)=10, and delta_s = delta_t = 10, so Claim 2 would require 10 + (10+10)/4 = 15 <= 10. Consequently, the safety of the HighConnectivity contraction rule, which is used in Eq. (1), is not proven.","section":"Section 4.1 and Appendix A, Claim 2"},{"comment":"The final equality in the proof of Lemma 3, sum_{i not in max2} delta(R(t_i)) / 2 = W(G), is false. By definition, W(G) = (1/2) * sum_{i=1}^k delta(R(t_i)) in the weighted quotient graph, since each cut edge is counted from both of its endpoint blocks. Omitting the two largest terms from the sum makes the left-hand side strictly smaller than W(G) whenever those terms are positive. Thus the displayed chain of inequalities in the proof of Lemma 3 does not establish the lemma, and the HighConnectivity reduction is not justified as written.","section":"Appendix A, proof of Lemma 3"},{"comment":"The main speedup experiments enable all kernelization rules, including HighConnectivity, and the performance claims in Section 8.5, including solving instances with more than a million vertices, are presented as exact optimal solutions. Since the only proof of HighConnectivity safety is invalid and no code or data are released, the experimental results cannot independently establish that the algorithm never returns a suboptimal cut. The abstract's claim of a fastest known exact algorithm is therefore unsubstantiated as written.","section":"Sections 8.4 and 8.5"}],"minor_comments":[{"comment":"The notation |W(G)| is confusing because W(G) is already a numeric weight; the absolute-value bars are unexplained and should be removed.","section":"Section 4.1, Lemma 3"},{"comment":"The description of the UpperBound comparator says it 'first examines problems with a lower bound'; this should presumably read 'with a lower upper bound' or a similarly explicit description.","section":"Section 8.3"},{"comment":"The phrase 'We use multiple set a instances' appears to be a typo; it should likely read 'We use multiple sets of instances'.","section":"Section 8.1.1"},{"comment":"The caption 'Solid line cannot be minimal as dashed line has smaller weight' is too terse; it would be clearer to state which edges are being compared and in which cases.","section":"Figure 2 caption"},{"comment":"The claim that in the subproblem G/e the lower bound strictly increases because the edge e was part of the largest isolating cut of the terminal s deserves a more detailed argument; as written it is not immediate that no other minimum s-T-cut can be decreased.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The core issue is the invalid proof of Lemma 3 in Appendix A. If the authors can supply a correct proof of the lemma, or alternatively remove the HighConnectivity rule from the claimed exact algorithm and rerun the experiments without it, I would be willing to reconsider. Without either, the exactness claim cannot stand."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the stress-test lands. The HighConnectivity reduction is load-bearing, and the Appendix A proof of Lemma 3 does not hold. Claim 2 is false as stated: for k=2 with an edge of weight 10 between the two terminals, λ=10, δ=10 for each terminal, and the claimed inequality becomes 15 ≤ 10. The proof of Lemma 3 also contains a false equality: sum over all but the two largest δ(R(t_i))/2 is not W(G). This is not a cosmetic slip. The reduction is used in the main speedup experiments, and an unsafe contraction can remove the optimal cut. So the 'exact algorithm' claim is not established in this manuscript.\n\nThat said, the paper has real value. The engineering is substantial: a branch-and-reduce framework, the new SemiEnclosed reduction, the priority-queue comparators, and the coupling of kernelization with an ILP are legitimate contributions. The experiments are extensive — several graph families, varying k and terminal ratios, ILP baselines, parallel scaling — and the reported speedups are large. The citation pattern is fair; self-citations point to standard max-flow/min-cut subroutines, not to a circular dependency. There are no fitted parameters and no invented entities.\n\nThe soft spots are the lemma proof and the lack of released code/data. The missing artifact is secondary but relevant: without code or data, the empirical claim that HighConnectivity never discards the optimum cannot be independently checked, and the experiments are the only evidence for exactness. Some of the notation in the appendix is sloppy, but that is not the main issue.\n\nThis paper is for researchers working on practical exact algorithms for multiterminal cut or on kernelization for NP-hard cut problems. If Lemma 3 is repaired, the paper will be a useful reference. As written, I would not cite it for the exactness claim, and I would not trust the headline result until the reduction is proven or removed.\n\nRecommendation: send it to peer review, but with the expectation of major revision. The ideas deserve referee time. A serious referee should ask for a correct proof of Lemma 3 (or a version without HighConnectivity) and ideally for code or data.","headline":"HighConnectivity reduction is load-bearing and its proof is invalid—exactness claim unproven, but the engineering and experiments deserve a serious referee.","tokens_in":17287,"tokens_out":4247,"would_cite":false,"duration_ms":42178,"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":"This paper claims that a branch-and-reduce algorithm with new and existing reduction rules is the fastest known exact solver for multiterminal cuts, solving graphs with more than a million vertices.","keywords":["multiterminal cut","multiway cut","branch-and-reduce","kernelization","data reduction","graph cut","exact algorithm","integer linear programming"],"falsifier":"Run the HighConnectivity rule on every small graph with, say, up to ten vertices and three or four terminals, comparing its contractions against all optimal cuts computed by brute force; any instance in which the rule contracts an edge that every optimal cut separates would invalidate Lemma 3 and collapse the exactness claim.","tokens_in":16366,"feed_emoji":"✂️","tokens_out":8405,"duration_ms":84167,"temperature":0.7,"pith_summary":"The paper tries to establish that exact minimum multiterminal cut problems, which are NP-hard for three or more terminals, can be solved in practice on far larger graphs than the standard integer-linear-programming approach allows. Its route is a branch-and-reduce algorithm wrapped around a stack of data-reduction rules: low-degree vertices are contracted, heavy edges and triangles are contracted, semi-enclosed vertices are merged into a terminal, and a new high-connectivity rule contracts edges that provably lie inside one block of some optimum. The same reductions also form a kernelization step that shrinks the graph before an ILP solves it. On the testbed the branch-and-reduce algorithm is a mean of 67 times faster than the plain ILP on instances both solve, and it solves real graphs with over a million vertices that the ILP cannot finish. If every reduction preserves at least one optimal solution, the result is a practical exact solver that replaces the ILP as the default for this problem.","feed_headline":"Exact multiterminal cuts, up to 1000x faster","feed_subtitle":"New reduction rules shrink graphs while preserving an optimal cut, beating the standard ILP by orders of magnitude.","key_machinery":"The engine is the branch-and-reduce loop over a queue of independent subproblems, where each subproblem is either reduced or branched on an edge incident to a terminal. Two dual operations carry the argument: contract an edge that is guaranteed not to be in at least one optimal cut, and delete (with weight bookkeeping) an edge that is guaranteed to be in every optimal cut. The new rule, HighConnectivity, uses Lemma 3: for an edge $(u,v)$, if $\\lambda(u,v) + \\sum_{i\\in\\{1,\\dots,k\\}\\setminus\\mathrm{max2}} \\lambda(G,t_i,T\\setminus\\{t_i\\})/4 > \\hat{W}(G)$, then $u$ and $v$ lie in the same block of an optimal solution, so the edge is contracted; a near-linear-time lower-bound routine makes the condition checkable for every edge. The isolating cuts $\\lambda(G,t_i,T\\setminus\\{t_i\\})$ supply both the upper-bound heuristic (sum of all but the largest isolating cuts) and the lower bounds that prune branches. A shared-memory queue lets multiple threads pull independent subproblems, yielding additional parallel speedup.","core_discovery":"The central claim is that minimum multiterminal cut admits an exact algorithm whose practical running time is no longer dominated by the ILP. The paper shows that a battery of contraction and deletion rules, most inherited from minimum-cut preprocessing and one new HighConnectivity rule, reduce the graph while guaranteeing that at least one optimal multiterminal cut survives. Whenever the connectivity lower bound of an edge plus the sum of all but the two largest isolating-cut values divided by four exceeds the current upper bound, the endpoints are in the same block of an optimal cut and the edge can be contracted. With these rules inside a branch-and-reduce search, the algorithm solves more instances to proven optimality than the ILP, and with the rules used as a kernelizer, the ILP itself becomes competitive on the reduced graph. The paper's performance claim is therefore twofold: the reductions are safe, and their engineering makes exact multiterminal cuts tractable at million-vertex scale.","pith_inferences":["As an editorial extension, the local reductions do not depend on knowing the full terminal structure, so they could be dropped into other exact frameworks, such as branch-and-cut or the FPT algorithms, to shrink any instance before deeper search.","The observed complementarity between cut-value-sensitive search and kernel-size-sensitive ILP points toward an adaptive hybrid that routes each subproblem to the cheaper solver; the paper does not implement this mixed dispatch.","The HighConnectivity inequality is stated through isolating-cut values only, so a natural testable extension is whether an analogue holds for node-weighted or directed multiway cut when a directed isolating-cut bound exists.","The speedups on real networks suggest that the reduction rules may also improve practical approximation algorithms, since a smaller graph with preserved optimal structure is easier for any downstream solver."],"forward_implications":["Optimal multiterminal cuts can be certified on graphs with more than a million vertices, a scale at which the plain ILP baseline never terminates.","The kernelized ILP inherits the same speedups when the reduced kernel is small but the cut value is large, which the experiments show on protein-protein interaction networks.","The branch-and-reduce variant is most efficient when the optimal cut value is small, so the two exact solvers cover complementary regimes of instance structure.","If the HighConnectivity reduction is safe on all graphs, the fixed-parameter tractable algorithms for multiterminal cut become deployable in practice rather than remaining purely theoretical."],"supporting_citations":[{"why":"Supplies the contraction and deletion rules (Lemmas 1 and 2) and the FPT algorithm that the kernelization reuses.","marker":"[7]"},{"why":"Defines the problem, proves NP-hardness, and establishes that isolating cuts can be kept inside optimal blocks, the basis for the upper-bound heuristic.","marker":"[12]"},{"why":"Gives the edge-contraction conditions for minimum cuts that the paper adapts into HeavyEdge and HeavyTriangle reductions.","marker":"[32]"},{"why":"Extends the same contraction conditions and provides the near-linear-time routines behind the connectivity lower bounds.","marker":"[33]"},{"why":"Supplies the local sufficient conditions for contracting edges while preserving a global minimum cut, adapted here to multiterminal cuts.","marker":"[34]"},{"why":"Provides the efficient implementation of those contraction conditions that the paper builds on for its reduction passes.","marker":"[23]"},{"why":"Contributes the ILP formulation that the paper uses as baseline and as the solver after kernelization.","marker":"[20]"},{"why":"Documents ILP as the de facto practical way to solve multiterminal cuts and supplies the protein-function prediction application domain.","marker":"[31]"}],"fun_headline_variants":["Exact cuts, orders-of-magnitude speedup","New reductions make multiterminal cuts tractable","Million-vertex cuts solved exactly","Reduce, branch, and cut faster","Speeding up exact multiterminal cuts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands or falls on whether the new high-connectivity contraction rule is truly safe: that whenever its test passes, the two endpoints lie in the same piece of some optimal solution.","fun_headline_variants_meta":{"raw":{"variants":["Exact cuts, orders-of-magnitude speedup","New reductions make multiterminal cuts tractable","Million-vertex cuts solved exactly","Reduce, branch, and cut faster","Speeding up exact multiterminal cuts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":9.7e-05,"raw_usage":{"total_tokens":941,"prompt_tokens":815,"completion_tokens":126,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":431,"completion_tokens_details":{"reasoning_tokens":58}},"tokens_in":431,"tokens_out":126,"duration_ms":2169,"temperature":1.0,"reasoning_tokens":58,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:52:24.511277+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the HighConnectivity rule on every small graph with, say, up to ten vertices and three or four terminals, comparing its contractions against all optimal cuts computed by brute force; any instance in which the rule contracts an edge that every optimal cut separates would invalidate Lemma 3 and collapse the exactness claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the contraction and deletion rules (Lemmas 1 and 2) and the FPT algorithm that the kernelization reuses."},{"cited_title":"Dahlhaus, D","cited_arxiv_id":null,"evidence_quote":"Defines the problem, proves NP-hardness, and establishes that isolating cuts can be kept inside optimal blocks, the basis for the upper-bound heuristic."},{"cited_title":"Nagamochi and T","cited_arxiv_id":null,"evidence_quote":"Gives the edge-contraction conditions for minimum cuts that the paper adapts into HeavyEdge and HeavyTriangle reductions."},{"cited_title":"Nagamochi, T","cited_arxiv_id":null,"evidence_quote":"Extends the same contraction conditions and provides the near-linear-time routines behind the connectivity lower bounds."},{"cited_title":"Padberg and G","cited_arxiv_id":null,"evidence_quote":"Supplies the local sufficient conditions for contracting edges while preserving a global minimum cut, adapted here to multiterminal cuts."},{"cited_title":"Henzinger, S","cited_arxiv_id":null,"evidence_quote":"Provides the efficient implementation of those contraction conditions that the paper builds on for its reduction passes."},{"cited_title":"Henzinger, A","cited_arxiv_id":null,"evidence_quote":"Contributes the ILP formulation that the paper uses as baseline and as the solver after kernelization."},{"cited_title":"Nabieva, K","cited_arxiv_id":null,"evidence_quote":"Documents ILP as the de facto practical way to solve multiterminal cuts and supplies the protein-function prediction application domain."}],"review_version":1}