Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-07
Computer Science
Data Structures and Algorithms
Scientific paper
We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the F-deletion problem when F contains a planar graph. We give (1) a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer. (2) an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F contains graph $\theta_c$ as a minor for a fixed integer $c$. The graph $\theta_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as {\sc Vertex Cover}, {\sc Feedback Vertex Set} and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.
Fomin Fedor V.
Lokshtanov Daniel
Misra Neeldhara
Philip Geevarghese
Saurabh Saket
No associations
LandOfFree
Hitting forbidden minors: Approximation and Kernelization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hitting forbidden minors: Approximation and Kernelization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting forbidden minors: Approximation and Kernelization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-509095