0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\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, 2021 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, 2021 at 7:33
  • 1
    $\begingroup$ 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? $\endgroup$
    – Pål GD
    Jan 10, 2022 at 19:36

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think there was misunderstanding, I mean to $ \Theta (k^2) $ vertices. $\endgroup$
    – John19
    Apr 12, 2021 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, 2021 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, 2021 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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