# Kernelization algorithm for the following problem

We are given an undirected graph $$G$$ and a positive parameter $$k \geq 0$$. The problem is to decide if there exists a set $$S \subseteq V(G)$$ of size at most $$k$$ such that $$G − S$$ does not have any path on three vertices.

Is there any deterministic kernel algorithm for this problem with $$\Theta (k^2)$$ vertices?

Kernelization algorithm definition: Given $$(G,k)$$, output an equivalent instance $$(G’,k’)$$ of the same problem in polynomial time, such that $$|G’| \leq f(k)$$ and $$k’ \leq k$$.

• Does "$G-S$ does not have any path on three vertices" mean that each connected component of $G-S$ is of size at most $2$? Apr 11, 2021 at 17:10
• Probably, although it's not completely obvious. If it's as you say, then the problem is the same as the 1-BDD problem posted about the other day (bounded degree deletion). Apr 12, 2021 at 7:33
• Do you mean induced paths of length three, or any paths at all on three vertices, i.e., that every connected component has size at most two? Jan 10, 2022 at 19:36

Your problem can be stated as $$3$$-path vertex cover problem. A simple google search gives this paper. The authors design a kernel of size $$5k$$ for this problem.
• I think there was misunderstanding, I mean to $\Theta (k^2)$ vertices. Apr 12, 2021 at 16:53
• @John19 A kernel of $5k$ vertices is also a kernel of $O(k^2)$ vertices. So what is the issue here? Apr 12, 2021 at 17:17
• @John19 If you want to make it $\Omega(k^2)$, you can always stop the algorithm when $\Theta(k^2)$ vertices are reached Apr 12, 2021 at 17:18