{"id":"7ed0fa97-d935-47db-bf00-375eff927242","arxiv_id":"1908.06795","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"A portfolio solver blending vertex cover kernelization with clique and maximum-independent-set techniques won PACE 2019, solving 87 of 100 private instances and revealing that kernelization can either boost or hurt branch-and-bound search.","lead":"This paper describes the winning solver from the PACE 2019 vertex cover challenge, a portfolio that combines kernelization, local search, branch-and-reduce, and a max-clique branch-and-bound solver. It reports that this combination solves more benchmark instances than any prior approach, and documents three new empirical insights about how kernelization and local search interact with exact solvers.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Benchmark duplication and unseeded ILS make the key ablation claims look more significant than they are.","rationale":"I read the paper as a competition report plus three transferable algorithm-design claims. The competition result is externally verified and the tables check out, so I do not want to reject. But the two new insights that are supposed to generalize are measured on a corpus with visible repeats: the same (n,m,n',m',|VC|) quadruple recurs 12–16 times. The solved-instance counts are the only quantitative support; deduplicating by family is therefore a necessary robustness check, not a stylistic preference. The absence of seeds/repetitions for the randomized ILS compounds this, because the local-search boost is exactly the kind of single-run effect that can be seed-dependent. This is why I keep the reader's CONDITIONAL verdict rather than upgrading to ACCEPT. I do not see evidence of incorrectness, and the source code availability is real support; the concern is about the breadth of the claims, not their soundness.","tokens_in":16378,"tokens_out":21166,"duration_ms":191475,"concrete_test":"On the 100 public instances from Tables 1–2, group instances by (n, m, n', m', |VC|) and, if the challenge sources allow, by generator family; recompute the number of distinct families solved by MoMC, RMoMC, BnR, LSBnR, and FullA. Then rerun LSBnR and FullA on the public instances with at least 10 different ILS seeds and report the range of solved counts. If RMoMC's family-level lead over BnR shrinks from 26 instances to a handful of families, or if LSBnR's lead is not monotone across seeds, the paper should soften 'significantly outperform' and 'significantly boost' to claims about specific benchmark families.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Tables 1–2 are internally consistent, and the PACE win is credible. The problem is that the paper's central ablation claims are dominated by near-duplicate instance families. RMoMC's headline advantage over BnR (68 vs 42, Sec. 6.2) is 26 instances; at least 23 of those come from two families: 16 instances with n=18096, m=28281, kernel ≈580/2000, |VC|=11185, and 7 with n=15783, m=24663, kernel ≈510/1750, |VC|=9755. LSBnR's 13-instance advantage over BnR is 12 copies of one family (n=26300, m=41500, kernel 500/3000, |VC|=16300) plus one other row. Within each family the tables list identical n, m, kernel size, and optimum, so these are almost certainly seeds from a single generator. Counting them as independent successes inflates the apparent 'significance' of the kernelization-plus-B&B and local-search insights. In addition, the ILS-based LSBnR and FullA results are single runs with no seeds or repetitions, so the local-search boost is not yet separated from seed luck. The competition result survives, but these two stated insights are not as broadly supported as the counts suggest.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents WeGotYouCovered, the winning solver of the PACE 2019 Implementation Challenge Vertex Cover Track. The solver is a four-phase portfolio: kernelization with an adaptation of Akiba and Iwata's reduction suite, iterated local search on the kernel, branch-and-reduce with an initial solution, and two calls to the MoMC branch-and-bound maximum-clique solver on the complement graph (one on the kernel, one on the original graph). On the 100 public benchmark instances, the full algorithm solves 82; on the 100 private instances it solves 87, beating the second-place solver by 10 instances. The paper's ablations report that RMoMC (kernelization plus MoMC) solves 68 public instances versus 42 for BnR (branch-and-reduce), LSBnR (local search plus BnR) solves 55, and MoMC alone solves 30. The authors draw three qualitative conclusions: kernelization can boost branch-and-bound enough to beat branch-and-reduce, local search can significantly boost branch-and-reduce, and kernelization can sometimes hurt branch-and-bound (instances 131 and 157).","tokens_in":16650,"tokens_out":9346,"duration_ms":78086,"significance":"If supported, the paper's insights are valuable to the exact vertex cover / maximum clique / independent set community: they demonstrate that techniques can be transferred across these equivalent problems and that portfolio design matters for competition-level performance. The paper ships its source code under an open license, reports per-instance results on an external benchmark, and compares fixed algorithm configurations without fitted parameters, which is a strength. The PACE 2019 win itself is credible and is a useful data point for benchmark-based evaluation. However, the two main ablation claims rely on raw instance counts over a benchmark that contains large families of near-duplicate instances, which weakens the generality of the conclusions as currently stated.","major_comments":[{"comment":"The central ablation claim that kernelization followed by branch-and-bound 'significantly outperforms' branch-and-reduce rests on the 26-instance advantage of RMoMC over BnR. Inspection of Tables 1 and 2 shows that 16 of these 26 instances come from one family (n=18096, m=28281, kernel with roughly 580 vertices and 2000 edges, |VC|=11185) and 7 come from a second family (n=15783, m=24663, kernel roughly 510/1750, |VC|=9755). Within each family the rows report identical n, m, kernel size, and optimum, so these are near-duplicates from a common generator rather than independent test cases. Counting them as independent successes overstates the breadth of the evidence; the paper should report per-family success counts and qualify the 'significant' claim accordingly.","section":"Section 6.2, Tables 1-2"},{"comment":"The same duplication problem affects the claimed local-search boost: LSBnR solves 13 more instances than BnR, but 12 of those 13 are from a single family (n=26300, m=41500, kernel 500/3000, |VC|=16300), with instance 181 being the only exception. The evidence that local search 'significantly boosts' branch-and-reduce is thus essentially a result on one graph family. The authors should report how many distinct generator families each configuration solves and use family-level counts, not total instance counts, to support the qualitative conclusion.","section":"Section 6.2, Tables 1-2"},{"comment":"The paper does not state whether the iterated local search used in LSBnR and FullA is deterministic or how random seeds are chosen. If the ILS is randomized, a single run per instance is not sufficient to separate the reported 13-instance advantage of LSBnR over BnR from seed variation. The authors should either state that their fixed configuration uses a deterministic ILS, or report the variance over multiple seeds (for example, the number of instances solved across 10 independent runs). This is load-bearing for the local-search-boost claim.","section":"Section 6.1"}],"minor_comments":[{"comment":"'Vertex over problem' should be 'vertex cover problem' in the abstract and the introduction.","section":"Abstract and Section 1"},{"comment":"In the desk-reduction description, the condition is printed as '|N(A)\\B| ≤ 2, |N(A)\\B| ≤ 2, and N(A) ∩ N(B) = ∅'; the second condition should presumably be '|N(B)\\A| ≤ 2'.","section":"Section 4.1"},{"comment":"'An minimum vertex cover' should be 'a minimum vertex cover'.","section":"Section 4.1"},{"comment":"The sentence 'The results are similar to the results on the private instances' should refer to the public instances, since the preceding sentence discusses the private instances.","section":"Section 6.2"},{"comment":"The conclusion states the solver uses 'all known reduction rules', while Section 4.1 describes the collection as 'extensive (though not exhaustive)'; these statements should be aligned.","section":"Section 7"},{"comment":"Figure 1 is hard to read at its printed resolution, and the tables do not report per-instance running times, so readers cannot reconstruct the time-to-solution behavior behind the cumulative plot.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid competition-solver report with a credible PACE win and open-source code. The main risk is that the stated insights are supported by raw counts over heavily duplicated benchmark families and by single unseeded runs of a stochastic local search. I recommend requiring a per-family analysis and a reproducibility statement for the ILS before publication; the central solver description does not need to change."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the competition win is real and the paper ships code and tables, but the two headline insights are based mostly on near-duplicate instances, so the significance of those insights is inflated. Still worth refereeing.\n\nWhat's genuinely new: FullA, the portfolio, won the PACE vertex cover track by 10 instances. The combination of kernelization plus ILS-seeded branch-and-reduce plus MoMC on kernel and original graph is new and well described. The counterexample to 'kernelization always helps B&B'—instances 131 and 157, where reductions add edges and MoMC solves the original but not the kernel—is a real observation. Good news: code is public on Zenodo, the method section is clear, and the tables let you check the claims.\n\nWhere it gets soft: the ablation counts. LSBnR's 13-instance edge over BnR is 12 copies of the same n=26300, m=41500, kernel=500/3000, |VC|=16300 family plus one row. RMoMC's 26-instance edge over BnR is at least 23 instances from two families with identical (n,m,kernel,optimum). Treating these as independent successes makes the 'first time kernelization plus B&B beats BnR' and 'local search significantly boosts BnR' claims look stronger than the evidence. The ILS runs are single-shot with no seeds, so the local search boost is confounded with luck. Private-instance results can't be checked because the instances aren't released. Time limits are hand-set without sensitivity analysis.\n\nNone of these are fatal to the competition result. FullA's win and the negative-result observation stand. But the paper's central stated insights need either deduplicated reporting, per-family analysis, or at least a paragraph acknowledging the duplication. As is, I'd call the paper a solid competition report with an over-claimed analysis.\n\nI'd send this to an experimental-algorithms venue (SEA/ALENEX type) with a request to fix the ablation claims. A serious referee can handle it; the underlying engineering is honest and reproducible.","headline":"The PACE win is credible and the code is public, but the paper's two headline insights rest on near-duplicate instances and unseeded runs, so the ablation claims are over-sold.","tokens_in":17176,"tokens_out":3907,"would_cite":true,"duration_ms":34364,"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":"The winning solver of the 2019 vertex cover challenge is a scheduled portfolio that first shrinks the graph with reduction rules, then alternates two search paradigms, and the paper shows the shrink step is what makes a clique-style…","keywords":["minimum vertex cover","kernelization","branch-and-bound","branch-and-reduce","local search","maximum clique","maximum independent set","PACE 2019"],"falsifier":"Run the same configurations—plain branch-and-bound, kernelized branch-and-bound, branch-and-reduce with and without a local-search starting solution, and the full portfolio—on a fresh corpus of 100 previously unseen instances that includes dense graphs, under the same 30-minute budget; the central claim would be contradicted if kernelized branch-and-bound no longer solves more instances than branch-and-reduce, or if the portfolio's margin collapses.","tokens_in":16180,"feed_emoji":"🧩","tokens_out":8249,"duration_ms":77097,"temperature":0.7,"pith_summary":"The paper claims that the best way to solve hard minimum vertex cover instances exactly is not a single algorithm but a time-scheduled pipeline: aggressively shrink the graph with reduction rules, obtain a strong starting solution by local search, then alternate branch-and-reduce and branch-and-bound search under short and long time limits. The authors show that two techniques borrowed from the complementary maximum clique and maximum independent set problems carry most of the gain. Kernelization lets a state-of-the-art branch-and-bound clique solver, run on the complement graph, solve more than twice as many public instances as it could without reduction, and a local-search starting solution lets branch-and-reduce solve more instances than it could alone. The challenge result is the evidence: the full portfolio solved 82 of 100 public instances and 87 of 100 held-out private instances, ten more than the runner-up. The paper also records a counterintuitive side effect: reductions can occasionally make the kernel harder for branch-and-bound, so a robust solver should search both the kernel and the original graph.","feed_headline":"Solver that shrinks graphs first wins vertex cover challenge","feed_subtitle":"Reduction rules, local search, and clique search on complements solved 87 of 100 private instances.","key_machinery":"The load-bearing identity is the complement relation among the three problems: a minimum vertex cover of $G$ is the complement of a maximum independent set, which is a maximum clique in the complement graph. The portfolio combines four mechanisms. Kernelization repeatedly applies data-reduction rules—degree-one removal, vertex folding, an LP-relaxation reduction, and unconfined, twin, funnel, and desk reductions—to shrink the graph while preserving a minimum vertex cover. Iterated local search based on $(1,2)$-swaps finds a high-quality initial cover on the kernel. Branch-and-reduce interleaves the same reductions with branching, mirror and satellite elimination, and lower-bound pruning. MoMC is a branch-and-bound maximum-clique solver using incremental MaxSAT reasoning to prune search, run on the complement graph of both the kernel and the original input. The phase order and time limits (one second for short phases, thirty seconds for the long branch-and-reduce phase, then the remaining budget for branch-and-bound) are what make the portfolio work.","core_discovery":"The central discovery is that kernelization and branch-and-bound compose in a way the vertex cover literature had not demonstrated. On the 100 public instances, plain branch-and-bound solved 30 instances, but the same solver run on the reduced kernel solved 68; branch-and-reduce with reductions but no local search solved 42, and adding a locally searched initial solution raised that to 55. The complete portfolio solved 82 public and 87 private instances within the 30-minute competition limit. The paper claims this is the first time kernelization followed by branch-and-bound is shown to significantly outperform branch-and-reduce, and it explains a necessary detail: the branch-and-bound solver must also be run on the original graph, because the alternative reduction can increase the number of edges and make the kernel harder than the input.","pith_inferences":["Inference: an adaptive kernelizer that only keeps reductions when they do not increase the edge count, or that falls back to the original graph on edge growth, could recover the two documented hard cases without paying for two full searches.","Inference: the same portfolio-scheduling idea—kernelize, seed with local search, then time-slice a reduce-heavy and a bound-heavy solver—may transfer to other NP-hard problems that have practical kernelizations and strong branch-and-bound solvers.","Inference: the hand-tuned phase time limits suggest a testable extension in which the schedule is learned from instance features on the public corpus and then evaluated on held-out instances, which would measure how much of the win depends on the tuning rather than on the component algorithms."],"forward_implications":["Exact minimum vertex cover solvers should be built as pipelines rather than as single algorithms: kernelize, obtain a good initial solution by local search, then let branch-and-reduce and branch-and-bound share the remaining time budget.","Because vertex cover, maximum independent set, and maximum clique are complementary, the same pipeline transfers directly to solving maximum clique or maximum independent set on sparse graphs.","Kernelization is not always safe for branch-and-bound: since reductions can increase the number of edges, a robust solver should search both the kernel and the original graph unless it can prove the kernel is easier.","Branch-and-reduce benefits substantially from a high-quality initial solution produced by local search on the kernel, even though the reduction rules themselves do not depend on it."],"supporting_citations":[{"why":"supplies the full suite of kernelization reductions and the branch-and-reduce algorithm that the portfolio is built around.","marker":"[2]"},{"why":"provides MoMC, the branch-and-bound maximum-clique solver that is run on the complement graph.","marker":"[28]"},{"why":"provides the iterated local search with (1,2)-swaps that computes the initial high-quality solution on the kernel.","marker":"[3]"},{"why":"shows that an initial solution from local search can speed up branch-and-bound clique search, the effect the paper transfers to branch-and-reduce.","marker":"[4]"},{"why":"gives the LP-relaxation reduction that fixes vertices in the minimum vertex cover during kernelization.","marker":"[30]"},{"why":"improves the LP-based reduction to run in linear time via network flow, making the kernelization fast enough for the pipeline.","marker":"[24]"},{"why":"supplies the unconfined, twin, funnel, and desk reductions used to shrink the kernel.","marker":"[43]"},{"why":"introduces vertex folding, one of the core reduction rules for degree-two vertices.","marker":"[10]"}],"fun_headline_variants":["Kernelization boosts branch-and-bound to beat branch-and-reduce","New solver shrinks first, then searches, wins PACE 2019","Vertex cover: shrink graph first, then branch and bound wins","Local search and kernelization key to PACE vertex cover win","Surprise: kernelization can hurt branch-and-bound alone"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the 100 public and 100 private benchmark instances, with a fixed 30-minute time limit and hand-tuned phase time limits, stand in for the space of exact vertex cover instances; the paper itself notes that reduction-based techniques rarely work on dense graphs.","fun_headline_variants_meta":{"raw":{"variants":["Kernelization boosts branch-and-bound to beat branch-and-reduce","New solver shrinks first, then searches, wins PACE 2019","Vertex cover: shrink graph first, then branch and bound wins","Local search and kernelization key to PACE vertex cover win","Surprise: kernelization can hurt branch-and-bound alone"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1736,"prompt_tokens":912,"completion_tokens":824,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":735}},"tokens_in":528,"tokens_out":824,"duration_ms":7394,"temperature":1.0,"reasoning_tokens":735,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:34:39.984330+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same configurations—plain branch-and-bound, kernelized branch-and-bound, branch-and-reduce with and without a local-search starting solution, and the full portfolio—on a fresh corpus of 100 previously unseen instances that includes dense graphs, under the same 30-minute budget; the central claim would be contradicted if kernelized branch-and-bound no longer solves more instances than branch-and-reduce, or if the portfolio's margin collapses.","supporting_citations":[{"cited_title":"Batsyn, B","cited_arxiv_id":null,"evidence_quote":"shows that an initial solution from local search can speed up branch-and-bound clique search, the effect the paper transfers to branch-and-reduce."},{"cited_title":"Nemhauser and L","cited_arxiv_id":null,"evidence_quote":"gives the LP-relaxation reduction that fixes vertices in the minimum vertex cover during kernelization."},{"cited_title":"Iwata, K","cited_arxiv_id":null,"evidence_quote":"improves the LP-based reduction to run in linear time via network flow, making the kernelization fast enough for the pipeline."}],"review_version":1}