# algorithms – Petal-Deletion problem on O(k)

In Petal-Deletion, we are given an undirected graph G and k ∈ N, and the objective is to decide whether there exists a subset S ⊆ V (G) of size at most k such that G − S does not contain any 3-petal as a subgraph. Design an O(k)-vertex kernel for Petal-Deletion.

I got a hint: You may use a 4-approximation polynomial-time algorithm for 4-Hitting Set as a black box.

What I did so far:

3-petals is a group of 4 as follow: 1 center and 3 leaves (see image for 4-petals for example. I need 3-prtals )

I use the hitting set in this way:

input: F ={p | p is a 3-Petal in the graph}

output: A – minimum hitting set .

if the answer is bigger than 4k – no instance.
else –
B={ x = {x1,x2,…,xm} | x is a maximum connected component in G-A with vertices {x1,x2,…,xm} }.

for each x in B
E’ = { (v,x) v is in A and x is in B | (xi,v) belongs to E when xi is one of the node in the maximum connected component x)

we now define bipartite graph G’= (A B,E)

and repeat:

While |B| >= 3|A|:

apply the expansion lemma on G’ and we will get X A and Y B and then we can get a new safe instance to the problem: (G-X, k- |X|) (it will return true iff the original problem will return true)

(now the while loop is over) ->

|B| = O(k) but I don’t know how to minimize the size of each connected component. each of them need to be fixed size so we can overall get O(k) or maybe there is another way to get O(k)-vertex kernel?