Planar F-Deletion: Approximation and Optimal FPT Algorithms

Details Planar F-Deletion: Approximation and Optimal FPT Algorithms Planar F-Deletion: Approximation and Optimal FPT Algorithms

2012-04-19

arxiv.org/abs/1204.4230v1

Computer Science

Data Structures and Algorithms

Scientific paper

Let F be a finite set of graphs. In the F-Deletion problem, we are given an n-vertex, m-edge graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-Deletion is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as Vertex Cover, Feedback Vertex Set or Treewidth t-Deletion. In this paper we obtain a number of generic algorithmic results about Planar F-Deletion, when F contains at least one planar graph. The highlights of our work are - A randomized O(nm) time constant factor approximation algorithm for the optimization version of Planar F-Deletion. - A randomized O(2^{O(k)} n) time parameterized algorithm for Planar F-Deletion when F is connected. Here a family F is called connected if every graph in F is connected. The algorithm can be made deterministic at the cost of making the polynomial factor in the running time n\log^2 n rather than linear. These algorithms unify, generalize, and improve over a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results -- constant factor approximation and FPT algorithms -- are stringed together by a common theme of polynomial time preprocessing.

Affiliated with

Also associated with

No associations

Rating

Planar F-Deletion: Approximation and Optimal FPT Algorithms 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 Planar F-Deletion: Approximation and Optimal FPT Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planar F-Deletion: Approximation and Optimal FPT Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-33776