{"id":"b7d85fb8-c6ca-4413-bcac-1215dedbffb8","arxiv_id":"1908.07318","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A branching algorithm for destroying claws and diamonds in a graph runs in O*(3.562^k) time, improving the previous O*(3.792^k) bound.","lead":"This paper gives a faster branching algorithm for the {Claw,Diamond}-Free Edge Deletion problem, improving the running time from O*(3.792^k) to O*(3.562^k). The result is a step toward understanding polynomial kernels for the related Claw-Free Edge Deletion problem.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Rule (5) computer-assisted 18-case enumeration is the load-bearing unverified step; the reported worst-case vector checks out, but the full table/script is needed to certify the 3.562 bound.","rationale":"The central claim is a fixed-parameter algorithm with a branching number of 3.562. The derivation of the constant relies on a finite case analysis in Rule (5) that is not documented. Our own spot-check of the stated worst case confirms the reported vector, so the flaw is not a known error but a substantial reproducibility gap: the 18-case enumeration is load-bearing and cannot be audited from the manuscript. We agree with the reader that this warrants a CONDITIONAL verdict. The Rule (6) F-list typo is notable but does not change the branching vector, and our corrected reading gives the same 3.562 bound. No fundamental flaw was found.","tokens_in":2910,"tokens_out":44790,"duration_ms":407891,"concrete_test":"Write a script that, for each of the 18 graphs defined in Rule (5), generates all inclusion-minimal deletion sets of G[{a,b,c,d,s,t}] (by checking all subsets of the at most 10 edges for the property that the remaining graph has no induced claw or diamond), records the branching vector, and computes the branching number. Verify that the maximum is at most 3.533 and that the reported worst case reproduces the vector (1,1,2,2,2,2,3,3,3,3,3). Release the script and table alongside the paper.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The claimed O*(3.562^k) bound is the maximum of branching numbers of Rules (3)-(7). Rule (5) is the only step justified by an undocumented Python enumeration of 18 graphs on {a,b,c,d,s,t}. We manually re-derived the stated worst case (N(t)∩{b,d}={b}, N(s)∩{a,b,c,d}={a,b}) and found exactly 11 minimal deletion sets with sizes (1,1,2,2,2,2,3,3,3,3,3), matching the paper. This makes the reported worst-case plausible. However, the paper does not give the script or a table for the other 17 cases, and no formal proof is supplied. A single case with a branching number above 3.562 would invalidate the headline bound, since Rule (5) is applied before Rule (6) and the overall running time is determined by the worst rule. The reader's verdict of CONDITIONAL is appropriate pending independent reproduction of this enumeration. Separately, Rule (6)'s printed F list contains an apparent typo—'{bt, ac}' should be '{bt, ad}'—but this does not affect the branching vector once corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a fixed-parameter branching algorithm for {Claw,Diamond}-Free Edge Deletion, the problem of deciding whether a graph can be made induced-claw-free and induced-diamond-free by deleting at most k edges. The algorithm applies seven branching rules. Rules (3) and (4) handle induced claws and symmetric diamonds; Rule (5) handles a diamond with two asymmetric external vertices using a computer-assisted enumeration of 18 induced 6-vertex configurations; Rules (6) and (7) handle the remaining asymmetric cases. The worst-case branching number over all rules is claimed to be that of Rule (6), giving a claimed running time of O*(3.562^k), improving on the previous O*(3.792^k) bound.","tokens_in":3142,"tokens_out":18058,"duration_ms":170950,"significance":"If the claimed running time is correct, this is the fastest known fixed-parameter algorithm for {Claw,Diamond}-Free Edge Deletion and a meaningful improvement in the parameterized complexity of a graph modification problem connected to polynomial kernelization for Claw-Free Edge Deletion. The branching framework is explicit and the safeness arguments for Rules (4), (6), and (7) are based on concrete isomorphisms; I verified the key isomorphism in Rule (6) once the printed edge list is corrected. The reported worst-case branching vector of Rule (5), (1,1,2,2,2,2,3,3,3,3,3), is also consistent with a manual check of that case. The main obstacle to accepting the bound is that Rule (5) rests on an undocumented 18-case computer enumeration, and Rule (7) states a branching vector without showing the corresponding deletion sets.","major_comments":[{"comment":"The correctness of the entire O*(3.562^k) bound depends on the assertion that, among the 18 cases for the graph induced by {a,b,c,d,s,t}, the largest branching number is at most 3.533. The paper only states this and gives the worst-case vector; it does not provide the Python script, the list of deletion sets for the other 17 cases, or a table of their branching vectors. Because Rule (5) is applied before Rule (6), a single overlooked case with branching number above 3.562 would invalidate the headline bound. Please supply the script, a complete table of all 18 cases with their inclusion-minimal deletion sets and branching vectors, or a formal enumeration proof.","section":"Section 2, Rule (5)"},{"comment":"The printed set F(G[{a,b,c,d,t}]) = {{ab},{bc},{ac},{at,ad},{at,cd},{bt,ac}} is incorrect: {bt,ac} is not inclusion-minimal because {ac} is already a minimal deletion set, while the minimal set {bt,ad} is omitted. Interpreting the list literally would make the algorithm branch on a redundant set and skip a needed branch. The intended entry is almost certainly {bt,ad}; with that correction the branching vector (1,1,1,2,2) and the claimed bound 3.562 follow. Please fix this typo and verify that no other minimal deletion set is missing.","section":"Section 2, Rule (6)"},{"comment":"The case split is confusing and the claimed branching vector is not justified in the text. The condition \"Otherwise (namely, if t is adjacent to b)\" contradicts the preceding rule, which already handled the case where t is not adjacent to d; the intended condition appears to be \"if t is adjacent to d\". More importantly, the rule states that F(G[{a,b,c,d,t}]) has twelve size-2 sets, but neither the set F nor the deletion sets are listed, and no symmetry argument is given to justify the 12-term branching vector (2,2,2,2,2,2,2,2,2,2,2,2). Since this contributes to the overall running time, please provide the explicit list of minimal deletion sets (or a complete enumeration) for this case.","section":"Section 2, Rule (7)"}],"minor_comments":[{"comment":"There are several typos: \"th is\", \"Preleminaries\", \"polynomail\", \"subexpontial-tim e\", \"algorith\", and \"an algorithm for whose running time\" should be \"an algorithm whose running time\". These should be corrected.","section":"Section 1 and Abstract"},{"comment":"The bullet-list argument for the 18 cases is terse, especially the sentence \"If s is adjacent to c, the vertices s,t can be either adjacent or non-adjacent. If s is adjacent to a then s,t are adjacent, otherwise {a,c,s,t} induces a claw.\" The second sentence concerns the case where s is adjacent to a, not to c; rewording would prevent confusion.","section":"Section 2, Rule (5)"},{"comment":"The notation F(G[{a,b,c,d,t}]) is reused in Rules (6) and (7) for two different induced subgraphs (t adjacent to b only, versus t adjacent to both b and d). Please use distinct names or explicitly redefine the set in each rule to avoid ambiguity.","section":"Section 2, Rules (6) and (7)"}],"recommendation":"major_revision","confidential_remarks":"The central obstruction is the undocumented computer enumeration in Rule (5); if the author can supply the script or a complete table, the result is likely correct. The Rule (6) typo and the missing details in Rule (7) are fixable but need to be addressed before the branching-vector analysis can be accepted as rigorous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a new branching algorithm for {Claw,Diamond}-Free Edge Deletion, improving the running time from O*(3.792^k) to O*(3.562^k). That is a real, if modest, advance in the parameterized complexity of this NP-hard problem. The algorithm itself is clearly structured: the rules are precisely defined, and the safeness arguments for Rules (4), (6), and (7) are explicit isomorphism-based justifications. I spot-checked Rule (6) and the intended symmetry argument holds. Rule (4) is straightforward and correct. The recurrence analysis that produces the final bound is standard and self-contained, with no fudged constants, and the claimed bound is the actual maximum over the branching numbers of the rules. This is a solid piece of work within an established research program, not a routine application of known techniques.\n\nThe main soft spot is Rule (5). The paper justifies the worst-case branching vector by saying a Python script enumerated 18 possible graphs on {a,b,c,d,s,t} and gives the worst case (1,1,2,2,2,2,3,3,3,3,3) with branching number at most 3.533. But it does not provide the script, nor a complete table of all 18 cases, nor a formal proof. The stress-test independently re-derived the stated worst case and found exactly the same 11 minimal deletion sets, so the reported vector is plausible. But this is a load-bearing premise: a single miscalculated case could invalidate the headline bound. For a paper whose central claim is a constant-factor improvement, the authors should either include the enumeration script or give a human-verifiable table.\n\nThere is also a typo in Rule (6): the printed F(G[{a,b,c,d,t}]) contains '{bt, ac}', but that set is not a deletion set (it leaves a claw centered at a). It should be '{bt, ad}'. Once corrected, the branching vector (1,1,1,2,2) is right and the rule is safe. This is a minor exposition bug, but as written it makes the rule literally unsafe if taken at face value. The authors should fix it in revision.\n\nOverall, the mathematics is sound and the improvement is legitimate. The paper deserves a serious referee and will likely be publishable after the Rule (5) documentation is added and the Rule (6) typo is corrected. I would bring it to a reading group focused on parameterized branching algorithms; for my own work I would cite it as the current best bound for this problem.","headline":"A genuine but incremental FPT improvement for {Claw,Diamond}-Free Edge Deletion, with a load-bearing computer-assisted case analysis that needs to be fully disclosed.","tokens_in":3628,"tokens_out":4805,"would_cite":true,"duration_ms":46667,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The {Claw,Diamond}-Free Edge Deletion problem is solvable in O*(3.562^k) time by a symmetry-pruned branching algorithm.","keywords":["graph algorithms","parameterized complexity","branching algorithms","edge deletion","claw-free graphs","diamond-free graphs","induced subgraphs","fixed-parameter tractability"],"falsifier":"Independently enumerate all 18 graph cases described in Rule (5), compute the inclusion-minimal deletion sets of each, and calculate the branching number of each resulting branching vector; if any case exceeds the reported maximum of 3.533, or if Rule (6)'s vector is not $(1,1,1,2,2)$ with branching number at most $3.562$, the running-time claim is false.","tokens_in":2687,"feed_emoji":"✂️","tokens_out":11273,"duration_ms":106232,"temperature":0.7,"pith_summary":"The paper claims a faster fixed-parameter algorithm for the {Claw,Diamond}-Free Edge Deletion problem, where the goal is to delete at most $k$ edges from a graph so that no induced claw or diamond remains. The algorithm runs in $O^*(3.562^k)$ time, improving on the previous $O(3.792^k)$ bound. It is a branching algorithm that repeatedly finds an induced claw or diamond, branches over the minimal deletion sets of a small enclosing induced subgraph, and removes symmetric branches using graph isomorphisms. The worst-case rule has branching vector $(1,1,1,2,2)$ with branching number $3.562$, and the rule handling six vertices relies on a computer enumeration of 18 cases. If the analysis is correct, this is the fastest known algorithm for the problem.","feed_headline":"Faster algorithm deletes claws and diamonds in 3.562^k time","feed_subtitle":"The seven-rule branching algorithm beats the previous best base of 3.792 for this edge-deletion problem.","key_machinery":"The carrying mechanism is a branching algorithm whose state is the current graph and remaining bound $k$, with seven reduction and branching rules. The central analytic object is the branching vector of a rule, the list of edge-deletion counts in its recursive branches, and the associated branching number, the positive root of $\\sum_i x^{-b_i}=1$ that bounds the running-time recurrence. Rule (5) is the only computational step: for each of 18 possible graphs on the six vertices $\\{a,b,c,d,s,t\\}$ it computes the set of inclusion-minimal deletion sets and uses the worst case, with branching vector $(1,1,2,2,2,2,3,3,3,3,3)$ and branching number at most $3.533$. Rules (4), (6), and (7) work by observing that deleting one edge and then considering the enclosing subgraph often yields a graph isomorphic to the graph produced by deleting a different edge, so the isomorphic branch can be discarded. The maximum over all rules of the branching number is $3.562$, attained by Rule (6).","core_discovery":"The central discovery is that the structure of a minimal claw-and-diamond-free deletion set can be resolved by branching on tiny induced subgraphs, and that symmetry between the modified graphs makes many branches redundant. Concretely, the paper proves that {Claw,Diamond}-Free Edge Deletion is solvable in $O^*(3.562^k)$ time by a seven-rule branching algorithm. Once a claw is present, Rule (3) branches on its three edges; once the graph is claw-free but contains a diamond $a,b,c,d$, the algorithm branches on the minimal deletion sets of $G[\\{a,b,c,d\\}]$, and when needed, on the five- or six-vertex induced subgraphs that include one or two extra vertices $t$ and $s$. Rules (4), (6), and (7) identify isomorphic modified graphs and skip the duplicate branches; the reported worst case is Rule (6) with branching vector $(1,1,1,2,2)$ and branching number $3.562$, while Rule (5) has maximum branching number at most $3.533$.","pith_inferences":["The same case-enumeration scheme should generalize to deleting other constant-size induced forbidden subgraphs: whenever the minimal deletion sets of small witness graphs can be computed, a Rule (5)-style finite check can set the branching base.","A concrete verification step for the paper's bound would be to release the Python script behind Rule (5); an independent run over all 18 cases would settle whether the worst-case vector $(1,1,2,2,2,2,3,3,3,3,3)$ is correct.","Because Rule (6) is the stated bottleneck, any future attempt to push the base below $3.562$ should focus on the five-vertex case, for example by adding a new rule that detects when one of the deletion sets in $F(G[\\{a,b,c,d,t\\}])$ is redundant.","The paper leaves open whether the same branching base can be translated into a polynomial kernel for the problem; the kernelization question in the introduction is independent of the running-time result."],"forward_implications":["The fastest known running time for this problem becomes $O^*(3.562^k)$, replacing the previous $O(3.792^k)$ algorithm.","The algorithm is correct for every input graph: any instance whose answer is 'yes' has a deletion set of size at most $k$, and the branching rules only ever split into cases that cover all inclusion-minimal deletion sets of the witness subgraph.","The worst case is concentrated in Rule (6), so the five-vertex configuration determines the asymptotic exponent; the six-vertex Rule (5) case is slightly easier, at branching number at most $3.533$.","A direct corollary of the rule analysis is that no branch deletes more than three edges, so the recursion depth is at most $k$ and the algorithm is a standard fixed-parameter branching algorithm."],"supporting_citations":[{"why":"Introduces the problem, proves NP-hardness and the no-subexponential-time consequence under ETH, and motivates the kernelization connection.","marker":"[3]"},{"why":"Gives the previous best $O(3.792^k)$ algorithm that this paper improves.","marker":"[4]"},{"why":"Provides the baseline simple $O^*(5^k)$-time algorithm for the problem.","marker":"[1]"},{"why":"Supplies the branching-algorithm framework used throughout the paper.","marker":"[2]"}],"fun_headline_variants":["Claw and diamond deletion in 3.562^k","Faster claw-diamond deletion: base 3.562","Claw-Diamond-Free Deletion in 3.562^k","Claw-diamond deletion drops to 3.562^k"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O^*(3.562^k)$ bound depends on the unprinted computer enumeration of the 18 possible six-vertex graphs in Rule (5); if that enumeration is incomplete or a branching number is miscalculated, the claimed worst-case bound could be too low.","fun_headline_variants_meta":{"raw":{"variants":["Claw and diamond deletion in 3.562^k","Faster claw-diamond deletion: base 3.562","Claw-Diamond-Free Deletion in 3.562^k","Claw-diamond deletion drops to 3.562^k"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001289,"raw_usage":{"total_tokens":5208,"prompt_tokens":834,"completion_tokens":4374,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":450,"completion_tokens_details":{"reasoning_tokens":4303}},"tokens_in":450,"tokens_out":4374,"duration_ms":30392,"temperature":1.0,"reasoning_tokens":4303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:20:29.557757+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently enumerate all 18 graph cases described in Rule (5), compute the inclusion-minimal deletion sets of each, and calculate the branching number of each resulting branching vector; if any case exceeds the reported maximum of 3.533, or if Rule (6)'s vector is not $(1,1,1,2,2)$ with branching number at most $3.562$, the running-time claim is false.","supporting_citations":[{"cited_title":"Cygan, M","cited_arxiv_id":null,"evidence_quote":"Introduces the problem, proves NP-hardness and the no-subexponential-time consequence under ETH, and motivates the kernelization connection."},{"cited_title":"Improved Kernels and Algorithms for Claw and Diamond Free Edge Deletion Based on Refined Observations","cited_arxiv_id":"1707.06779","evidence_quote":"Gives the previous best $O(3.792^k)$ algorithm that this paper improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the baseline simple $O^*(5^k)$-time algorithm for the problem."}],"review_version":1}