{"id":"67a46ad9-8b64-4f83-b5dd-3ba54e7ec12d","arxiv_id":"2607.07419","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"A deletion-based exact algorithm for maximum k-biplex search achieves worst-case time O*(γ_k^n) with γ_k < 2 and up to four orders of magnitude practical speedup over prior state-of-the-art.","lead":"The paper reframes the maximum k-biplex search as a vertex-deletion problem on the complement graph, yielding a new exact branch-and-bound algorithm with worst-case time complexity below O*(2^n). A smart generalist might read this to understand how a complementary perspective on an NP-hard graph problem can yield both theoretical improvements and massive practical speedups.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Worst-case analysis in Theorem 5 Case 1 relies on an unproven structural claim about complement-graph adjacency that may not always hold, potentially affecting the stated γ_k values.","rationale":"The reader correctly identified the load-bearing step in Theorem 5's Case 1 analysis. Upon careful examination, the structural claim — that v_p's only complement-neighbor in D_p is u — does appear to hold for bipartite complement graphs, because complement edges only cross sides, so all of N̄_C(u) lies on the opposite side from u, and D_p contains only u from u's side. The claim is correct but the proof omits the explicit bipartite-structure justification, leaving an implicit gap. This is a rigor issue rather than a correctness error. The γ_k values (1.725, 1.856, 1.928) appear defensible. The empirical results are strong (4 orders of magnitude speedup, all 96 test cases solved), and the core algorithmic contribution — the complement-graph reformulation and deletion-based branching — is sound regardless of whether the exact constants are tight. The lack of public code is a reproducibility concern but the pseudocode is detailed. ACCEPT is appropriate; the worst-case complexity claim is likely correct even though one step in the proof could be more explicit. The reader's verdict and confidence level are well-calibrated.","tokens_in":32604,"tokens_out":907,"duration_ms":849361,"concrete_test":"Construct a small bipartite complement graph instance with k=1, d=k+1=2, p=q=2 (so u has two complement-neighbors v_1, v_2 both with non-degree k+1). Verify explicitly that in the Lemma 6 branch (where u is deleted and v_2 triggers Lemma 6), the set N̄_C(v_2)∖{u} contains exactly q-1=1 vertex from C (namely v_1), confirming the branch removes p+q=4 vertices from C. Then check whether any alternative bipartite complement configuration with d=k+1 and p≥2 could produce a Lemma 6 branch removing fewer than p+q vertices, which would increase the branching factor beyond what Eq. (3) predicts.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 5, Case 1 (d=k+1, u∈C, p≥2), the proof of recurrence Eq. (2) states: 'all vertices in N̄_C(u) are on the same side as v_p, and hence the only vertex in D_p adjacent to v_p in Ḡ is u.' This claim is load-bearing because it determines the size reduction of the Lemma 6 branch: if v_p has additional complement-neighbors in D_p = {u, v_1, ..., v_{p-1}}, then applying Lemma 6 would remove fewer than p+q vertices from C, weakening the recurrence. The statement that 'all vertices in N̄_C(u) are on the same side as v_p' is asserted without proof. In a bipartite complement graph Ḡ, if u∈U, then N̄_C(u)⊆V by definition (complement edges only cross sides). So v_p∈V and all of N̄_C(u)⊆V — they are indeed on the same side. Since D_p={u}∪{v_1,...,v_{p-1}} where u∈U and v_i∈V, the only vertex in D_p on u's side (U) is u itself. For v_p∈V to have a complement-edge to D_p, that edge must go to a vertex in D_p∩U={u}. So the structural claim appears correct for bipartite complements. However, the proof does not explicitly invoke the bipartite structure to justify this — it states the conclusion as if it follows from the algorithm's vertex ordering rather than from the bipartite partition. The concern is whether there exist configurations where the ordering or side-assignment assumptions break the claimed p+q reduction. The argument seems defensible but the proof gap is real: the connection between 'same side' and 'bipartite complement structure' is implicit rather than demonstrated.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"The paper proposes a deletion-based exact algorithm (DMBP) for the maximum k-biplex search problem in bipartite graphs. The key insight is a structural duality (Theorem 3) showing that finding a maximum k-biplex in G is equivalent to finding a specific minimal k-bounded-degree deletion (k-BDD) in the complement graph Ḡ. Based on this, the authors design a branching strategy (Theorem 4) with several reduction rules (Lemmas 3–6) and prove a worst-case time complexity of O*(γ_k^n) with γ_k < 2 (γ_1=1.725, γ_2=1.856, γ_3=1.928). Two linear-time upper bounds (Lemmas 7–8) and a polynomial-time heuristic (Algorithm 3) are developed. Experiments on eight real-world graphs show up to four orders of magnitude speedup over FastBB and CMBS-CSS.","tokens_in":32835,"tokens_out":1787,"duration_ms":242355,"significance":"The structural duality between k-biplexes and k-BDDs is a clean, parameter-free reformulation that is novel for this problem and opens a distinct algorithmic direction. The worst-case bounds γ_k < 2 improve upon the prior best (α_1=1.754, α_2=1.888, α_3=1.947 from Yu et al.) for k=1,2,3. The upper bounds are shown to be computable in linear time (Lemma 9), and the heuristic achieves 85–98% of optimal edge counts. The experimental coverage is comprehensive: 96 test cases across 8 datasets, ablation studies for both the upper bounds and the heuristic, scalability via sampling, and memory analysis. The speedups reported—particularly the ability to solve all Aol instances where baselines fail for k≥2—are substantial.","major_comments":[{"comment":"Theorem 5, Case 1 (p≥2), proof of Eq. (2): The claim that 'all vertices in N̄_C(u) are on the same side as v_p, and hence the only vertex in D_p adjacent to v_p in Ḡ is u' is load-bearing for the p+q reduction in the Lemma 6 branch. The argument is correct: in a bipartite complement graph Ḡ, if u∈U then N̄_C(u)⊆V, so v_p∈V and D_p∩U={u}, meaning v_p's only complement-neighbor in D_p is u. However, the proof does not explicitly invoke the bipartite partition structure to justify this step—it states the conclusion as if it follows from the vertex ordering rather than from the cross-side-only property of bipartite complements. The authors should add one or two sentences making the bipartite structure explicit (e.g., 'Since Ḡ is bipartite, all complement-edges cross sides; since u∈U and D_p∩U={u}, any complement-edge from v_p∈V to D_p must go to u'). This is a presentation gap in a load-b","section":null},{"comment":"Theorem 5, Case 1, transition from Eq. (2) to Eq. (3): The claim that 'the largest branching factor of Eq. (2) is obtained when q=p=k+1' is stated without proof. Since Eq. (2) has terms T(n−i−1) for i=1..q, T(n−i) for i=2..p, and T(n−p−q), and the constraint is 1≤p≤q≤k+1, the monotonicity argument (larger p and q give more terms and smaller reductions) is plausible but should be verified. A brief justification—e.g., noting that increasing p or q adds terms with smaller arguments while the T(n−p−q) term also decreases—would strengthen this step. The final γ_k values depend on this maximization being correct.","section":null},{"comment":"Theorem 5, Case 3: The characteristic equation is stated as x^{k+3} = x^{k+2} + Σ_{j=1}^{k+1} j·x^{k+1−j}, yielding ζ_1=1.725, ζ_2=1.856, ζ_3=1.923. However, the final claim states γ_3=1.928, which equals η_3 (from Case 2), not ζ_3=1.923. This is consistent with γ_k = max{η_k, ζ_k}, but the reader must verify that η_3 > ζ_3. The paper should explicitly state which case dominates for each k (e.g., 'for k=1,3, Case 2 dominates; for k=2, Case 3 dominates') to avoid confusion.","section":null}],"minor_comments":[{"comment":"§3.1, Theorem 3 proof: The expression 'G[U∪V∖D]' should be 'G[(U∪V)∖D]' for clarity of operator precedence.","section":null},{"comment":"§3.1, Algorithm 1, line 16: The condition 'd_{S∪C}(u) = k+1' triggers BranchImp, but the text in §3.2 refers to 'δ_{S∪C} = k+1'. These are equivalent only when u is the maximum-degree vertex; the algorithm-level condition should be stated consistently.","section":null},{"comment":"§3.1, Algorithm 1, line 27: The stopping condition 'd_{S∪(C∖P_i)}(u) ≤ k and (i=q or d_{S∪C}(v_{i+1}) ≤ k)' uses d_{S∪C}(v_{i+1}) rather than d_{S∪(C∖P_i)}(v_{i+1}). If P_i has already been moved to D, the non-degree of v_{i+1} should be evaluated in the reduced candidate set. Please clarify.","section":null},{"comment":"Table 3: Several entries show |E*|=0 (e.g., LKML k=6 θ=16, Google k=3 θ=15, Google k=4 θ=17). It would help to note in the table caption or text that |E*|=0 means no k-biplex satisfying the size threshold θ exists, so the reported time is the time to certify infeasibility.","section":null},{"comment":"§5.2, Exp-1: The speedup claim 'at least 5000×' on LKML (k=2, θ=9) is computed as 16231/2.77 ≈ 5859×, which is fine, but the Mummun claim 'at least 28000×' uses 9257/0.33 ≈ 28021×. These should be reported with consistent precision.","section":null},{"comment":"Figure 4: The y-axis label 'INF' for timeout is inconsistent with Table 3 which uses '-'. Please unify.","section":null},{"comment":"§2, Definition 1: 'A k-biplex G[S] is a subgraph of G induced by S=(U_S, V_S)' — the notation G[S] is used before G[S] is formally defined (it appears in the next paragraph). Consider reordering.","section":null},{"comment":"References [11], [33], [38], [39] use '[n. d.]' for the year. Please complete these bibliographic entries.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The stress-test concern about the structural claim in Theorem 5 Case 1 is valid as a presentation gap but does not affect correctness: the bipartite complement structure does ensure that v_p's only complement-neighbor in D_p is u. The concern is appropriately addressed by asking for an explicit justification rather than flagging a correctness error. The paper is a strong submission with a genuine algorithmic contribution and thorough experiments. The major comments are all fixable by adding clarifying sentences or a short lemma; none require re-derivation of the complexity bounds."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for the careful and constructive report. All three major comments concern presentation gaps in the proof of Theorem 5; we agree with each and will revise the manuscript accordingly. No standing objections remain.","responses":[{"response":"We agree that this step is load-bearing and that the current proof states the conclusion without explicitly justifying it from the cross-side-only property of bipartite complements. The argument is as follows: since Ḡ is bipartite, all complement-edges cross sides. The branching vertex u belongs to one side (say U), so its complement-neighbors N̄_C(u) lie entirely in V. Since v_p ∈ N̄_C(u), we have v_p ∈ V. The set D_p = {u, v_1, ..., v_{p-1}} intersects U only at u (as v_1, ..., v_{p-1} ∈ N̄_C(u) ⊆ V). Therefore, any complement-edge from v_p to D_p must go to u, since all complement-edges cross sides and u is the only vertex in D_p on the opposite side from v_p. We will add this explicit justification to the proof.","revision_made":"yes","referee_comment":"Theorem 5, Case 1 (p>=2), proof of Eq. (2): The claim that all vertices in N̄_C(u) are on the same side as v_p, and hence the only vertex in D_p adjacent to v_p in Ḡ is u, is correct but does not explicitly invoke the bipartite partition structure. The authors should add one or two sentences making the bipartite structure explicit."},{"response":"We agree that this maximization step deserves explicit justification. The argument is: Eq. (2) contains terms T(n-i-1) for i=1..q, terms T(n-i) for i=2..p, and a term T(n-p-q), under the constraint 1 ≤ p ≤ q ≤ k+1. Increasing q adds more terms T(n-i-1) with smaller reductions (i.e., larger arguments), which can only increase the branching factor. Similarly, increasing p adds more terms T(n-i) with larger arguments and simultaneously increases the reduction p+q in the last term T(n-p-q), but the net effect of adding a term with a larger argument dominates, so the branching factor increases. Thus the maximum is attained at p = q = k+1. We have also verified this numerically for k = 1, 2, 3 by evaluating the characteristic roots at all feasible (p, q) pairs. We will add a concise version of this monotonicity argument to the proof.","revision_made":"yes","referee_comment":"Theorem 5, Case 1, transition from Eq. (2) to Eq. (3): The claim that the largest branching factor of Eq. (2) is obtained when q=p=k+1 is stated without proof. A brief justification should be added."},{"response":"The referee is correct that γ_k = max{η_k, ζ_k} and that for k=3, Case 2 (η_3 = 1.928) dominates Case 3 (ζ_3 = 1.923). The final paragraph of the proof does state 'γ_k = max{η_k, ζ_k}' and lists the resulting values, but it does not explicitly indicate which case achieves the maximum for each k. We will add an explicit statement clarifying which case dominates for each value of k. Specifically: for k=1, Case 3 dominates (ζ_1 = 1.725 > η_1 = 1.618); for k=2, Case 3 dominates (ζ_2 = 1.856 > η_2 = 1.839); for k=3, Case 2 dominates (η_3 = 1.928 > ζ_3 = 1.923).","revision_made":"yes","referee_comment":"Theorem 5, Case 3: The characteristic equation yields ζ_3=1.923, but the final claim states γ_3=1.928, which equals η_3 from Case 2. The paper should explicitly state which case dominates for each k to avoid confusion."}],"tokens_in":32678,"tokens_out":929,"duration_ms":97695,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper introduces a deletion-based branching algorithm for maximum k-biplex search that achieves the best known worst-case bounds (γ_1=1.725, γ_2=1.856, γ_3=1.928) and demonstrates up to four-order-of-magnitude speedups over state-of-the-art methods on real graphs. The central idea — reformulating k-biplex search in G as k-bounded-degree deletion in the complement graph Ḡ — is genuinely new for this problem and well-executed. The structural duality (Theorem 3) is clean and parameter-free. The branching rule (Theorem 4) is a natural but effective adaptation, and the branch reduction via Lemma 6 for the δ=k+1 case is where the real complexity gain comes from. The upper-bounding techniques (Lemmas 7–8) are linear-time and the ablation studies show they matter substantially in practice. The heuristic algorithm produces solutions within 85–98% of optimal, which is solid for initial-bound purposes. Experiments are comprehensive across eight datasets with appropriate baselines (FastBB, CMBS-CSS) and the speedup claims are credible given the detail provided. No code is publicly available, which is a reproducibility gap, but the pseudocode is detailed enough to follow. The soft spot is in Theorem 5, Case 1. The proof claims that in the Lemma 6 branch, v_p's only complement-neighbor in D_p is u, because all vertices in N̄_C(u) are on the same side as v_p. The stress-test flagged this as unproven. On careful reading, the claim actually holds: in a bipartite complement graph, complement-edges only cross sides, so if u∈U then N̄_C(u)⊆V, and D_p∩U={u}, meaning v_p∈V can only connect to u in D_p. The argument is correct but the proof never explicitly invokes the bipartite structure to justify it — it states the conclusion as if it follows from the vertex ordering rather than from the partition. This is a presentation gap, not a mathematical error. The worst-case optimization claim (q=p=k+1 maximizes the branching factor) is defensible given the constraints 1≤p≤q≤k+1. This paper is for researchers in cohesive subgraph computation and exact combinatorial algorithms. It makes a substantive contribution to the k-biplex search literature. Recommend accept with minor revisions: ask the authors to (1) make the bipartite-structure argument explicit in Theorem 5 Case 1, and (2) release code if possible.","headline":"Solid algorithmic contribution with a real complexity improvement; one proof step in Theorem 5 needs tightening but the core holds.","tokens_in":33444,"tokens_out":627,"would_cite":true,"duration_ms":106455,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Flip the problem, find the biplex faster","keywords":["k-biplex","bipartite graph","complement graph","branch and bound","NP-hard","cohesive subgraph","vertex deletion","worst-case complexity"],"falsifier":"If a graph instance can be constructed where the complement-based branching consistently produces more branches than the inclusion-based approach (because the complement graph is dense and high-degree vertices have many neighbors to branch over), the claimed speedup would not hold on that instance class.","tokens_in":32620,"feed_emoji":"🔬","tokens_out":1103,"duration_ms":82839,"temperature":0.7,"pith_summary":"The paper proves that the maximum k-biplex problem in a bipartite graph is structurally equivalent to a minimum vertex deletion problem on the complement graph, where the goal is to remove the fewest vertices so that every remaining vertex has degree at most k. This duality reframes the search from deciding which vertices to keep to deciding which to delete, which changes the branching structure of the algorithm. The resulting branching algorithm achieves worst-case time complexity O*(γ_k^n) with γ_k < 2 (γ_1=1.725, γ_2=1.856, γ_3=1.928), which is the best known bound for this problem. Two linear-time upper-bounding techniques and a polynomial-time heuristic for initial solutions further prune the search space. On eight real-world bipartite graphs, the algorithm solves all 96 test cases while prior state-of-the-art methods solve only 22–23, with speedups reaching four orders of magnitude on large graphs like Aol.","feed_headline":"Complement-graph trick cracks k-biplex search","feed_subtitle":"Reframing the problem as vertex deletion in the complement yields sub-2^n complexity and up to 10,000x speedup on real graphs.","key_machinery":"Structural duality between k-biplex and k-bounded-degree deletion (k-BDD): the complement of a maximum k-biplex in G is a minimal k-BDD in Ḡ. The branching rule (Theorem 4) states that any k-BDD must contain either a chosen vertex v or at least d(v)−k of its neighbors, where d(v) is the degree in the complement. Branch reduction rules exploit vertices that can be deterministically moved to the deletion set or the solution set, and a special-case strategy for complement-degree k+1 uses Lemma 6 to force additional vertices into the solution, reducing the branching factor.","core_discovery":"The central discovery is the structural duality (Theorem 3) between maximum k-biplex search in a bipartite graph G and minimal k-bounded-degree deletion in its complement graph Ḡ. A k-biplex is a subgraph where every vertex has at most k missing edges; in the complement, this means every vertex has degree at most k. The complement of a maximum k-biplex is a minimal deletion set that reduces all degrees to at most k. This equivalence enables a branching strategy that selects a high-degree vertex in the complement and branches on either deleting it or deleting enough of its neighbors to bring its degree down to k, which produces fewer and more effective branches than prior inclusion-based (BK","pith_inferences":["The complement-graph approach may be particularly effective on dense bipartite graphs (where the complement is sparse), suggesting that the algorithm's practical advantage could vary with graph density—a relationship not explicitly analyzed in the paper.","The worst-case complexity analysis depends on the branching factor being maximized at specific parameter values (q=p=k+1 in Case 1); if this worst case cannot actually arise for certain graph classes, the true complexity on those classes could be lower than the stated bound.","The gap between heuristic solution quality (85–98% of optimal) and exact solution time suggests that for applications where near-optimal solutions suffice, the heuristic alone may deliver sufficient quality at a fraction of the cost."],"forward_implications":["The deletion-based complement perspective could be applied to other cohesive subgraph problems on bipartite graphs (e.g., maximum quasi-biclique, maximum s-plex on bipartite graphs) where a complement formulation yields better branching factors.","The upper-bounding techniques that account for both vertex-level and set-level missing-edge allowances could be adapted for any branch-and-bound algorithm that maximizes edges under degree constraints.","The heuristic algorithm's two-stage approach (greedy deletion followed by localized distance-bounded expansion) provides a template for constructing high-quality initial solutions in other NP-hard subgraph optimization problems where distance properties constrain feasible solutions."],"fun_headline_variants":["Complement duality reframes k-biplex search as vertex deletion","Delete instead of include: new branching for maximum k-biplex","Dual view: k-biplex search equals degree-bounded deletion","Sub-2^n k-biplex search via complement deletion duality","Complement-graph deletion yields 10,000x speedup on k-biplex"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The worst-case complexity proof assumes that in one sub-case of the branching analysis, the branching factor is maximized when all of a vertex's complement-neighbors are on the same side of the bipartite graph and have a specific degree structure. Whether this configuration is always the true worst case across all possible bipartite graph structures is stated but not fully verified.","fun_headline_variants_meta":{"raw":{"variants":["Complement duality reframes k-biplex search as vertex deletion","Delete instead of include: new branching for maximum k-biplex","Dual view: k-biplex search equals degree-bounded deletion","Sub-2^n k-biplex search via complement deletion duality","Complement-graph deletion yields 10,000x speedup on k-biplex","Maximum k-biplex through minimal degree-bounded deletion","Branching on deletion beats inclusion for maximum k-biplex","Flip to complement graph, delete vertices, find k-biplex faster","Structural duality cuts k-biplex search space by four orders","k-bounded-degree deletion: a dual route to maximum k-biplex"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":1421,"prompt_tokens":658,"completion_tokens":763,"prompt_tokens_details":null},"tokens_in":658,"tokens_out":763,"duration_ms":12405,"temperature":1.0,"reasoning_tokens":546,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T11:23:06.962906+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If a graph instance can be constructed where the complement-based branching consistently produces more branches than the inclusion-based approach (because the complement graph is dense and high-degree vertices have many neighbors to branch over), the claimed speedup would not hold on that instance class.","supporting_citations":[],"review_version":1}