2026-08-10T07:29:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10041 2024-03-06T10:30:33Z ddc:004 open_access

A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation Manurangsi, Pasin Maximum k-Vertex Cover Minimum k-Vertex Cover Approximation Algorithms Fixed Parameter Algorithms Approximate Kernelization In Maximum k-Vertex Cover (Max k-VC), the input is an edge-weighted 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 (FPT-AS) 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 FPT-AS [Anupam Gupta and, 2018; Anupam Gupta et al., 2018]. Our algorithm is simple: just use brute force to find the best k-vertex 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 k-VC [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 SDP-based algorithm for 2SAT with cardinality constraint [Prasad Raghavendra and, 2012] to give an 0.92-approximation algorithm for Max k-VC 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 k-VC), 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 FPT-AS for Min k-VC with similar running time of (1/epsilon)^{O(k)} poly(n). Once again, this improves on a (k/epsilon)^{O(k)} poly(n)-time FPT-AS 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 k-VC for any factor less than two. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pasin Manurangsi 2019 Is Part Of OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2019.15 urn:nbn:de:0030-drops-100417 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.15 eng https://creativecommons.org/licenses/by/3.0/legalcode