pith. sign in

arxiv: 2409.14209 · v3 · pith:THDWZVVOnew · submitted 2024-09-21 · 💻 cs.DS · cs.DM

A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees

Ashwin Jacob , Diptapriyo Majumdar , Meirav Zehavi This is my paper

Pith reviewed 2026-05-23 20:31 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords kernelizationparameterized complexitygraph deletionscattered graph classescliquetreepolynomial kernelreduction rules
0
0 comments X

The pith

Deleting at most k vertices so every component is a clique or tree reduces to an equivalent instance on O(k^5) vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a polynomial kernel for the deletion problem in which at most k vertices are removed so that each connected component of the remaining graph is either a clique or a tree. This is presented as the first non-trivial polynomial kernel for any deletion problem to a scattered graph class. The kernel is obtained through a sequence of reduction rules whose correctness is shown by bounding arguments that limit the total number of vertices to O(k^5). A symmetric reader would care because a polynomial kernel converts an FPT problem into one whose running time depends only polynomially on the parameter after a polynomial-time reduction step.

Core claim

The central claim is that the Deletion to Scattered Class of Cliques and Trees problem admits a kernel with O(k^5) vertices. The authors obtain the bound by designing reduction rules that safely delete or contract parts of the input graph while preserving the existence of a solution of size at most k, and then proving that any reduced yes-instance is bounded by that size.

What carries the argument

A collection of reduction rules together with size-bounding arguments that together produce an equivalent instance whose vertex count is O(k^5).

If this is right

  • The problem can be solved by first reducing to O(k^5) vertices in polynomial time and then applying any exponential-in-k algorithm on the reduced instance.
  • Any other deletion-to-scattered-class problem whose yes-instances admit similar structural bounds may also possess a polynomial kernel.
  • The O(k^5) bound improves upon the mere existence of an FPT algorithm by supplying an explicit polynomial dependence on k after the reduction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the same reduction style works for other pairs of dense and sparse classes, then polynomial kernels may exist for additional scattered deletion problems.
  • The O(k^5) size suggests that the problem is unlikely to require a quadratic or cubic kernel unless a stronger structural theorem is proved.
  • Kernelization techniques developed here could be tested on related problems such as deletion to forests or deletion to cliques with isolated vertices.

Load-bearing premise

The reduction rules and size bounds preserve yes/no answers exactly for every value of the deletion parameter k.

What would settle it

An input graph and integer k for which every sequence of the claimed reduction rules yields a graph with more than C k^5 vertices (for the hidden constant C) that is still a yes-instance.

Figures

Figures reproduced from arXiv: 2409.14209 by Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi.

Figure 1
Figure 1. Figure 1: An illustration of applying Reduction Rule 5. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration for obstruction O = {z, u, v, w} where we find an isomorphic obstruction O = {z, u, v′ , w}. Here, v ′ marked in the procedure Mark-Clique-K with respect to OS = O ∩ S and g and the unmarked vertex v. Let R = V (G) \ (S ∪ K). Also, let OS = O ∩ S, OK = O ∩ K and OR = O ∩ R. We have, O = OS ⊎ OK ⊎ OR. Each vertex z ∈ OS is either adjacent to v or not. Let us define a function g : OS → {0, 1} wh… view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of C5. We replace v in C by v ′ to get a new cycle C ′ that has the same number of vertices as C (see [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of Reduction Rule 11. The blue components are the components of [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
read the original abstract

The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered graph classes, where after deletion, each connected component of the graph should belong to at least one of the given graph classes. While fixed-parameter algorithms were given for a wide variety of problems, little progress has been made on the kernelization complexity of any of them. In this paper, we present the first non-trivial polynomial kernel for one such deletion problem, where, after deletion, each connected component should be a clique or a tree - that is, as densest as possible or as sparsest as possible (while being connected). We develop a kernel consisting of O(k^5) vertices for this problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces the first non-trivial polynomial kernel for the deletion-to-scattered-classes problem in which at most k vertices are deleted so that every connected component of the resulting graph is either a clique or a tree. The central claim is an O(k^5)-vertex kernel obtained via a set of reduction rules whose safeness and size analysis are asserted to hold.

Significance. If the kernelization is correct, the result is significant because it supplies the first polynomial kernel for any deletion-to-scattered-graph-classes problem; prior work had only established FPT membership. The explicit O(k^5) bound and the choice of the two extremal classes (cliques and trees) constitute a concrete, falsifiable contribution to the kernelization complexity of this new problem family.

minor comments (3)
  1. [Abstract] The abstract and introduction should explicitly name the problem (e.g., “Deletion to Scattered Cliques and Trees”) and state the parameter k in the problem definition for immediate clarity.
  2. [Introduction] Notation for the two target classes (cliques and trees) and for the scattered-class deletion set should be introduced once and used consistently; occasional shifts between “component belongs to C or T” and “component is a clique or tree” are distracting.
  3. [Kernelization section (presumed §3 or §4)] The size bound O(k^5) is stated without an accompanying table or explicit derivation sketch that isolates the contribution of each reduction rule to the final polynomial degree; adding such a summary would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and the recommendation of minor revision. The report accurately captures the contribution as the first non-trivial polynomial kernel for any deletion-to-scattered-classes problem. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; kernelization is a constructive algorithmic proof

full rationale

The paper presents a kernelization procedure consisting of reduction rules whose safeness (preservation of yes/no answers) is established by direct arguments, followed by a size bound of O(k^5) derived from the application of those rules. No equations, fitted parameters, or predictions appear; the central claim is an explicit construction of rules and a bounding argument rather than a derivation that reduces to its own inputs by definition or self-citation. The result is self-contained within the standard framework of parameterized complexity kernelization and does not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of graphs, connected components, cliques, trees, and the deletion parameter k; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • standard math Standard undirected simple graph definitions and the usual semantics of vertex deletion.
    Invoked implicitly throughout the abstract when defining the problem.

pith-pipeline@v0.9.0 · 5675 in / 1178 out tokens · 19012 ms · 2026-05-23T20:31:35.669724+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Krithika, and Deepak Rajendraprasad

    Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing arc-disjoint 4-cycles in oriented graphs. In Anuj Dawar and Venkatesan Guruswami, editors,42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India, volume 250 ofLIPIcs, pages 5:1–5:16. Schlo...

    work page 2022

  2. [2]

    Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

    Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent feedback vertex set for p5-free graphs. Algorithmica, 81(4):1342–1369, 2019

    work page 2019

  3. [3]

    A fast branching algorithm for cluster vertex deletion.Theory Comput

    Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion.Theory Comput. Syst., 58(2):357–376, 2016

    work page 2016

  4. [4]

    Golovach, Tomás Kaiser, Daniël Paulusma, and Andrzej Proskurowski

    Hajo Broersma, Jirí Fiala, Petr A. Golovach, Tomás Kaiser, Daniël Paulusma, and Andrzej Proskurowski. Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J. Graph Theory, 79(4):282–299, 2015

    work page 2015

  5. [5]

    Fixed-parameter tractability of graph modification problems for hereditary proper- ties

    Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary proper- ties. Inf. Process. Lett., 58(4):171–176, 1996

    work page 1996

  6. [6]

    Interval deletion is fixed-parameter tractable.ACM Trans

    Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable.ACM Trans. Algo- rithms, 11(3):21:1–21:35, 2015

    work page 2015

  7. [7]

    Chordaleditingisfixed-parametertractable

    YixinCaoandDánielMarx. Chordaleditingisfixed-parametertractable. Algorithmica, 75(1):118– 137, 2016

    work page 2016

  8. [8]

    Vertex cover kernelization

    Jianer Chen. Vertex cover kernelization. InEncyclopedia of Algorithms, pages 2327–2330. 2016

    work page 2016

  9. [9]

    Kanj, and Ge Xia

    Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover.Theor. Comput. Sci., 411(40-42):3736–3756, 2010

    work page 2010

  10. [10]

    The strong perfect graph theorem

    Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of mathematics, pages 51–229, 2006

    work page 2006

  11. [11]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms, 3rd Edition. MIT Press, 2009

    work page 2009

  12. [12]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12–75, 1990

    work page 1990

  13. [13]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

    work page 2015

  14. [14]

    A polynomial kernel for bipartite permutation vertex deletion

    Jan Derbisz, Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh, and Shaily Verma. A polynomial kernel for bipartite permutation vertex deletion. Algorithmica, 84(11):3246–3275, 2022. 18

    work page 2022

  15. [15]

    Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics

    Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012

    work page 2012

  16. [16]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows.Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013

    work page 2013

  17. [17]

    An improved kernelization algorithm for trivially perfect editing

    Maël Dumas and Anthony Perez. An improved kernelization algorithm for trivially perfect editing. In Neeldhara Misra and Magnus Wahlström, editors,18th International Symposium on Parame- terized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, volume 285 ofLIPIcs, pages 15:1–15:17. Schloss Dagstuhl - Leibniz-Zentrum für In...

    work page 2023

  18. [18]

    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs.J

    Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot. Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs.J. Discrete Algorithms, 8(1):36– 49, 2010

    work page 2010

  19. [19]

    Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.ACM Trans

    FedorV.Fomin, Tien-NamLe, DanielLokshtanov, SaketSaurabh, StéphanThomassé, andMeirav Zehavi. Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.ACM Trans. Algorithms, 15(1):13:1–13:44, 2019

    work page 2019

  20. [20]

    A polynomial kernel for proper interval vertex deletion.SIAM Journal on Discrete Mathematics, 27(4):1964–1976, 2013

    Fedor V Fomin, Saket Saurabh, and Yngve Villanger. A polynomial kernel for proper interval vertex deletion.SIAM Journal on Discrete Mathematics, 27(4):1964–1976, 2013

    work page 1964

  21. [21]

    Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Discovering archipelagos of tractability for constraint satisfaction and counting.ACM Trans. Algorithms, 13(2):29:1–29:32, 2017

    work page 2017

  22. [22]

    Golovach, Daniël Paulusma, and Erik Jan van Leeuwen

    Petr A. Golovach, Daniël Paulusma, and Erik Jan van Leeuwen. Induced disjoint paths in claw-free graphs. SIAM J. Discret. Math., 29(1):348–375, 2015

    work page 2015

  23. [23]

    Elsevier, 2004

    Martin Charles Golumbic.Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004

    work page 2004

  24. [24]

    Bandwidth of bipartite permutation graphs in polynomial time.J

    Pinar Heggernes, Dieter Kratsch, and Daniel Meister. Bandwidth of bipartite permutation graphs in polynomial time.J. Discrete Algorithms, 7(4):533–544, 2009

    work page 2009

  25. [25]

    Ashwin Jacob, Jari J. H. de Kroon, Diptapriyo Majumdar, and Venkatesh Raman. Deletion to scattered graph classes I - case of finite number of graph classes.J. Comput. Syst. Sci., 138:103460, 2023

    work page 2023

  26. [26]

    Deletion to scattered graph classes II - improved FPT algorithms for deletion to pairs of graph classes

    Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman. Deletion to scattered graph classes II - improved FPT algorithms for deletion to pairs of graph classes. J. Comput. Syst. Sci., 136:280–301, 2023

    work page 2023

  27. [27]

    Expansion lemma - variations and applications to polynomial-time preprocessing.Algorithms, 16(3):144, 2023

    Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman. Expansion lemma - variations and applications to polynomial-time preprocessing.Algorithms, 16(3):144, 2023

    work page 2023

  28. [28]

    Close relatives (of feed- back vertex set), revisited

    Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close relatives (of feed- back vertex set), revisited. In Petr A. Golovach and Meirav Zehavi, editors,16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lis- bon, Portugal, volume 214 ofLIPIcs, pages 21:1–21:15. Schloss Dagstuhl - Leibniz-Z...

    work page 2021

  29. [29]

    Bart M. P. Jansen, Jari J. H. de Kroon, and Michal Wlodarczyk. Single-exponential FPT al- gorithms for enumerating secluded f-free subgraphs and deleting to scattered graph classes. In Satoru Iwata and Naonori Kakimura, editors,34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan, volume 283 of LIPIcs, p...

    work page 2023

  30. [30]

    Connected vertex cover for (sp1+p5)- free graphs

    Matthew Johnson, Giacomo Paesani, and Daniël Paulusma. Connected vertex cover for (sp1+p5)- free graphs. Algorithmica, 82(1):20–40, 2020

    work page 2020

  31. [31]

    Colouring (pr + ps)-free graphs

    Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (pr + ps)-free graphs. Algorithmica, 82(7):1833–1858, 2020. 19

    work page 2020

  32. [32]

    Faster deterministic feedback vertex set.Inf

    Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set.Inf. Process. Lett., 114(10):556–560, 2014

    work page 2014

  33. [33]

    Feedback vertex set on at-free graphs.Discret

    Dieter Kratsch, Haiko Müller, and Ioan Todinca. Feedback vertex set on at-free graphs.Discret. Appl. Math., 156(10):1936–1947, 2008

    work page 1936

  34. [34]

    Representation of a finite graph by a set of intervals on the real line.Fundamenta Mathematicae, 51(1):45–64, 1962

    Cornelis Lekkeikerker and Johan Boland. Representation of a finite graph by a set of intervals on the real line.Fundamenta Mathematicae, 51(1):45–64, 1962

    work page 1962

  35. [35]

    Lewis and Mihalis Yannakakis

    John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219–230, 1980

    work page 1980

  36. [36]

    Disconnected cuts in claw-free graphs

    Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen. Disconnected cuts in claw-free graphs. J. Comput. Syst. Sci., 113:60–75, 2020

    work page 2020

  37. [37]

    On maximal independent sets of vertices in claw-free graphs.Journal of Combi- natorial Theory, Series B, 28(3):284–304, 1980

    George J Minty. On maximal independent sets of vertices in claw-free graphs.Journal of Combi- natorial Theory, Series B, 28(3):284–304, 1980

    work page 1980

  38. [38]

    Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets.ACM Trans. Algorithms, 2(3):403–415, 2006

    work page 2006

  39. [39]

    A 4k2 kernel for feedback vertex set.ACM Trans

    Stéphan Thomassé. A 4k2 kernel for feedback vertex set.ACM Trans. Algorithms, 6(2):32:1–32:8, 2010. 20

    work page 2010