{"id":"6c5cd25a-97d3-418e-ae2c-871918c71b75","arxiv_id":"1908.03600","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A kernel with O(k^{t-1}) vertices and edges for K_t-free edge deletion, improving on the previous O(k^{t(t-1)/2}) bound.","lead":"This paper gives a smaller kernel for the K_t-free edge deletion problem, reducing the number of graph elements from O(k^{t(t-1)/2}) to O(k^{t-1}). The improvement comes from a sunflower-based reduction that compresses the hitting set of all t-cliques.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's pigeonhole step is false: with k+1 sunflower sets and k edges, cross-petal edges can touch every petal, so the claimed untouched petal need not exist; the proof of R1's safety is invalid as written.","rationale":"The reader's weakest assumption was that sets added by R1 are cliques in G; that property is actually true and easily verified. The more serious problem is a false step in the proof of Lemma 3, the lemma that establishes equivalence of the sunflower reduction R1. The proof claims that from disjointness of the petals Xi\\Y one can infer an untouched petal with respect to S. This is false because an edge can span two petals. I constructed a concrete counterexample with t=3, k=3, and a hitting set S of size 3 that touches every petal, disproving the asserted inference. The conclusion of Lemma 3 is nevertheless true and can be proved by a correct pigeonhole argument, so the central result is probably salvageable. However, as written, the proof of the kernel's key reduction is invalid, and the paper should be revised to replace the faulty step. Because the flaw is localized and repairable, a conditional acceptance is appropriate rather than rejection. The secondary ambiguity about whether Fxy is redefined after applications of R1 also affects Lemma 4, but the Lemma 3 gap is the clearest load-bearing issue.","tokens_in":3170,"tokens_out":23172,"duration_ms":228380,"concrete_test":"Check Lemma 3 against the explicit counterexample (t=3, k=3, four triangles {x,y,a}, {x,y,b}, {x,y,c}, {x,y,d}, and S={(x,y),(a,b),(c,d)}). Verify that S is a hitting set, that no petal is untouched by S, and that the proof's asserted index does not exist. Then attempt the repaired argument: if S∩E_{Y∪{x,y}}=∅, each edge of S lies in at most one sunflower set, giving a contradiction with k edges and k+1 sets. If the repair succeeds, the concern is a correctable proof gap; if it fails, Rule R1 may be unsafe and the kernel is unproven.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Lemma 3 (safety of Rule R1), the paper asserts: '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.' This 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; with k+1 petals, an untouched petal is not guaranteed. Concretely, 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)}. 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 in S, so no index i with the stated property exists. Thus the proof of R1's equivalence is invalid as written. The lemma is likely repairable by a different argument: if S contains no edge from E_{Y∪{x,y}}, then every edge of S is contained in at most one of the sets E_{Xi∪{x,y}}, so k edges cannot hit all k+1 sets. However, the argument actually presented is false, and since Lemma 3 underpins the central reduction, this is a load-bearing proof gap.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":3463,"tokens_out":13711,"duration_ms":124710,"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":[{"comment":"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.","section":"Section 2, Lemma 3"}],"minor_comments":[{"comment":"Throughout the text, 'Kt' should be typeset as 'K_t', and the phrase 'removal results a graph' should be 'removal results in a graph'.","section":"Abstract and Introduction"},{"comment":"There is a typo in 'Cai an d Cai' (should be 'Cai and Cai').","section":"Introduction"},{"comment":"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":"Section 2, Lemma 3"},{"comment":"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":"Section 2, Lemma 5"},{"comment":"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":"Section 2, third stage"},{"comment":"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.","section":"Section 2, Lemma 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is close to acceptance: the main result is sound after a local repair of Lemma 3, and the kernel-size improvement is significant. The authors should be asked to correct the proof of Lemma 3 and to fix the minor presentation issues. I would be willing to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I checked the paper and the reader's favorable verdict is mostly right, but they missed something important in Lemma 3. The result itself is a genuine improvement: the O(k^{t-1}) kernel for K_t-free edge deletion beats Cai's O(k^{t(t-1)/2}) bound, and the high-level strategy is sound. The reduction to hitting set, the sunflower-based shrinking of the family, and the reconstruction of the graph are all natural and the size bound follows cleanly from Lemma 4. This is a solid subfield contribution, not a paradigm shift, but it deserves publication.\n\nThe soft spot is the proof of Lemma 3. The paper claims that because the sunflower petals are disjoint, the k+1 petals must include one untouched by the at-most-k edges of S. That's false: an edge can have endpoints in two different petals, so k edges can touch up to 2k petals. Concrete counterexample for t=3 and k=3: take petals {a}, {b}, {c}, {d} with empty core, and S = {(x,y), (a,b), (c,d)}. This set hits all four triangles {x,y,a}, {x,y,b}, {x,y,c}, {x,y,d}, yet every petal is touched. So the stated pigeonhole argument is invalid.\n\nThat said, the lemma itself is salvageable and probably true. If S contains no edge from E_{Y∪{x,y}}, then each edge of S lies in at most one of the sets E_{X_i∪{x,y}} (an edge with endpoints in two different petals lies in none of them), so k edges cannot hit all k+1 sets. The paper just doesn't present this argument. Since Lemma 3 is load-bearing for the reduction, the proof needs to be rewritten before the paper is acceptable.\n\nThe rest checks out. Lemma 4's packing argument is correct, and Lemma 5's graph reconstruction works; the reader's worry about added sets being cliques is resolved by the definition of the original family. No citation problems, no self-citation issues, fully self-contained except for the standard sunflower lemma.\n\nBottom line: the result is real and worth publishing after a minor-to-moderate revision. I would send it to peer review, with the request that the proof of Lemma 3 be corrected. This is exactly the kind of paper a serious referee should see.","headline":"The kernel-size improvement is real, but the proof of Lemma 3 as written has a load-bearing gap that needs a fix.","tokens_in":3950,"tokens_out":5550,"would_cite":true,"duration_ms":48326,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"K_t-free edge deletion has a kernel with $O(k^{t-1})$ vertices and edges.","keywords":["kernelization","K_t-free edge deletion","sunflower lemma","hitting set","parameterized complexity","fixed-parameter tractable","edge deletion"],"falsifier":"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.","tokens_in":2990,"feed_emoji":"🌻","tokens_out":7175,"duration_ms":64309,"temperature":0.7,"pith_summary":"The paper proves that $K_t$-free edge deletion—the problem of deleting at most $k$ edges to destroy every clique of size $t$—admits a kernel with $O(k^{t-1})$ vertices and edges, improving the previous $O(k^{t(t-1)/2})$ kernel. The proof works by translating the graph instance into a hitting set instance whose elements are the edge sets of all $t$-cliques, then using the sunflower lemma to repeatedly shrink this family. The reduced family is then re-encoded as a graph, yielding the kernel. A sympathetic reader should care because the exponent drops from quadratic in $t$ to linear in $t$, and the sunflower-based compression is a transferable technique for edge-deletion problems.","feed_headline":"Kernel for clique-free edge deletion is O(k^{t-1})","feed_subtitle":"One sunflower reduction per edge shrinks any instance before the graph is rebuilt; previous bound was O(k^{t(t-1)/2}).","key_machinery":"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})$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the sunflower lemma that guarantees the $k+1$-petal sunflower in $\\mathcal{F}_{xy}$ used by Rule (R1).","marker":"[4]"},{"why":"Provides the previous kernel for $K_t$-free edge deletion with $O(k^{t(t-1)/2})$ vertices and edges, the baseline this paper improves.","marker":"[2]"}],"fun_headline_variants":["Edge deletion kernel falls to O(k^{t-1})","Clique-free edge deletion kernel shrinks","K_t-free deletion gets tighter kernel bound","Improved kernel: O(k^{t-1}) for K_t-free"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Edge deletion kernel falls to O(k^{t-1})","Clique-free edge deletion kernel shrinks","K_t-free deletion gets tighter kernel bound","Improved kernel: O(k^{t-1}) for K_t-free"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000127,"raw_usage":{"total_tokens":1072,"prompt_tokens":863,"completion_tokens":209,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":144}},"tokens_in":479,"tokens_out":209,"duration_ms":2595,"temperature":1.0,"reasoning_tokens":144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:09:08.509458+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Intersection theorems for systems of sets","cited_arxiv_id":null,"evidence_quote":"Supplies the sunflower lemma that guarantees the $k+1$-petal sunflower in $\\mathcal{F}_{xy}$ used by Rule (R1)."},{"cited_title":"Polynomial kernelisation of H-free edge modification probl ems","cited_arxiv_id":null,"evidence_quote":"Provides the previous kernel for $K_t$-free edge deletion with $O(k^{t(t-1)/2})$ vertices and edges, the baseline this paper improves."}],"review_version":1}