Abstract
In Maximum kVertex Cover (Max kVC), the input is an edgeweighted graph G and an integer k, and the goal is to find a subset S of k vertices that maximizes the total weight of edges covered by S. Here we say that an edge is covered by S iff at least one of its endpoints lies in S.
We present an FPT approximation scheme (FPTAS) that runs in (1/epsilon)^{O(k)} poly(n) time for the problem, which improves upon Gupta, Lee and Li's (k/epsilon)^{O(k)} poly(n)time FPTAS [Anupam Gupta and, 2018; Anupam Gupta et al., 2018]. Our algorithm is simple: just use brute force to find the best kvertex subset among the O(k/epsilon) vertices with maximum weighted degrees.
Our algorithm naturally yields an (efficient) approximate kernelization scheme of O(k/epsilon) vertices; previously, an O(k^5/epsilon^2)vertex approximate kernel is only known for the unweighted version of Max kVC [Daniel Lokshtanov and, 2017]. Interestingly, this also has an application outside of parameterized complexity: using our approximate kernelization as a preprocessing step, we can directly apply Raghavendra and Tan's SDPbased algorithm for 2SAT with cardinality constraint [Prasad Raghavendra and, 2012] to give an 0.92approximation algorithm for Max kVC in polynomial time. This improves upon the best known polynomial time approximation algorithm of Feige and Langberg [Uriel Feige and, 2001] which yields (0.75 + delta)approximation for some (small and unspecified) constant delta > 0.
We also consider the minimization version of the problem (called Min kVC), where the goal is to find a set S of k vertices that minimizes the total weight of edges covered by S. We provide a FPTAS for Min kVC with similar running time of (1/epsilon)^{O(k)} poly(n). Once again, this improves on a (k/epsilon)^{O(k)} poly(n)time FPTAS of Gupta et al. On the other hand, we show, assuming a variant of the Small Set Expansion Hypothesis [Raghavendra and Steurer, 2010] and NP !subseteq coNP/poly, that there is no polynomial size approximate kernelization for Min kVC for any factor less than two.
BibTeX  Entry
@InProceedings{manurangsi:OASIcs:2018:10041,
author = {Pasin Manurangsi},
title = {{A Note on Max kVertex Cover: Faster FPTAS, Smaller Approximate Kernel and Improved Approximation}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {15:115:21},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770996},
ISSN = {21906807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10041},
URN = {urn:nbn:de:0030drops100417},
doi = {10.4230/OASIcs.SOSA.2019.15},
annote = {Keywords: Maximum kVertex Cover, Minimum kVertex Cover, Approximation Algorithms, Fixed Parameter Algorithms, Approximate Kernelization}
}
Keywords: 

Maximum kVertex Cover, Minimum kVertex Cover, Approximation Algorithms, Fixed Parameter Algorithms, Approximate Kernelization 
Collection: 

2nd Symposium on Simplicity in Algorithms (SOSA 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 