{"id":"69ce58dc-48ee-4a8a-92b0-3b5e115b1e5e","arxiv_id":"2507.09377","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A Python implementation of a standard vertex-cover branching algorithm is benchmarked against SageMath, but the claimed O(n·1.71^k) complexity is only empirically fitted and the experiments are under-specified.","lead":"This paper describes a Python implementation of a standard fixed-parameter branching algorithm for vertex cover and compares it with SageMath on synthetic graphs. The reported speedups cannot be verified because code, graph generation details, and a formal complexity derivation are all missing.","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central performance claim rests on an unreported and likely trivial graph-generation protocol; the reported timings are irreproducible and inconsistent with any O(n · 1.71^k) search, so the empirical complexity is unsupported.","rationale":"The reader's weakest assumption identifies the unreported synthetic graph generation and the condition that the true minimum vertex cover equals k. My stress-test agrees and sharpens the point: the reported wall-clock numbers are not merely hard to verify, they are internally inconsistent with the paper's own claimed complexity. For k = 1,000, any algorithm with a 1.71^k search tree would require an infeasible number of operations; the reported 279 ms can only hold if the benchmark graphs cause the algorithm to avoid branching almost entirely. Thus the central claim—that the implementation demonstrates FPT behavior with O(n · 1.71^k)—is not supported by the evidence presented. This is a correctness-risk concern about the empirical argument, not about the logical soundness of the textbook branching skeleton, which I read as essentially correct. The paper could become a useful implementation report only if the generator, code, node counts, and a real benchmark protocol are supplied. Because the reader already rejected on these grounds, my assessment does not change the verdict.","tokens_in":6349,"tokens_out":3855,"duration_ms":47193,"concrete_test":"Release the exact graph generator and code, then rerun on at least three families: (i) disjoint unions of P3 paths; (ii) random graphs with a planted minimum vertex cover of size k, with edge probabilities chosen so the true cover size is k and the graph is connected or dense enough to force real branching; (iii) a standard benchmark set such as DIMACS or random regular graphs. Instrument the implementation to report the number of recursive calls (search-tree nodes) as a function of k at fixed n, and separately fit the growth in node count. If the node count does not scale like c^k with c near 1.71 on families (ii) and (iii), the empirical O(n · 1.71^k) claim is not established and the Table 1 speedups likely reflect easy instance structure. If even family (i) causes exponential blow-up, the implementation's branch-case handling would need re-examination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Section 5 claim an 'empirically observed complexity of O(n · 1.71^k)' and large speedups over SageMath. The only evidence is Table 1, whose instances are not reproducible: Section 4.1 states 'the specific graph generation method is not detailed', and Section 4.2 restricts the results to graphs where the actual minimum vertex cover size equals k. This is load-bearing because the timings themselves are inconsistent with the claimed exponential growth. For n = 10,000 and k = 1,000, 1.71^1000 is astronomically large; a recursive search visiting even a tiny fraction of such a tree cannot complete in 279.79 ms on a 2 GB CPU-only web application. The only way the table is plausible is if the synthetic graphs are so structured that the branching step almost never fires (for example, unions of disjoint edges or isolated P3s), in which case the runtimes reflect a trivial polynomial check, not FPT branching behavior. The table also shows non-monotonic runtime in k (e.g., n = 200,000: 75.83 ms at k = 50 versus 21.70 ms at k = 100), with no repeats, variance, or instance family described. The SageMath baseline is similarly unspecified as to version and exact function. The branching algorithm in Section 3.1 appears logically sound as a decision procedure; the unsupported part is the claimed practical complexity and the comparison. Without code, data, or a generator description, the central contribution is an unreviewable and likely misleading benchmark.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a recursive FPT branching algorithm for the Minimum Vertex Cover decision problem, parameterized by the cover size k. At each step the algorithm searches for an induced path on three vertices and tries five ways of adding vertices from that path to the cover, with a base case that handles residual isolated edges. The authors implement the algorithm in Python and report wall-clock comparisons against SageMath on synthetic graphs, concluding that the algorithm has empirically observed complexity O(n·1.71^k) and outperforms SageMath for large n and small k. The paper provides no pseudocode or code, no graph-generation details, and no formal correctness or complexity proof.","tokens_in":6644,"tokens_out":9643,"duration_ms":106292,"significance":"The underlying P3-branching idea is standard and the algorithm is likely correct as a decision procedure, but the paper's contribution is presented as an empirical demonstration of practical FPT performance. If the benchmark were trustworthy, the results would be a mildly useful data point that a simple P3-branching solver can beat a general exact solver on sparse instances with small vertex cover. The paper is explicitly honest that 1.71 is an empirical constant rather than a derived worst-case base, and it cites the standard FPT literature; however, the central empirical claim is not reproducible and the reported timings are numerically inconsistent with the claimed complexity.","major_comments":[{"comment":"The benchmark is irreproducible. Section 4.1 states 'the specific graph generation method is not detailed', no code or data are provided, no repeated trials or error bars are reported, and Section 4.2 restricts the table to instances in which the actual minimum vertex cover equals k. More importantly, the timings are inconsistent with the claimed O(n·1.71^k) complexity: for k=1000, 1.71^1000 is on the order of 10^233, so the nominal search tree cannot be traversed in 279.79 ms on a 2GB CPU-only machine. The only way to reconcile the table is to suppose that the generated graphs cause almost no branching, in which case the runtimes reflect a trivial instance family rather than FPT branching behavior. The experiment must be replaced with a fully specified generator, available code/data, and a count of search-tree nodes or branching events as a function of k.","section":"Section 4.1, Table 1"},{"comment":"The complexity claim is fitted, not derived. For the five branch cases with budget reductions 2, 2, 2, 1, and 3, the recurrence is T(k)=3T(k-2)+T(k-1)+T(k-3), whose characteristic polynomial r^3-r^2-3r-1 has dominant root 1+sqrt(2) ≈ 2.414; even the standard two-branch P3 rule has root phi ≈ 1.618. The paper offers no derivation of 1.71, and the table itself contradicts a monotone dependence on k: at n=200000 the runtime decreases from 75.83 ms at k=50 to 21.70 ms at k=100. The claimed O(n·1.71^k) must either be derived from the actual branch rules or replaced by a rigorously measured scaling law.","section":"Sections 4.3 and 5"},{"comment":"The algorithm is described only informally; there is no pseudocode, no termination proof, and no correctness theorem. The prose does not state how the isolated-edge base case is implemented (e.g., whether one vertex is charged per remaining edge, which is trivial for a matching), and the five branching cases include redundant supersets such as 'add u and v' alongside 'add v'. Since the paper's central claim is that this algorithm solves Vertex Cover exactly, a formal specification with a proof that the branching is sound and complete is required.","section":"Section 3.1"},{"comment":"The SageMath baseline is underspecified: no version, no function name, and no indication of the algorithm used by the 'Exact Algo' column. Without that information the comparison does not establish that the FPT implementation is faster than a representative exact solver, and the paper's own caveat that 'a more comprehensive evaluation would involve testing against other state-of-the-art Vertex Cover solvers' should be a required part of the evidence, not future work.","section":"Section 4.1"}],"minor_comments":[{"comment":"The phrase 'Polynomial Time Complexity' is misleading: the stated bound is O(n·1.71^k), exponential in k, and Vertex Cover is NP-hard. The title and abstract should say 'fixed-parameter tractable' rather than implying a polynomial-time algorithm in both n and k.","section":"Title and Abstract"},{"comment":"The SageMath reference is incomplete: it contains the placeholders '[insert version used]' and '[insert year used]' and must be completed.","section":"Reference [18]"},{"comment":"There are typographical errors such as 'vertices ( n)' in Section 4.1 and 'fork = 1000' in Section 4.2 that should be corrected.","section":"Throughout"},{"comment":"The caption 'All valid/invalid possible combinations to form a triplet of vertices' is unclear; the caption should state exactly which combinations are valid or invalid for the branching rule.","section":"Figure 2"},{"comment":"The phrase 'trading memory for a smaller branching factor' conflates memoization with a change in the branching rule; memoization can reduce repeated work but does not by itself alter the branching factor, and this distinction should be stated.","section":"Section 4.3"}],"recommendation":"reject","confidential_remarks":"This manuscript reads as a preliminary student project rather than a journal submission: the benchmark is a single non-reproducible table, the central constant is an empirical fit, and the paper itself lists the required formal analysis and broader evaluation as future work. The numerical inconsistency between the claimed base 1.71 and the k=1000 row is severe enough that I would advise against requesting a revision; rejection is the appropriate outcome."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the algorithm described is a standard P3 branching routine and the correctness part reads fine, but the only new thing—the benchmark table—does not hold up. I would not trust the empirical claims.\n\nWhat is actually there: a clean description of the decision version of vertex cover solved by branching on a path of length 2. The five cases cover all ways a minimal cover can meet a P3, the base cases are right, and the leftover matching case is handled correctly. It is honest enough to cite Chen et al. for the usual 1.618 base and to label the 1.71 base as empirically observed rather than derived. None of this is new—P3 branching is textbook material—but as an exposition of a known algorithm it is coherent.\n\nThe soft spots are concentrated in Section 4. The generator is explicitly not detailed, no code or data are released, no repeats or variance are reported, and the SageMath baseline is not pinned to a version or exact function. More seriously, the timings are internally inconsistent with the claimed O(n·1.71^k). A search visiting even a negligible fraction of 1.71^1000 states cannot complete in 279.79 ms on a 2 GB CPU-only notebook. That table only makes sense if the synthetic graphs were so structured that branching almost never fires—disjoint edges or isolated P3s—in which case the times measure a trivial polynomial check, not FPT branching. The non-monotonic entries (75.83 ms for n=200k,k=50 vs 21.70 ms for k=100) reinforce that. The title's 'in Polynomial Time Complexity' is also misleading, since runtime is exponential in k.\n\nThe citation list has a few odd inclusions: seven self-citations to the author's control-barrier papers, none relevant to vertex cover. That is a minor annoying pattern, not a scientific flaw.\n\nWho gets value from this: an instructor looking for a clean student write-up of FPT branching, maybe. A researcher does not. The central performance claim is unsupported, and there is no formally verified or reproducible artifact to rescue it. I would desk-reject rather than send it to referees. If the authors add the generator, code, raw timings, and a proper baseline, an implementation report would be worth a look; as submitted, there is nothing to referee.","headline":"A textbook FPT branching algorithm with a believable correctness story, but the benchmark table is irreproducible and internally implausible, so the empirical claim fails.","tokens_in":7123,"tokens_out":3854,"would_cite":false,"duration_ms":44883,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a P3-branching FPT algorithm solves Minimum Vertex Cover with empirically observed O(n·1.71^k) time, beating SageMath by orders of magnitude when the cover is small.","keywords":["minimum vertex cover","fixed-parameter tractability","branching algorithm","P3 branching","parameterized complexity","exact algorithm","empirical complexity"],"falsifier":"Run the implementation on two families with the same n and k but different structure—for example random graphs with a planted k-cover versus sparse graphs with long cycles—and count branching calls instead of wall-clock time. If the number of recursive calls grows with n rather than depending only on k, the claimed $O(n \\cdot 1.71^k)$ is not the right model. A second check is to run the same graphs in a controlled environment with an explicit exact solver and compare node counts or search-tree sizes, which removes hardware and language differences from the comparison.","tokens_in":6113,"feed_emoji":"⚡","tokens_out":8854,"duration_ms":96799,"temperature":0.7,"pith_summary":"The paper claims that a deliberately simple recursive branching algorithm can solve the Minimum Vertex Cover problem exactly and quickly whenever the cover size k is small, even on graphs with hundreds of thousands of vertices. The implementation branches on a yet-uncovered path of three vertices, tries five ways of adding its endpoints to the cover, and backtracks after each try; on synthetic graphs it reports an empirically observed running time of $O(n \\cdot 1.71^k)$. In the reported benchmarks, the Python code finishes in milliseconds on graphs with up to 200,000 vertices and k up to 1,000, while SageMath's exact vertex cover routine takes seconds. The paper presents this as a demonstration that a textbook FPT branching pattern, not a heavily engineered solver, can make an NP-complete problem practically solvable for small-cover instances. The 'polynomial time' of the title is the FPT sense: polynomial in n for each fixed k, with the exponential dependency pushed entirely into k.","feed_headline":"A 5-way branching rule solves vertex cover in O(n·1.71^k)","feed_subtitle":"A Python FPT implementation finishes in milliseconds and beats SageMath when k is small.","key_machinery":"The load-bearing structure is the length-2 path of uncovered vertices u–v–w, with edges {u,v} and {v,w}. Whenever such a triplet exists, the algorithm opens five branches: add {u,v}, {u,w}, {v,w}, only v, or all three vertices to the selected cover, spending 2, 2, 2, 1, or 3 units of the remaining budget k, and it backtracks after each recursive call. When no triplet is left, the remaining graph has only isolated edges, and the algorithm covers each remaining edge with one budget unit. This branching scheme is what makes the runtime scale as $O(1.71^k \\cdot n)$; the search-tree size, not the per-node bookkeeping, is the dominant term.","core_discovery":"The central claim is that the P3-branching FPT algorithm solves the decision version of Minimum Vertex Cover in time governed by k rather than n. The author reports an empirically observed complexity of $O(n \\cdot 1.71^k)$ and tables where, for n up to 200,000 and k up to 1,000, the implementation runs in tens to hundreds of milliseconds while SageMath takes seconds. The paper attributes the base 1.71 to the five branching rules that reduce the remaining budget by 2, 2, 2, 1, or 3, and it explicitly notes that this is an empirical observation rather than a formal derivation. It compares 1.71 with the standard P3-branching constant 1.618 from the literature and with state-of-the-art vertex cover algorithms whose branching bases are below 1.3, acknowledging that the implemented rule is not theoretically optimal. The contribution, as the author states it, is to show how parameterization can render a classical NP-complete problem practically solvable on relevant instances rather than to improve the theoretical frontier.","pith_inferences":["The $O(n \\cdot 1.71^k)$ is an empirical fit rather than a worst-case guarantee; on graph families chosen adversarially, the same five-way branch rule could show a larger base, so the constant should be treated as a property of the tested synthetic family.","Wall-clock comparisons against SageMath mix Python implementation overhead with algorithmic behavior; counting recursive calls would isolate the search-tree size and give a fairer test of the claimed dependence on k.","The triplet-finding rule is arbitrary, so the method's transfer to dense or structured real-world graphs such as social networks, circuits, or protein networks is untested; node-count experiments on standard benchmark datasets would show whether the small-cover advantage persists.","Read strictly, the paper demonstrates the FPT principle for one branching rule; the title's 'polynomial time' should be understood as polynomial in n for each fixed k, not as polynomial-time solving of NP-complete instances in general."],"forward_implications":["If the observed $O(n \\cdot 1.71^k)$ behavior holds beyond the tested family, exact vertex cover becomes a millisecond-scale operation on graphs of hundreds of thousands of vertices whenever k is only a few hundred.","The advantage shrinks as k grows: at k = 1,000 on n = 100,000 the SageMath baseline becomes competitive, which is the expected crossover when the exponential term in k dominates.","Because recursion depth is bounded by the true minimum vertex cover size, passing an overestimated budget k does not slow the search; the run stops as though the budget were the actual cover size.","A plain Python implementation of the simplest P3 branching rule is enough to exhibit FPT-style behavior, which lowers the implementation barrier for applications with small covers.","The paper's comparison is specifically against SageMath on the tested instances, so the claim is a proof-of-concept of parameterization, not a blanket statement about all exact solvers."],"supporting_citations":[{"why":"This is the classical source for NP-completeness of Vertex Cover, the hardness fact the FPT framing responds to.","marker":"[17]"},{"why":"This is the SageMath system whose vertex cover function is the timing baseline in the experiments.","marker":"[18]"},{"why":"This reference supplies the definition of fixed-parameter tractability and the f(k)·poly(n) running-time framework.","marker":"[20]"},{"why":"This is the source of the standard P3-branching factor 1.618 against which the observed 1.71 is measured.","marker":"[21]"},{"why":"This is the reference for state-of-the-art vertex cover branching factors below 1.3, the benchmark for judging the algorithm's base.","marker":"[22]"},{"why":"This is the reference invoked for memoization and related optimizations that could reduce the branching factor.","marker":"[23]"}],"fun_headline_variants":["Vertex cover solved fast when k is small, via FPT branching","Python FPT vertex cover: milliseconds for large n, small k","FPT algorithm beats SageMath on vertex cover for small solutions","Empirical O(n·1.71^k) vertex cover: 5-way branching in Python","Parameterized vertex cover: fast on huge graphs when k is tiny"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise of the experimental claim is that the synthetic benchmark graphs, whose generation is not described and whose true minimum vertex cover is set to k, are representative of vertex cover instances in general; if those graphs are structurally easy, the reported $O(n \\cdot 1.71^k)$ behavior and the SageMath comparison do not transfer to arbitrary inputs.","fun_headline_variants_meta":{"raw":{"variants":["Vertex cover solved fast when k is small, via FPT branching","Python FPT vertex cover: milliseconds for large n, small k","FPT algorithm beats SageMath on vertex cover for small solutions","Empirical O(n·1.71^k) vertex cover: 5-way branching in Python","Parameterized vertex cover: fast on huge graphs when k is tiny"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1308,"prompt_tokens":939,"completion_tokens":369,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":555,"completion_tokens_details":{"reasoning_tokens":273}},"tokens_in":555,"tokens_out":369,"duration_ms":4862,"temperature":1.0,"reasoning_tokens":273,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:57:05.514757+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the implementation on two families with the same n and k but different structure—for example random graphs with a planted k-cover versus sparse graphs with long cycles—and count branching calls instead of wall-clock time. If the number of recursive calls grows with n rather than depending only on k, the claimed $O(n \\cdot 1.71^k)$ is not the right model. A second check is to run the same graphs in a controlled environment with an explicit exact solver and compare node counts or search-tree sizes, which removes hardware and language differences from the comparison.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This is the classical source for NP-completeness of Vertex Cover, the hardness fact the FPT framing responds to."},{"cited_title":"Sagemath, the Sage Mathematics Software System (Version [insert version used]),","cited_arxiv_id":null,"evidence_quote":"This is the SageMath system whose vertex cover function is the timing baseline in the experiments."},{"cited_title":"Fixed-parameter tractability and completeness,","cited_arxiv_id":null,"evidence_quote":"This reference supplies the definition of fixed-parameter tractability and the f(k)·poly(n) running-time framework."},{"cited_title":"A new branching strategy for vertex cover,","cited_arxiv_id":null,"evidence_quote":"This is the source of the standard P3-branching factor 1.618 against which the observed 1.71 is measured."},{"cited_title":"Cygan, F","cited_arxiv_id":null,"evidence_quote":"This is the reference for state-of-the-art vertex cover branching factors below 1.3, the benchmark for judging the algorithm's base."},{"cited_title":"Niedermeier, Invitation to Fixed-Parameter Algorithms","cited_arxiv_id":null,"evidence_quote":"This is the reference invoked for memoization and related optimizations that could reduce the branching factor."}],"review_version":1}