Document Open Access Logo

A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation

Author Pasin Manurangsi

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.15.pdf
  • Filesize: 0.61 MB
  • 21 pages

Document Identifiers

Author Details

Pasin Manurangsi

Cite As Get BibTex

Pasin Manurangsi. A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.15

Abstract

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.

Subject Classification

Keywords
  • Maximum k-Vertex Cover
  • Minimum k-Vertex Cover
  • Approximation Algorithms
  • Fixed Parameter Algorithms
  • Approximate Kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, and Christopher T. Symons. Kernelization algorithms for the vertex cover problem: Theory and experiments. In ALENEX, pages 62-69, 2004. Google Scholar
  2. Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307-328, 2004. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  4. Nicola Apollonio and Bruno Simeone. The maximum vertex coverage problem on bipartite graphs. Discrete Applied Mathematics, 165:37-48, 2014. Google Scholar
  5. Per Austrin. Balanced Max 2-Sat might not be the hardest. In STOC, pages 189-197, 2007. Google Scholar
  6. Per Austrin, Siavosh Benabbas, and Konstantinos Georgiou. Better balance by being biased: A 0.8776-approximation for max bisection. In SODA, pages 277-294, 2013. Google Scholar
  7. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(1):27-43, 2011. Google Scholar
  8. Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In FOCS, pages 453-462, 2009. Google Scholar
  9. R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithms for Combinatorial Problems, volume 109 of North-Holland Mathematics Studies, pages 27 - 45. North-Holland, 1985. Google Scholar
  10. Reuven Bar-Yehuda. Using homogeneous weights for approximating the partial cover problem. J. Algorithms, 39(2):137-144, 2001. Google Scholar
  11. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, pcps, and nonapproximability-towards tight results. SIAM J. Comput., 27(3):804-915, 1998. Google Scholar
  12. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  13. Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, and Georgios Stamoulis. Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discrete Optimization, 27:26-56, 2018. Google Scholar
  14. Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM J. Comput., 22(3):560-572, 1993. Google Scholar
  15. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of parameterized tractability. Ann. Pure Appl. Logic, 84(1):119-138, 1997. Google Scholar
  16. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280-301, 2001. Google Scholar
  17. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  18. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Google Scholar
  19. Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. Google Scholar
  20. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? ECCC, 23:198, 2016. Google Scholar
  21. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. ECCC, 24:94, 2017. Google Scholar
  22. Irit Dinur and Shmuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439-485, 2005. Google Scholar
  23. Uriel Feige and Michael Langberg. Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms, 41(2):174-211, 2001. Google Scholar
  24. Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. Parameterized approximation via fidelity preserving transformations. J. Comput. Syst. Sci., 93:30-40, 2018. Google Scholar
  25. Rajiv Gandhi and Guy Kortsarz. On set expansion problems and the small set expansion conjecture. Discrete Applied Mathematics, 194:93-101, 2015. Google Scholar
  26. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  27. Oded Goldreich. On promise problems: A survey. In Theoretical Computer Science, Essays in Memory of Shimon Even, pages 254-290, 2006. Google Scholar
  28. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory Comput. Syst., 41(3):501-520, 2007. Google Scholar
  29. Anupam Gupta, Euiwoong Lee, and Jason Li. Faster exact and approximate algorithms for k-cut. In FOCS, 2018. To appear. Google Scholar
  30. Anupam Gupta, Euiwoong Lee, and Jason Li. An FPT algorithm beating 2-approximation for k-cut. In SODA, pages 2821-2837, 2018. Google Scholar
  31. Eran Halperin and Uri Zwick. A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Struct. Algorithms, 20(3):382-402, 2002. Google Scholar
  32. Qiaoming Han, Yinyu Ye, Hantao Zhang, and Jiawei Zhang. On approximation of max-vertex-cover. European Journal of Operational Research, 143(2):342-355, 2002. Google Scholar
  33. Qiaoming Han, Yinyu Ye, and Jiawei Zhang. An improved rounding method and semidefinite programming relaxation for graph partition. Math. Program., 92(3):509-535, 2002. Google Scholar
  34. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  35. Dorit S. Hochbaum. Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Boston, MA, USA, 1997. Google Scholar
  36. George Karakostas. A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms, 5(4):41:1-41:8, 2009. Google Scholar
  37. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  38. Subhash Khot. On the power of unique 2-prover 1-round games. In CCC, page 25, 2002. Google Scholar
  39. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In STOC, pages 576-589, 2017. Google Scholar
  40. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. ECCC, 25:6, 2018. Google Scholar
  41. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  42. Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the MAX 2-sat and MAX DI-CUT problems. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings, pages 67-82, 2002. Google Scholar
  43. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In STOC, pages 224-237, 2017. Google Scholar
  44. Pasin Manurangsi. A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation. arXiv preprint arXiv:1810.03792, 2018. Google Scholar
  45. Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. In ICALP, pages 78:1-78:15, 2017. Google Scholar
  46. Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60-78, 2008. Google Scholar
  47. Burkhard Monien and Ewald Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf., 22(1):115-123, 1985. Google Scholar
  48. George L. Nemhauser and Leslie E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48-61, 1974. Google Scholar
  49. Erez Petrank. The hardness of approximation: Gap location. Computational Complexity, 4:133-157, 1994. Google Scholar
  50. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC, pages 755-764, 2010. Google Scholar
  51. Prasad Raghavendra, David Steurer, and Madhur Tulsiani. Reductions between expansion problems. In CCC, pages 64-73, 2012. Google Scholar
  52. Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In SODA, pages 373-387, 2012. Google Scholar
  53. Henrik Sjögren. Rigorous analysis of approximation algorithms for MAX 2-CSP. Master’s thesis, KTH Royal Institute of Technology, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact