REVIEW 3 major objections 3 minor 4 references
An algorithm for destroying claws and diamonds
T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The {Claw,Diamond}-Free Edge Deletion problem is solvable in O*(3.562^k) time by a symmetry-pruned branching algorithm.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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).
What would settle it
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.
Extended reading notes
Core claim
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$.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 2, Rule (5)] 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 2, Rule (6)] 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 2, Rule (7)] 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.
minor comments (3)
- [Section 1 and Abstract] 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 2, Rule (5)] 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 2, Rules (6) and (7)] 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.
Circularity Check
No significant circularity: the O*(3.562^k) bound is derived from explicitly defined branching rules with standard recurrence analysis, not from fitted parameters or self-citation.
full rationale
The paper's central claim is a worst-case running-time bound for a branching algorithm. The bound is obtained by enumerating the branching vectors of Rules (3)-(7), each of which is computed from explicitly listed inclusion-minimal deletion sets of small induced subgraphs. For example, Rule (6) gives branching vector (1,1,1,2,2) from F(G[{a,b,c,d,t}]) = {{ab},{bc},{ac},{at,ad},{at,cd},{bt,ac}}, and the stated bound 3.562 is the resulting branching number. No parameter is fitted to a desired running time, and no result from the author's prior work is invoked to justify the algorithm or its analysis. Rule (5)'s computer-assisted enumeration of 18 cases is a verification step, not an input to the derivation that is then relabeled as a prediction; its completeness is a correctness risk, not a circularity. The safeness of the rules is justified by isomorphism/symmetry arguments relative to the definition of deletion sets. Consequently, the derivation is self-contained against the problem definition and contains no circular step.
Assumptions & free parameters
assumptions (3)
- ad hoc to paper The Python script correctly enumerates the 18 cases for Rule (5) and computes their branching vectors, with worst-case branching number 3.533.
- domain assumption The isomorphism arguments in Rules (4), (6), and (7) correctly identify equivalent branches.
- domain assumption The case distinction from Rule (3) onward is exhaustive for a claw-free graph containing a diamond.
Cite this review
Pith. "Pith review of An algorithm for destroying claws and diamonds." pith.science (2026). https://pith.science/paper/LDWR7YEC
@misc{pith2026190807318,
author = {Pith},
title = {Pith review of: An algorithm for destroying claws and diamonds},
year = {2026},
howpublished = {\url{https://pith.science/paper/LDWR7YEC}},
note = {Machine review of arXiv:1908.07318}
}
abstract
In the {Claw,Diamond}-Free Edge Deletion problem the input is a graph $G$ and an integer $k$, and the goal is to decide whether there is a set of edges of size at most $k$ such that removing the edges of the set from $G$ results a graph that does not contain an induced claw or diamond. In this paper we give an algorithm for this problem whose running time is $O^*(3.562^k)$.
Reference graph
Works this paper leans on
-
[1]
L. Cai. Fixed-parameter tractability of graph modification proble ms for heredi- tary properties. Information Processing Letters, 58(4):171–176, 1996
work page 1996
-
[2]
Cygan, F
M. Cygan, F. V. Fomin, /suppress L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015
2015
- [3]
-
[4]
W. Li, J. Wang, and Y. Yang. Improved kernels and algorithms for claw and diamond free edge deletion based on refined observations. arXiv preprint arXiv:1707.06779, 2017. 3
work page Pith review arXiv 2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.