Document Open Access Logo

A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem

Author Bingkai Lin

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.81.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Bingkai Lin
  • National Institute of Informatics, Tokyo, Japan
  • Nanjing University, Nanjing, China

Funding

This work was supported in part by the National Key R&D Program of China 2018YFB1003202 and JSPS KAKENHI Grant Number JP18H05291.

Acknowledgements

The author wishes to thank the anonymous referees for their detailed comments.

Cite AsGet BibTex

Bingkai Lin. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.81

Abstract

Given an n-vertex bipartite graph I=(S,U,E), the goal of set cover problem is to find a minimum sized subset of S such that every vertex in U is adjacent to some vertex of this subset. It is NP-hard to approximate set cover to within a (1-o(1))ln n factor [I. Dinur and D. Steurer, 2014]. If we use the size of the optimum solution k as the parameter, then it can be solved in n^{k+o(1)} time [Eisenbrand and Grandoni, 2004]. A natural question is: can we approximate set cover to within an o(ln n) factor in n^{k-epsilon} time? In a recent breakthrough result[Karthik et al., 2018], Karthik, Laekhanukit and Manurangsi showed that assuming the Strong Exponential Time Hypothesis (SETH), for any computable function f, no f(k)* n^{k-epsilon}-time algorithm can approximate set cover to a factor below (log n)^{1/poly(k,e(epsilon))} for some function e. This paper presents a simple gap-producing reduction which, given a set cover instance I=(S,U,E) and two integers k<h <=(1-o(1))sqrt[k]{log |S|/log log |S|}, outputs a new set cover instance I'=(S,U',E') with |U'|=|U|^{h^k}|S|^{O(1)} in |U|^{h^k}* |S|^{O(1)} time such that - if I has a k-sized solution, then so does I'; - if I has no k-sized solution, then every solution of I' must contain at least h vertices. Setting h=(1-o(1))sqrt[k]{log |S|/log log |S|}, we show that assuming SETH, for any computable function f, no f(k)* n^{k-epsilon}-time algorithm can distinguish between a set cover instance with k-sized solution and one whose minimum solution size is at least (1-o(1))* sqrt[k]((log n)/(log log n)). This improves the result in [Karthik et al., 2018].

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • set cover
  • FPT inapproximability
  • gap-producing reduction
  • (n
  • k)-universal set

Metrics

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

Related Versions

References

  1. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In International Colloquium on Automata, Languages, and Programming, pages 1-12. Springer, 2013. Google Scholar
  2. Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In European Symposium on Algorithms, pages 1-12. Springer, 2014. Google Scholar
  3. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 25-36. IEEE, 2017. Google Scholar
  4. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms (TALG), 2(2):153-177, 2006. Google Scholar
  5. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501-555, 1998. Google Scholar
  6. E. Bonnet, B. Escoffier, E. Kim, and V. Th. Paschos. On Subexponential and FPT-Time Inapproximability. In Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, pages 54-65, 2013. Google Scholar
  7. Nicolas Bourgeois, Bruno Escoffier, and Vangelis Paschos. Efficient approximation of MIN SET COVER by "low-complexity" exponential algorithms, 2008. Google Scholar
  8. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-ETH to FPT-inapproximability: Clique, dominating set, and more. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 743-754. IEEE, 2017. Google Scholar
  9. Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 505-514. IEEE, 2016. Google Scholar
  10. V. Chvátal. A greedy heuristic for the set-covering problem. Mathematics of Operations, 4(3):233-235, 1979. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström. Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). Dagstuhl Reports, 7(1):103-128, 2017. Google Scholar
  12. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4(8). Springer, 2015. Google Scholar
  13. Marek Cygan, Łukasz Kowalik, and Mateusz Wykurz. Exponential-time approximation of weighted set cover. Information Processing Letters, 109(16):957-961, 2009. Google Scholar
  14. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. Google Scholar
  15. R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999. Google Scholar
  16. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1-3):57-67, 2004. Google Scholar
  17. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  18. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  19. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62:367-375, 2001. Google Scholar
  20. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  21. D. S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, 9(3):256-278, 1974. Google Scholar
  22. Stasys Jukna. Extremal combinatorics: with applications in computer science. Springer Science &Business Media, 2011. Google Scholar
  23. R. M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York., pages 85-103, 1972. Google Scholar
  24. CS Karthik, Bundit Laekhanukit, and Pasin Manurangsi. On the Parameterized Complexity of Approximating Dominating Set. In STOC, 2018. Google Scholar
  25. Wenxing Lai. The Inapproximability of k-DominatingSet for Parameterized AC⁰ Circuits. In Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings, pages 133-143, 2019. Google Scholar
  26. Bingkai Lin. The Parameterized Complexity of k-Biclique. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 605-615, 2015. Google Scholar
  27. Bingkai Lin. The Parameterized Complexity of the k-Biclique Problem. J. ACM, 65(5):34:1-34:23, 2018. Google Scholar
  28. L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4):383-390, 1975. Google Scholar
  29. C. Lund and M. Yannakakis. On the Hardness of Approximating Minimization Problems. Journal of the ACM, 41(5):960-981, 1994. Google Scholar
  30. D. Marx. Parameterized Complexity and Approximation Algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  31. Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1065-1075. SIAM, 2010. Google Scholar
  32. R. Raz and S. Safra. A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, STOC 1997, El Paso, Texas, USA, May 4-6, 1997, pages 475-484, 1997. Google Scholar
  33. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 721-730. ACM, 2008. Google Scholar
  34. P. Slavík. A Tight Analysis of the Greedy Algorithm for Set Cover. Journal of Algorithms, 25(2):237-254, 1997. Google Scholar
  35. S. K. Stein. Two Combinatorial Covering Theorems. Journal of Combinatorial Theory, Series A, 16(3):391-397, 1974. 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 Imprint Privacy Contact