{"id":"2a0e8562-31ff-486b-aca5-8bdbc1777c12","arxiv_id":"2412.00704","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"MVM is a new kernelization algorithm for bipartite maximum matching that applies Karp-Sipser reduction rules with a claimed O(min(m log n, n^2)) time bound on CSR-style storage and faster measured runtimes than existing KaSi variants.","lead":"This paper introduces MVM, a kernelization algorithm that applies Karp-Sipser reduction rules to shrink bipartite graphs before maximum matching is computed. It claims near-linear running time on ordinary array-based storage and reports large speedups over prior kernelization methods on real and synthetic graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(m log n) theorem rests on the unproved halving inequality N(V_r) <= N(V_{r-1})/2 (Eq. 5), so the central near-linear worst-case bound is unsupported.","rationale":"I read the paper as making two distinct contributions: a practical MVM implementation with strong empirical speedups, and a theoretical claim that this implementation has O(min(m log n, n^2)) worst-case time even on structures with O(n) search efficiency. The experimental portion is credible: the ablation study, comparisons against KaSi variants and maximal-matching initializers, and the kernelization-quality measurements all support the practical value of the method. The theoretical contribution, however, is the abstract's headline and the basis for the claimed novelty over earlier O(n^2) implementations. That claim stands or falls on the number of rounds R in §IV-E, and the only argument for R = O(log n) is the asserted halving inequality N(V_r) <= N(V_{r-1})/2 in Eq. (5). The paper explicitly says this 'can be derived' but gives no derivation, and Eq. (4) is a local condition about a single starting vertex's neighborhood rather than a global bound on merge counts. This is exactly the load-bearing assumption the reader identified, and I agree it is insecure. I also note the same section asserts, without proof, that boundary sets of same-side merge operations within a round are disjoint, which is needed for the O(m) per-round cost in Eq. (3); that is a secondary but related gap. Because the central theoretical guarantee is unsupported at its decisive step, the current manuscript should not be accepted as-is. A revision that either proves Eq. (5) from explicit invariants or limits the paper's claims to empirical performance would be a different matter. Since the reader's REJECT verdict already reflects this concern, my stress-test does not change the recommendation.","tokens_in":16282,"tokens_out":6555,"duration_ms":62983,"concrete_test":"Implement Algorithm 2 exactly with the balanced round and bucket logic, and instrument it to record N(V_r), the number of multi-vertex merging operations completed in each global round. Enumerate all bipartite graphs up to a small size (e.g., n <= 10) or a large biased sample including Kaya-style worst-case instances, and check whether N(V_r) <= N(V_{r-1})/2 holds for every round on every input. A single violation would refute Eq. (5), leaving only O(mn) as supported; if no violation is found in exhaustive enumeration, the inequality still requires a written proof before the theorem can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The claimed novelty is the O(min(m log n, n^2)) worst-case bound for a CSR-like, O(n)-search-efficiency implementation. In §IV-E the entire argument reduces to the number R of processing rounds: Eq. (3) bounds each round by O(m), and R is then asserted to be O(log n) because N(V_r) <= N(V_{r-1})/2 in Eq. (5). This halving inequality is the only step that makes the bound near-linear, but the paper does not derive it. The text says it 'can be derived' from Eq. (4), yet Eq. (4) is a local statement about one starting vertex whose two neighbors in the previous round belong to two different merge sets; it does not by itself bound the global number of multi-vertex merges in successive rounds. Nothing in Eq. (4) rules out many new starting vertices being generated from the same pair of prior merge sets, or boundary-vertex overlap causing N(V_r) to decay by only a constant fraction. If Eq. (5) fails, R can be Θ(n), and the O(m) per-round cost yields O(mn), not O(m log n). Eq. (3)'s additional assertion that boundary sets of same-side merges in a round are disjoint is also stated without proof. The experimental results remain credible evidence of practical speed, but they do not substitute for the missing proof of Eq. (5), so the theoretical headline is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MVM, a kernelization algorithm for exact maximum bipartite matching that implements the two Karp-Sipser reduction rules on a CSR-like storage format. It introduces three optimizations: multi-vertex merging, indirect set operations, and a balanced round-based processing order, and claims that the resulting algorithm runs in O(min(m log n, n^2)) even when neighborhood search has O(n) worst-case cost. The paper also designs a linked edge-table data structure for lower-cost vertex merging and reports experiments on 26 real-world and 8 synthetic graphs, showing large speedups over KaSi variants and stable acceleration over maximal-matching initializers.","tokens_in":16617,"tokens_out":12916,"duration_ms":123054,"significance":"The claimed worst-case bound is the main contribution: existing CSR-based implementations of Karp-Sipser kernelization have O(n^2) upper bounds, and a near-linear bound on a storage format with O(n) search would be a genuinely useful robustness guarantee. The engineering ideas are clearly described and the experimental evaluation is extensive, including an ablation of the three strategies and memory measurements. If the proof can be completed, the result is significant; as written, however, the proof of the main theorem is incomplete at the point where the number of rounds is bounded, so the headline theoretical result is not yet established.","major_comments":[{"comment":"The analysis reduces to bounding the number R of processing rounds. Eq. (5) asserts N(V_r) <= N(V_{r-1})/2, and the text says this 'can be derived' from Eq. (4), but no derivation is shown. Eq. (4) is a local statement about a single starting vertex in round r whose two neighbors lie in two round-(r-1) boundary sets; it does not imply a global halving of the number of multi-vertex merging operations. It also silently assumes that every vertex that becomes degree-2 in round r has both neighbors arising from previous-round merge sets, which is not argued. If Eq. (5) fails, R can be as large as Theta(n) and the claimed O(m log n) bound degrades to O(mn). A complete proof of the halving property is required before the central claim is supported.","section":"Section IV-E, Eq. (5)"},{"comment":"The equality T_MVM = O(R * m) in Eq. (3) relies on the sentence 'in each iteration, the mergeable vertices on the same side of the bipartite graph have non-overlapping boundary vertices.' This disjointness property is not proved from Algorithm 2; it is exactly what is needed to replace the sum of boundary-vertex degrees by O(m) per round. Since the balanced-processing strategy is one of the three core optimizations, this invariant should be stated and proved explicitly.","section":"Section IV-E, Eq. (3)"},{"comment":"The amortized O(1) bound for updating external vertices requires the total gap size y to be Theta(deg(v)). The paper acknowledges that the practical implementation does not enforce this condition unless the edge tables are enlarged, e.g., by doubling. The theoretical complexity statement should therefore include this storage-size assumption explicitly, and the experimental section should state whether the tested implementation relied on the gap condition or on a different mechanism.","section":"Section V-B, Eq. (6)"}],"minor_comments":[{"comment":"The header misspells 'DATASET' as 'DATESET'.","section":"Table II"},{"comment":"The reference for the KaSi comp baseline is inconsistent: Section I cites [33] while Section VI-A cites [37]; please unify.","section":"Sections I and VI-A"},{"comment":"The symbol N(.) is used without a precise definition; please define it as the number of multi-vertex merging operations performed in a given round.","section":"Section IV-E, Eq. (5)"},{"comment":"The early-exit condition uses |V~| = |V^|, but the case |V~| > |V^| can arise when a newly added mergeable vertex contributes a boundary vertex not previously present; this case is not discussed.","section":"Algorithm 2, lines 15-19"},{"comment":"The paper says each instance was run five times and averaged, but the algorithms are deterministic; this is not an error, but a brief explanation of what varies across runs would help the reader interpret the reported times.","section":"Section VI"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the missing proof of Eq. (5). I see no circular reasoning or fitted parameters in the paper, and the experimental claims are plausible, but they do not substitute for the missing theoretical derivation. If the authors can provide a rigorous proof of the halving inequality (or a corrected bound), I would view the paper as publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The practical MVM algorithm is the real deal as an engineering contribution. The multi-vertex merging strategy over implicit degree-two vertices, the indirect set-operation trick, and the linked-CSR storage format are legitimate extensions beyond the existing KaSi variants, and the experiments back the claims: MVM consistently beats KaSi cache, KaSi comp, HKaSi, and TKaSi on real graphs, and the ablation study shows the three strategies each earn their keep. The speedups are large and in the right direction. If you work on practical bipartite matching preprocessing, this paper is worth a careful read.\n\nThat said, the theoretical headline does not hold up on the current write-up. The entire near-linear claim reduces to the halving inequality N(V_r) <= N(V_{r-1})/2 in Eq. (5), and the paper never proves it. The text says it \"can be derived\" from Eq. (4), but Eq. (4) is a local statement about a single starting vertex's neighbors split between two merge sets; it does not obviously bound the global number of merge operations in successive rounds. Without that bound, R could be Theta(n), and the O(m) per-round cost gives O(mn), not O(m log n). The same section also asserts that same-side merge sets have disjoint boundary sets without proof. That is another unexamined assumption. And the amortized O(1) update cost in Eq. (6) depends on edge-table doubling, which the authors explicitly say their implementation does not use, so the practical algorithm does not actually meet the theoretical amortized bound as stated.\n\nThe authors are not sloppy elsewhere. The algorithm descriptions are detailed, the experimental methodology is sound, and they honestly point out the trade-offs of the balanced processing strategy. The gap is specifically in Section IV-E, and it is load-bearing. A revision that either supplies a real proof of Eq. (5) or scales the claim back to \"practical robustness with experiments\" would fix most of my concern. No code is released, which limits reproducibility, but the experiments use public datasets and the descriptions are concrete enough to reimplement.\n\nThis deserves a serious referee. I would send it to peer review, not desk reject it, but I would not accept it as-is. The practical kernelization is valuable, and the theory question is exactly the kind of thing a good referee can push on. My own verdict: skeptical on the theorem, positive on the engineering.","headline":"The MVM kernelization is a genuinely useful practical contribution with credible speedups, but the headline O(m log n) worst-case bound rests on an unproven and non-obvious halving inequality, so the theory needs major revision.","tokens_in":17072,"tokens_out":1667,"would_cite":false,"duration_ms":17446,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","68Q25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims MVM is the first Karp-Sipser kernelization with near-linear worst-case time on CSR-style array storage.","keywords":["bipartite graph matching","maximum matching","kernelization","Karp-Sipser reduction rules","data reduction","near-linear time","CSR graph storage"],"falsifier":"Run MVM on the paper's synthetic worst-case graphs with $n = 2^{15}$ through $2^{22}$, counting the number of multi-vertex merge operations performed in each round. If any round contains more than half the previous round's merges, repeatedly, then the halving property used for the bound is false and the claimed $O(m \\log n)$ time does not follow from the given proof.","tokens_in":16062,"feed_emoji":"📉","tokens_out":8900,"duration_ms":74026,"temperature":0.7,"pith_summary":"This paper proposes MVM, an algorithm that applies Karp and Sipser's two data-reduction rules to shrink a bipartite graph before a maximum matching is computed on the kernel. The central claim is that MVM runs in $O(\\min(m \\log n, n^2))$ time even when the graph is stored in a CSR-like array structure whose per-operation search cost is $O(n)$ in the worst case, a setting where previous Karp-Sipser implementations had an $O(n^2)$ bound. If the claim holds, MVM is the first Karp-Sipser kernelization that is both provably near-linear on sequential, cache-friendly storage and competitive with hash-table or tree-based variants in practice. The paper also reports speedups of 25$\\times$ and 56$\\times$ over those theoretical hash- and tree-based variants on real graphs, with kernelization reducing the input by orders of magnitude on difficult instances.","feed_headline":"Near-linear kernelization for bipartite matching on plain CSR","feed_subtitle":"MVM applies Karp-Sipser reductions in O(m log n) time even on array storage, shrinking graphs before exact matching.","key_machinery":"The carrying object is the pair $(\\hat{V}, \\tilde{V})$: the current set of mergeable vertices and their neighboring boundary vertices. Multi-vertex merging expands $\\hat{V}$ until no vertex satisfies $|\\Gamma(v) - \\tilde{V}| \\le 1$, and the merge operation reconnects the whole boundary set to one retained vertex. The key identity for the runtime bound is $N(\\hat{V}_r) \\le N(\\hat{V}_{r-1})/2$, where $N(\\hat{V}_r)$ counts merge operations in round $r$; along with $O(m)$ work per round it yields $O(m \\log n)$. The storage machinery is a CSR variant in which edge tables are linked by vtx_link_next and vtx_link_last pointers and updates to external vertices are batched and deferred, giving amortized $O(1)$ edge insertions.","core_discovery":"On the paper's own terms, the discovery is that Karp-Sipser kernelization can be made round-based rather than vertex-by-vertex. In each round, MVM takes an explicit degree-2 vertex, expands to the set $\\hat{V}$ of all mergeable vertices that share boundary vertices, and merges the entire boundary set $\\tilde{V}$ at once; implicit mergeable vertices are found by the rule that $|\\Gamma(v)-\\tilde{V}|=1$, and the search itself only touches edges incident to boundary vertices. A balanced processing strategy delays newly created degree-2 vertices to later rounds so that boundary sets in one round do not overlap on the same side of the bipartition. The paper claims this forces the number of multi-vertex merges to at least halve each round, giving $O(\\log n)$ rounds and hence $O(m \\log n)$ total work on a CSR-like data structure; the same analysis gives an $O(n^2)$ amortized bound, hence $O(\\min(m \\log n, n^2))$.","pith_inferences":["Inference: the proof's load-bearing point is the halving bound $N(\\hat{V}_r) \\le N(\\hat{V}_{r-1})/2$; if that inequality cannot be derived, the worst-case bound would revert to $O(mn)$, so a direct proof or a counterexample would settle the paper's central claim.","Inference: the same round-based expansion machinery may transfer to other degree-based preprocessing such as weighted matching or maximum matching in general graphs, because the merge operation is defined locally on degree-2 vertices.","Inference: a hybrid that applies balanced rounds only when high-degree boundary vertices are present could recover the small constant-factor losses the paper observes on real-life graphs while preserving the worst-case guarantee.","Inference: the deferred batch-update data structure likely transfers to streaming or dynamic graph settings, where postponing cleanup of deleted vertices can reduce update costs below per-edge reallocation."],"forward_implications":["Kernelization can be inserted as a preprocessing step with a worst-case guarantee on ordinary CSR graphs, so exact maximum matching becomes faster without losing a provable bound on sparse inputs.","Because the kernel is smaller and denser, exact algorithms such as PFP solve it more quickly; on com-LiveJournal the paper reports roughly a 230-fold overall speedup.","MVM can be combined with maximal matching algorithms on the kernel graph to gain further speed, an option the paper notes but did not include in its fairness comparisons.","The amortized $O(1)$ batch update scheme means edge-table updates need not reallocate arrays per insertion, which matters for any subsequent graph algorithm that runs on the kernel.","Hash-table and tree-based storage are no longer needed to reach poly-logarithmic bounds, since the claimed $O(m \\log n)$ result holds on CSR-like arrays with $O(n)$ search efficiency."],"supporting_citations":[{"why":"Supplies the original Karp-Sipser data-reduction rules, degree-1 deletion and degree-2 merging, that MVM implements.","marker":"[22]"},{"why":"Introduces the KaSi algorithm and the HKaSi and TKaSi hash- and tree-based variants whose bounds and synthetic worst-case instances MVM builds on and compares against.","marker":"[17]"},{"why":"Provides KaSi_comp, the existing component-based kernelization baseline that MVM generalizes with multi-vertex merging.","marker":"[33]"},{"why":"Supplies PFP, the exact maximum matching algorithm used after kernelization; its cost on the kernel graph determines the reported speedups.","marker":"[16]"},{"why":"Provides the component-based method and shared-memory kernelization context that motivates the multi-vertex merging strategy.","marker":"[37]"}],"fun_headline_variants":["Merging round-by-round: near-linear Karp-Sipser kernelization on CSR","Round-based Karp-Sipser reductions hit O(m log n) on plain arrays","MVM: Shrink bipartite graphs in near-linear time via batch vertex merges","Efficient kernelization: MVM merges Karp-Sipser rounds on CSR storage","Bipartite matching faster: kernelize in O(m log n) with round-based merging"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The near-linear bound stands on the claim that each round at least halves the number of merge operations, and the paper states this halving without proving it from the preceding round relation. If the halving can fail, the number of rounds could grow with the graph size and the bound would degrade to $O(mn)$.","fun_headline_variants_meta":{"raw":{"variants":["Merging round-by-round: near-linear Karp-Sipser kernelization on CSR","Round-based Karp-Sipser reductions hit O(m log n) on plain arrays","MVM: Shrink bipartite graphs in near-linear time via batch vertex merges","Efficient kernelization: MVM merges Karp-Sipser rounds on CSR storage","Bipartite matching faster: kernelize in O(m log n) with round-based merging"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00073,"raw_usage":{"total_tokens":3278,"prompt_tokens":967,"completion_tokens":2311,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":2197}},"tokens_in":583,"tokens_out":2311,"duration_ms":15467,"temperature":1.0,"reasoning_tokens":2197,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:05:51.176795+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MVM on the paper's synthetic worst-case graphs with $n = 2^{15}$ through $2^{22}$, counting the number of multi-vertex merge operations performed in each round. If any round contains more than half the previous round's merges, repeatedly, then the halving property used for the bound is false and the claimed $O(m \\log n)$ time does not follow from the given proof.","supporting_citations":[{"cited_title":"Maximum matching in sparse random graphs,","cited_arxiv_id":null,"evidence_quote":"Supplies the original Karp-Sipser data-reduction rules, degree-1 deletion and degree-2 merging, that MVM implements."},{"cited_title":"Karp-sipser based kernels for bipartite graph matching,","cited_arxiv_id":null,"evidence_quote":"Introduces the KaSi algorithm and the HKaSi and TKaSi hash- and tree-based variants whose bounds and synthetic worst-case instances MVM builds on and compares against."},{"cited_title":"Data reduction for maximum matching on real-world graphs: Theory and experiments,","cited_arxiv_id":null,"evidence_quote":"Provides KaSi_comp, the existing component-based kernelization baseline that MVM generalizes with multi-vertex merging."},{"cited_title":"Design, implementation, and analysis of maximum transversal algorithms,","cited_arxiv_id":null,"evidence_quote":"Supplies PFP, the exact maximum matching algorithm used after kernelization; its cost on the kernel graph determines the reported speedups."},{"cited_title":"Shared-memory implementa- tion of the karp-sipser kernelization process,","cited_arxiv_id":null,"evidence_quote":"Provides the component-based method and shared-memory kernelization context that motivates the multi-vertex merging strategy."}],"review_version":1}