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 $.

  • $\begingroup$ 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$? $\endgroup$ – Nathaniel Apr 11 at 17:10
  • $\begingroup$ 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). $\endgroup$ – Pål GD Apr 12 at 7:33

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.

  • $\begingroup$ I think there was misunderstanding, I mean to $ \Theta (k^2) $ vertices. $\endgroup$ – John19 Apr 12 at 16:53
  • $\begingroup$ @John19 A kernel of $5k$ vertices is also a kernel of $O(k^2)$ vertices. So what is the issue here? $\endgroup$ – Inuyasha Yagami Apr 12 at 17:17
  • $\begingroup$ @John19 If you want to make it $\Omega(k^2)$, you can always stop the algorithm when $\Theta(k^2)$ vertices are reached $\endgroup$ – Inuyasha Yagami Apr 12 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.