REVIEW 1 major objections 6 minor 8 references
Kernel for Kt-free edge deletion
T0 review · 1 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read K_t-free edge deletion has a kernel with $O(k^{t-1})$ vertices and edges.
desk verdict The kernel-size improvement is real, but the proof of Lemma 3 as written has a load-bearing gap that needs a fix. 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 central object is a sunflower in the family $\mathcal{F}_{xy}$ of vertex sets $X$ such that $X\cup\{x,y\}$ is a $t$-clique. A sunflower is a collection of sets whose pairwise intersections are the same core $Y$; the sunflower lemma guarantees that any sufficiently large family of sets of size at most $t-2$ contains one with $k+1$ petals, and that it can be found in polynomial time. The work it does is the reduction rule (R1): replacing all sets containing $Y\cup\{x,y\}$ with the single edge-set $E_{Y\cup\{x,y\}}$, which preserves the hitting-set property while collapsing many cliques into one. Iterating this rule is what forces the family size down to $O(k^{t-1})$.
What would settle it
Take $t=3$, build $G$ with many triangles all sharing a common edge, run the reduction, and check whether the graph $G'$ re-encoded from the compressed family still has exactly the same yes/no answer for small $k$; if one can find a $t$-clique in $G'$ that corresponds to no set in the compressed family, Lemma 5 fails.
Extended reading notes
Core claim
The central claim is that every instance $(G,k)$ of $K_t$-free edge deletion can be transformed in polynomial time into an equivalent instance $(G',k)$ with at most $O(k^{t-1})$ vertices and edges. The transformation first encodes each $t$-clique $X$ as the set $E_X$ of its $\binom{t}{2}$ edges, so that edge deletions correspond exactly to hitting sets of this family. For each edge $(x,y)$, the algorithm collects all vertex sets $X$ for which $X\cup\{x,y\}$ is a clique; when this collection is large, the sunflower lemma yields $k+1$ sets sharing a core $Y$, and the rule replaces every set containing $Y\cup\{x,y\}$ by the single set $E_{Y\cup\{x,y\}}$, which preserves all hitting sets of size at most $k$. After exhaustively applying this rule, a counting argument shows either the family has size $O(k^{t-1})$ or the instance is a no-instance. The surviving family is rebuilt as a graph $G'$ by making each surviving set a clique, adding new vertices when a set has fewer than $t$ elements, and Lemma 5 certifies the equivalence.
Load-bearing premise
The correctness of the graph reconstruction in Lemma 5 depends on every set that survives the sunflower reductions being a clique in the original graph $G$, and although this follows from the definitions of the sunflower core, the paper does not state it as an explicit invariant.
Editorial extensions
If this is right
- For constant $t$, the kernel is polynomial in $k$, so the problem is fixed-parameter tractable with a preprocessing bound that improves the previous one by a factor of roughly $k^{(t-1)(t-2)/2}$.
- For $t=3$, triangle-free edge deletion inherits a kernel with $O(k^2)$ vertices and edges, improving the previous $O(k^3)$ bound.
- Because the kernel preserves the parameter $k$, it can be composed with any later FPT algorithm for the problem without increasing the parameter.
- The three-stage template—graph to hitting set, sunflower compression, hitting set back to graph—applies to other edge modification problems whose forbidden structures have bounded clique size.
- A no-instance is detected as soon as the compressed family exceeds $2(t-2)!k^{t-1}$, giving a concrete threshold that can be used to stop the reduction early in implementations.
Reading between the lines
- The $O(k^{t-1})$ bound likely matches the information-theoretic lower bound from the sunflower lemma, so further improvement would need a different compression mechanism rather than tighter sunflower counting.
- The reduction only needs to find sunflowers for edges, so in practice it can be implemented by enumerating independent sets of size $t-2$ in the common neighborhood of an edge—this yields a direct test on small random graphs of whether the kernel size reaches the stated bound.
- Since Rule (R1) is applied iteratively and each application removes at least one set, the running time of the kernelization is polynomial in the original instance size; a more delicate amortized analysis might further tighten the constants.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the K_t-free edge deletion problem, where the goal is to decide whether at most k edges can be removed from a graph so that the remaining graph has no clique of size t. The main contribution is a kernelization algorithm that produces a kernel with O(k^{t-1}) vertices and edges, improving on the previous O(k^{t(t-1)/2}) bound by Cai. The algorithm first translates the problem into a hitting set instance on the family of edge sets of t-cliques. A sunflower-based reduction rule (R1) is applied until each edge lies in few hyperedges, a counting rule (R2) rejects oversized instances, and a third stage reconstructs a graph while preserving equivalence. The correctness rests on three lemmas: R1 preserves the hitting set instance (Lemma 3), R2 is safe (Lemma 4), and the graph reconstruction preserves the original instance (Lemma 5).
Significance. If the proof issues are resolved, this is a significant improvement: the kernel size drops from an exponent quadratic in t to linear in t, and the technique is clean and self-contained, relying only on the standard sunflower lemma. The paper is also a nice example of reducing edge modification to hitting set and then reconstructing a graph, which may be useful for other H-free edge deletion problems. The result is a genuine derivation from stated assumptions, with no circularity or hidden parameters.
major comments (1)
- [Section 2, Lemma 3] The proof of the forward direction is invalid as written. The claim 'Since Xi\Y ≠ Xj\Y for every i ≠ j, there is an index i such that S does not contain an edge with at least one endpoint in Xi\Y' does not follow from disjointness of the petals. An edge of S can have endpoints in two different petals, so k edges can touch up to 2k petals. For example, for t=3 and k=3, take four sunflower sets {a}, {b}, {c}, {d} with empty core Y, and let S = {(x,y), (a,b), (c,d)}. Then S is a hitting set of the four triangles {x,y,a}, {x,y,b}, {x,y,c}, {x,y,d}, yet every petal is touched by some edge of S, so no index i with the stated property exists. The lemma itself is repairable: if S contained no edge from E_{Y∪{x,y}}, then each edge of S could belong to at most one of the sets E_{Xi∪{x,y}}, so k edges could not hit all k+1 sets, a contradiction. This corrected argument should replace the faulty pigeonhole step in the proof.
minor comments (6)
- [Abstract and Introduction] Throughout the text, 'Kt' should be typeset as 'K_t', and the phrase 'removal results a graph' should be 'removal results in a graph'.
- [Introduction] There is a typo in 'Cai an d Cai' (should be 'Cai and Cai').
- [Section 2, Lemma 3] In the second paragraph of the proof, the set is called S, but the text writes 'S′∩ EY ∪{x,y}≠∅'; this should be 'S ∩ E_{Y∪{x,y}} ≠ ∅'. Also, the notation EY ∪{x,y} is ambiguous and should be written as E_{Y∪{x,y}} throughout.
- [Section 2, Lemma 5] In the second direction, the set S' is said to have 'size k', but it should be 'size at most k' since |S| ≤ k and S' is obtained by one replacement.
- [Section 2, third stage] The third stage is described as iterating over 'EX ∈F', but at this point the instance has already been reduced to F'. This appears to be a typo; it should be 'EX ∈F''.
- [Section 2, Lemma 5] The proof would be clearer if it explicitly stated that every set X with E_X in F' is a clique in G: in particular, the set Y∪{x,y} added by Rule (R1) is a clique because it is contained in each Xi∪{x,y}. This justifies the claim that a clique of original vertices in G' is also a clique in G.
Circularity Check
No circularity: the kernel derivation is self-contained and relies solely on the external sunflower lemma.
full rationale
The paper's derivation chain is not circular. The only structural tool is the sunflower lemma (Lemma 1), cited to Erdős and Rado, an external source; the reduction rules R1 and R2 are standard hitting-set arguments built directly on that lemma. No parameter is fitted and later renamed as a prediction, and no load-bearing claim is justified by the author's own prior work. The only prior kernel cited (Cai's thesis, Ref. [2]) is used as a baseline to improve, not to support the validity of the present result. The core lemmas (Observation 2, Lemma 3, Lemma 4, Lemma 5) are argued from definitions and the sunflower lemma rather than from the conclusion being proved. Although the proof of Lemma 3 contains a potential combinatorial gap (the pigeonhole assertion that k edges cannot touch all k+1 petals), a proof gap is not circular reasoning: it does not reduce the conclusion to the hypothesis or to a fitted input. All claimed results are original derivations rather than restatements of the input, so the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (3)
- standard math Erdos-Rado sunflower lemma
- domain assumption The hitting set formulation is equivalent to the deletion set problem
- domain assumption t is a fixed constant, so O(k^{t-1}) is polynomial in k
Cite this review
Pith. "Pith review of Kernel for Kt-free edge deletion." pith.science (2026). https://pith.science/paper/AJTINUJK
@misc{pith2026190803600,
author = {Pith},
title = {Pith review of: Kernel for Kt-free edge deletion},
year = {2026},
howpublished = {\url{https://pith.science/paper/AJTINUJK}},
note = {Machine review of arXiv:1908.03600}
}
abstract
In the $K_t$-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 at most $k$ edges of $G$ whose removal results a graph with no clique of size $t$. In this paper we give a kernel to this problem with $O(k^{t-1})$ vertices and edges.
Reference graph
Works this paper leans on
-
[1]
Incompressibility of H-free edge modification prob- lems
Leizhen Cai and Yufei Cai. Incompressibility of H-free edge modification prob- lems. Algorithmica, 71(3):731–757, 2015
work page 2015
-
[2]
Polynomial kernelisation of H-free edge modification probl ems
Yufei Cai. Polynomial kernelisation of H-free edge modification probl ems. PhD thesis, Chinese University of Hong Kong, 2012
work page 2012
-
[3]
A polynomial k ernel for diamond-free editing
Yixin Cao, Ashutosh Rai, RB Sandeep, and Junjie Ye. A polynomial k ernel for diamond-free editing. In Proc. 26th European Symposium on Algorithms (ESA) , 2018
work page 2018
-
[4]
Intersection theorems for systems of sets
Paul Erd¨ os and Richard Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society , 1(1):85–90, 1960
work page 1960
-
[5]
Graph-based data clustering with overlaps
Michael R Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeie r, and Johannes Uhlmann. Graph-based data clustering with overlaps. Discrete Opti- mization, 8(1):2–17, 2011. 3
work page 2011
-
[6]
Grap h-modeled data clustering: Exact algorithms for clique generation
Jens Gramm, Jiong Guo, Falk H¨ uffner, and Rolf Niedermeier. Grap h-modeled data clustering: Exact algorithms for clique generation. Theory of Computing Systems, 38(4):373–392, 2005
work page 2005
-
[7]
On the (non-) existence of polynomial kernels for Pl-free edge modification problems
Sylvain Guillemot, Fr´ ed´ eric Havet, Christophe Paul, and Anthony Perez. On the (non-) existence of polynomial kernels for Pl-free edge modification problems. Algorithmica, 65(4):900–926, 2013
work page 2013
-
[8]
R. B. Sandeep and Naveen Sivadasan. Parameterized lower boun d and improved kernel for diamond-free edge deletion. In Proc. 10th International Symposium on Parameterized and Exact Computation (IPEC) , 2015. 4
work page 2015
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.