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? enter image description here

  • $\begingroup$ Related cs.stackexchange.com/questions/131348/… $\endgroup$
    – Juho
    Jul 14, 2021 at 18:43
  • $\begingroup$ @Juho yes but I need O(k) $\endgroup$
    – GO VEGAN
    Jul 14, 2021 at 20:09
  • 1
    $\begingroup$ The 3-petal is more commonly known as a claw. $\endgroup$
    – Juho
    Jul 15, 2021 at 11:23
  • $\begingroup$ I found an article that may be helpful. But it doesn't clear from the article what the size of the kernel they found: k^2logk or klogk. arxiv.org/pdf/1010.1365.pdf @Juho $\endgroup$
    – GO VEGAN
    Jul 23, 2021 at 6:50
  • $\begingroup$ Not sure if it's that helpful. On a quick skim, the paper seems to deal with a more general problem, namely $\mathcal{F}$-minor-free deletion. Your problem requires there to be no claw as a subgraph (i.e., having an induced claw in your problem is fine). You probably just need to focus on the hint given to you. $\endgroup$
    – Juho
    Jul 23, 2021 at 7:29


Your Answer

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

Browse other questions tagged or ask your own question.