Abstract
Let F be a family of graphs. A canonical vertex deletion problem corresponding to F is defined as follows: given an nvertex undirected graph G and a weight function w: V(G)  >R^+, find a minimum weight subset S subseteq V(G) such that GS belongs to F. This is known as Weighted F Vertex Deletion problem. In this paper we devise a recursive scheme to obtain O(log^{O(1)} n)approximation algorithms for such problems, building upon the classical technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to those problems, where an optimum solution S together with a wellstructured set X, form a balanced separator of the input graph. In this paper, we obtain the first O(log^{O(1)} n)approximation algorithms for the following vertex deletion problems.
 Let {F} be a finite set of graphs containing a planar graph, and F=G(F) be the family of graphs such that every graph H in G(F) excludes all graphs in F as minors. The vertex deletion problem corresponding to F=G(F) is the Weighted Planar FMinorFree Deletion (WPFMFD) problem. We give randomized and deterministic approximation algorithms for WPFMFD with ratios O(log^{1.5} n) and O(log^2 n), respectively. Previously, only a randomized constant factor approximation algorithm for the unweighted version of the problem was known [FOCS 2012].
 We give an O(log^2 n)factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs.
 We give an O(log^3 n)factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD), also known as Weighted Rankwidth1 Vertex Deletion (WR1VD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth one.
We believe that our recursive scheme can be applied to obtain O(log^{O(1)} n)approximation algorithms for many other problems as well.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2018:9405,
author = {Akanksha Agrawal and Daniel Lokshtanov and Pranabendu Misra and Saket Saurabh and Meirav Zehavi},
title = {{Polylogarithmic Approximation Algorithms for WeightedFDeletion Problems}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {1:11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9405},
URN = {urn:nbn:de:0030drops94058},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.1},
annote = {Keywords: Approximation Algorithms, Planar FDeletion, Separator}
}
Keywords: 

Approximation Algorithms, Planar FDeletion, Separator 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 