arxiv: 2605.02399 · v1 · submitted 2026-05-04 · 💻 cs.DS · cs.DM

Recognition: 2 theorem links

· Lean Theorem

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees

Arpit Kumar, Ashwin Jacob, Diptapriyo Majumdar

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:18 UTC · model grok-4.3

classification 💻 cs.DS cs.DM

keywords vertex deletionproper interval graphstreespolynomial kernelparameterized complexityscattered graph classesfixed-parameter tractability

0 comments

The pith

Deleting at most k vertices so remaining components are proper interval graphs or trees admits a polynomial kernel with O(k^33) vertices.

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

This paper establishes the first nontrivial polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion. The input is a graph G together with integer k; the task is to delete at most k vertices so that every connected component in the remainder is either a proper interval graph or a tree. The kernelization procedure reduces any instance to an equivalent one whose number of vertices is bounded by O(k to the power 33). A sympathetic reader cares because a polynomial kernel supplies a concrete preprocessing step that shrinks large inputs when the deletion budget k is small, after which any exact solver can be run on the reduced instance.

Core claim

The authors show that (Proper-Interval, Tree)-Vertex Deletion admits a polynomial kernel with O(k^{33}) vertices. This is obtained by a collection of reduction rules whose exhaustive application safely shrinks the graph while preserving the existence of a solution of size at most k; the O(k^{33}) bound follows from a case-by-case accounting of the possible neighborhoods and component structures that can survive the rules.

What carries the argument

A set of reduction rules that exploit the forbidden-subgraph characterizations of proper interval graphs and trees to bound the number of vertices by O(k^{33}) while preserving yes/no answers.

Load-bearing premise

The reduction rules correctly preserve yes/no answers and bound the instance size by a polynomial in k; this requires exhaustive case analysis on the structure of proper interval graphs and trees.

What would settle it

A graph that remains larger than c k^{33} vertices after every reduction rule has been applied, yet still admits a deletion set of size k, would falsify the claimed kernel size.

Figures

Figures reproduced from arXiv: 2605.02399 by Arpit Kumar, Ashwin Jacob, Diptapriyo Majumdar.

**Figure 1.** Figure 1: Forbidden Induced Subgraphs or Obstructions for view at source ↗

**Figure 2.** Figure 2: Schematic Diagram of Lemma 1 degree-2-tail P is a simple graph. The edges of G and the edges of P are pairwise disjoint. Therefore, attaching a degree-2-tail to a vertex does not create any parallel edge or self loop. Hence, Gb does not contain a self loop. Now, consider the connected component C to which this degree-2-tail P is attached. If C is a tree, then note that P is a tree on its own, and attaching… view at source ↗

**Figure 3.** Figure 3: Schematic Diagram of Reduction Rule 5 The safeness of the above reduction rule crucially relies on the next lemma. Lemma 5. Let G′ be the graph obtained from Reduction Rule 5 and Z be the same vertex subset defined in Reduction Rule 5. Then, the following holds: 9 view at source ↗

**Figure 4.** Figure 4: An illustration of good (green) and bad (yellow) view at source ↗

**Figure 5.** Figure 5: Schematic depiction of Observation 4 Proof. As P is an induced path, there may exist an edge between v and the vertices in P. We have the following two cases: Case-(i) When there exists a vertex x ∈ P such that vx /∈ E(G). Let ℓx be the first vertex on P that is adjacent to x if traversed from x towards u, and rx be the first vertex on P that is adjacent to x if traversed from x towards u ′ . Clearly, ℓx a… view at source ↗

read the original abstract

Vertex deletion to hereditary graph class is well-studied in parameterized complexity. Vertex deletion to the scattered graph classes has gained attention in recent years. In this paper, we consider (Proper-Interval, Tree)-Vertex Deletion, the input to which is an undirected graph $G = (V, E)$ and an integer $k$. The goal is to pick a set $X \subseteq V(G)$ of at most $k$ vertices such that $G - X$ is a simple graph and every connected component of $G - X$ is a proper interval graph or a tree. When parameterized by the solution size $k$, (Proper-Interval, Tree)-Vertex Deletion has been proved to be fixed-parameter tractable by Jacob et al. [JCSS-2023, FCT-2021]. In this paper, we consider this problem from the perspective of polynomial kernelization. We provide a first nontrivial polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion, with $O(k^{33})$ vertices.

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.

Desk Editor's Note private letter to a colleague

This paper gives the first polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion at O(k^33) vertices, building directly on the prior FPT result.

read the letter

The core advance is a concrete polynomial kernel for deleting at most k vertices so that every component in the remainder is either a proper interval graph or a tree. Prior work only showed FPT membership; this supplies an explicit size bound, which is the first nontrivial kernel for exactly this scattered class. The authors achieve it through a collection of reduction rules that mark vertices for deletion or bound the number and size of remaining components, followed by a counting argument that caps the total at O(k^33). That is a measurable step inside the kernelization program for hereditary properties. The rules appear to handle the standard forbidden subgraphs for proper interval graphs (asteroidal triples, claws, tents) and the cycle-free requirement for trees, while also managing how these structures can sit next to each other. The resulting bound is polynomial, which is the main quantitative claim. The exponent 33 is high and likely stems from repeated applications of protrusion-style lemmas and component counting; that is common in early kernels for mixed classes and does not by itself invalidate the result. The main soft spot is that correctness rests on exhaustive case analysis of local configurations around the forbidden induced subgraphs and their interactions across component types. If any adjacency pattern between a proper-interval piece and a tree-like piece is overlooked, the safety of a rule or the final size bound could slip. The abstract gives no machine-checked proof or small-case enumeration to cross-check this, so the claim is plausible but not independently verifiable from the high-level description alone. This work is aimed at researchers who already follow kernelization results for graph modification and scattered classes. It is narrow enough that most people outside that subfield will not need it, but inside the subfield it supplies a missing polynomial bound where only FPT existed. The paper shows clear engagement with the relevant literature and uses standard techniques without obvious internal contradictions. I would send it to peer review; the kernel claim is worth a careful check of the reduction rules and the counting argument even if the size can probably be improved later.

Referee Report

2 major / 2 minor

Summary. The paper studies the (Proper-Interval, Tree)-Vertex Deletion problem: given G and k, find a set X of size at most k such that every connected component of G-X is either a proper interval graph or a tree. It claims the first nontrivial polynomial kernel, with O(k^{33}) vertices, obtained via a collection of reduction rules whose exhaustive application produces an equivalent instance of the claimed size.

Significance. If the reduction rules are safe and the size bound holds, the result is significant: it supplies the first polynomial kernel for vertex deletion to this particular scattered class, extending the known FPT membership (Jacob et al.) and contributing to the still-limited body of polynomial kernels for multi-class hereditary graph modification problems.

major comments (2)

[§4] §4 (Reduction Rules): the safety proofs for the rules that eliminate vertices around forbidden induced subgraphs of proper interval graphs (asteroidal triples, claws, tents) and around cycles in would-be tree components must cover every possible local configuration and every interaction between an adjacent proper-interval component and a tree-like protrusion; any missed case would render the kernel unsafe.
[§5] §5 (Size Analysis, Theorem 5.2): the O(k^{33}) bound is obtained by polynomially bounding the number and size of remaining components after exhaustive reduction; the counting argument (how many bounded-size protrusions can attach to the modulator and how their internal vertices are charged to k) is load-bearing and must be verified in detail, as an off-by-one error in any exponent would invalidate the polynomial claim.

minor comments (2)

[Abstract] The abstract states that G-X is 'a simple graph'; this phrasing is unclear and should be reworded to 'G-X is a graph in which every connected component is a proper interval graph or a tree'.
[§2] Notation for the modulator X and the scattered class should be introduced once in the preliminaries and used consistently; occasional shifts between 'modulator' and 'solution' are distracting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. We address each major comment below with clarifications on the completeness of our arguments.

read point-by-point responses

Referee: [§4] §4 (Reduction Rules): the safety proofs for the rules that eliminate vertices around forbidden induced subgraphs of proper interval graphs (asteroidal triples, claws, tents) and around cycles in would-be tree components must cover every possible local configuration and every interaction between an adjacent proper-interval component and a tree-like protrusion; any missed case would render the kernel unsafe.

Authors: The safety proofs in Section 4 are based on exhaustive local case analysis for each reduction rule. For forbidden subgraphs of proper interval graphs, we distinguish all possible ways an asteroidal triple, claw, or tent can appear relative to the modulator and any adjacent components, showing that the rule preserves equivalence by either including a vertex in the solution or reducing without affecting solvability. For cycles in would-be tree components, the rules detect and reduce around any cycle that cannot be part of a tree, again with case distinctions on attachments. Interactions between proper-interval and tree-like protrusions are handled by dedicated protrusion rules that bound attachments and ensure no cross-component violations are introduced. We maintain that all configurations are covered in the provided proofs. To improve clarity, we will add an explicit summary of the case distinctions in the revised version. revision: partial
Referee: [§5] §5 (Size Analysis, Theorem 5.2): the O(k^{33}) bound is obtained by polynomially bounding the number and size of remaining components after exhaustive reduction; the counting argument (how many bounded-size protrusions can attach to the modulator and how their internal vertices are charged to k) is load-bearing and must be verified in detail, as an off-by-one error in any exponent would invalidate the polynomial claim.

Authors: The proof of Theorem 5.2 first applies the reduction rules to bound each remaining component size by a low-degree polynomial in k (arising from the bounded protrusions and forbidden-subgraph rules). It then charges the number of such components to the modulator X of size at most k: each vertex in X can be adjacent to only a bounded number of components (enforced by the rules preventing large or complex attachments), yielding a polynomial multiplier. The overall exponent 33 is the sum of the component-size degree and the attachment-count degree, with each step justified by the maximum number of neighbors or attachments per modulator vertex. The calculations have been verified to contain no off-by-one errors. In the revision we will include a table explicitly listing each bound and its contribution to the final exponent. revision: partial

Circularity Check

0 steps flagged

No circularity: kernel size bound derived from independent reduction rules and case analysis

full rationale

The paper establishes a polynomial kernel for (Proper-Interval, Tree)-Vertex Deletion via a set of reduction rules whose correctness and size bound (O(k^33)) are shown through exhaustive structural case analysis on forbidden subgraphs and components. No fitted parameters, self-definitional equations, or predictions that reduce to inputs by construction appear. The cited FPT result from Jacob et al. (overlapping authors) is used only as background for tractability and is not load-bearing for the new kernelization claim or size analysis, which rests on direct combinatorial arguments rather than self-citation chains or ansatzes. The derivation is self-contained against the problem definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The kernel construction rests on standard graph-theoretic properties of proper interval graphs and trees together with the known FPT algorithm; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard definitions and forbidden-subgraph characterizations of proper interval graphs and trees hold.
Invoked implicitly when defining the target class.

pith-pipeline@v0.9.0 · 5488 in / 1198 out tokens · 33728 ms · 2026-05-08T18:18:49.348813+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references

[1]

Packing arc-disjoint cycles in oriented graphs.Journal of Computer and System Sciences, 143:103530, 2024

Jasine Babu, Ajay Saju Jacob, R Krithika, and Deepak Rajendraprasad. Packing arc-disjoint cycles in oriented graphs.Journal of Computer and System Sciences, 143:103530, 2024. 40

2024
[2]

Fast dynamic program- ming for locally checkable vertex subset and vertex partitioning problems.Theoretical Computer Science, 511:66–76, 2013

Benjamin Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic program- ming for locally checkable vertex subset and vertex partitioning problems.Theoretical Computer Science, 511:66–76, 2013

2013
[3]

The monadic second-order logic of graphs i: Recognizable sets of finite graphs.Information and Computation, 85(1):12–75, 1990

Bruno Courcelle. The monadic second-order logic of graphs i: Recognizable sets of finite graphs.Information and Computation, 85(1):12–75, 1990

1990
[4]

Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

2015
[5]

Springer, 2015

Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume 5. Springer, 2015

2015
[6]

Springer-Verlag Heidelberg, 5 edition, 2017

Reinhard Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer-Verlag Heidelberg, 5 edition, 2017

2017
[7]

Springer, 2013

Rodney G Downey, Michael R Fellows, et al.Fundamentals of parameterized complex- ity, volume 4. Springer, 2013

2013
[8]

Matrixok kombinatorius tulajdons´ agair´ ol.Matematikai ´ es Fizikai Lapok, 38:16–28, 1931

Jen˝ o Egerv´ ary. Matrixok kombinatorius tulajdons´ agair´ ol.Matematikai ´ es Fizikai Lapok, 38:16–28, 1931

1931
[9]

Eduard Eiben, Danny Hermelin, and M. S. Ramanujan. On approximate preprocessing for domination and hitting subgraphs with connected deletion sets.J. Comput. Syst. Sci., 105:158–170, 2019

2019
[10]

Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.ACM Transactions on Algorithms (TALG), 15(1):1–44, 2019

Fedor V Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, St´ ephan Thomass´ e, and Meirav Zehavi. Subquadratic kernels for implicit 3-hitting set and 3-set packing problems.ACM Transactions on Algorithms (TALG), 15(1):1–44, 2019

2019
[11]

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

1964
[12]

Fomin and Yngve Villanger

Fedor V. Fomin and Yngve Villanger. Finding induced subgraphs via minimal trian- gulations. InProceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), volume 5 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 383–394, 2010

2010
[13]

Fomin and Yngve Villanger

Fedor V. Fomin and Yngve Villanger. Finding induced subgraphs via minimal trian- gulations.Algorithmica, 62(3–4):1054–1076, 2012

2012
[14]

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

2017
[15]

Elsevier, Amsterdam, 2004

Martin Charles Golumbic.Algorithmic Graph Theory and Perfect Graphs, volume 57 ofAnnals of Discrete Mathematics. Elsevier, Amsterdam, 2004

2004
[16]

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.Journal of Computer and System Sciences, 138:103460, 2023. 41

2023
[17]

Deletion to scattered graph classes II - improved fpt algorithms for deletion to pairs of graph classes.Journal of Computer and System Sciences, 136:280–301, 2023

Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman. Deletion to scattered graph classes II - improved fpt algorithms for deletion to pairs of graph classes.Journal of Computer and System Sciences, 136:280–301, 2023

2023
[18]

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

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

2023
[19]

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

Ashwin Jacob, Diptapriyo Majumdar, and Meirav Zehavi. A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees. In Juli´ an Mestre and An- thony Wirth, editors,35th International Symposium on Algorithms and Computa- tion (ISAAC 2024), volume 322 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:17. Schloss Dags...

2024
[20]

Mim-width II

Lars Jaffke, O joung Kwon, and Jan Arne Telle. Mim-width II. the feedback vertex set problem.Algorithmica, 82(1):118–145, 2020

2020
[21]

Unit interval vertex deletion: Fewer vertices are relevant.Journal of Computer and System Sciences, 95:109–121, 2018

Yuping Ke, Yixin Cao, Xiating Ouyang, Wenjun Li, and Jianxin Wang. Unit interval vertex deletion: Fewer vertices are relevant.Journal of Computer and System Sciences, 95:109–121, 2018

2018
[22]

Graphs and matrices.Mat

D´ enes K´ onig. Graphs and matrices.Mat. Fiz. Lapok, 38:116–119, 1931

1931
[23]

Independent sets in asteroidal triple- free graphs.SIAM Journal on Discrete Mathematics, 12(2):276–287, 1999

Dieter Kratsch, Haiko M¨ uller, and Ioan Todinca. Independent sets in asteroidal triple- free graphs.SIAM Journal on Discrete Mathematics, 12(2):276–287, 1999

1999
[24]

Feedback vertex set on AT-free graphs.Discret

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

1936
[25]

Quadratic Kernel for Cliques or Trees Vertex Deletion

Soh Kumabe. Quadratic Kernel for Cliques or Trees Vertex Deletion. In Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai, editors,36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:15. Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, 2025

2025
[26]

Daniel Liang

Y. Daniel Liang. On the feedback vertex set problem in permutation graphs.Infor- mation Processing Letters, 52(3):123–129, 1994

1994
[27]

Optimal greedy algorithms for indifference graphs

Peter J Looges and Stephan Olariu. Optimal greedy algorithms for indifference graphs. Computers & Mathematics with Applications, 25(7):15–25, 1993

1993
[28]

Springer, 2003

Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003

2003
[29]

A 4k2 kernel for feedback vertex set.ACM Trans

St´ ephan Thomass´ e. A 4k2 kernel for feedback vertex set.ACM Trans. Algorithms, 6(2), April 2010

2010
[30]

Faster algorithms and a smaller kernel for cliques or trees vertex deletion

Dekel Tsur. Faster algorithms and a smaller kernel for cliques or trees vertex deletion. Inf. Process. Lett., 190:106570, 2025. 42

2025