Document Open Access Logo

Lossy Kernelization for (Implicit) Hitting Set Problems

Authors Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.49.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Tien-Nam Le
  • École Normale Supérieure de Lyon, France
Daniel Lokshtanov
  • University of California Santa Barbara, CA, USA
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway
Stéphan Thomassé
  • École Normale Supérieure de Lyon, France
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

  • Fomin, Fedor V.: Research Council of Norway via the project BWCA (grant no. 314528).
  • Lokshtanov, Daniel: Supported by NSF award CCF-2008838.
  • Saurabh, Saket: European Research Council (ERC) grant agreement no. 819416, and Swarnajayanti Fellowship no. DST/SJF/MSA01/2017-18.
  • Thomassé, Stéphan: ANR projects TWIN-WIDTH (CE48-0014-01) and DIGRAPHS (CE48-0013-01).
  • Zehavi, Meirav: European Research Council (ERC) grant titled PARAPATH.

Cite AsGet BibTex

Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.49

Abstract

We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Hitting Set
  • Lossy Kernelization

Metrics

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

Related Versions

References

  1. Faisal N. Abu-Khzam. A kernelization algorithm for d-Hitting Set. J. Comput. Syst. Sci., 76(7):524-531, 2010. URL: https://doi.org/10.1016/j.jcss.2009.09.002.
  2. Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci., 77(6):1071-1078, 2011. Google Scholar
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. Google Scholar
  4. Hans L. Bodlaender, Fedor V. Fomin, and Saket Saurabh. Open problems, worker 2010. Available at http://fpt.wikidot.com/open-problems, 2010. Google Scholar
  5. Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993-2007, 2000. Google Scholar
  6. Jianer Chen, Iyad A Kanj, and Weijia Jia. Vertex cover: further observations and further improvements. Journal of Algorithms, 41(2):280-301, 2001. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Bart MP Jansen, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Open problems for fpt school 2014. URL: http://fptschool. mimuw. edu. pl/opl. pdf, 2014. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 68-81, 2012. Google Scholar
  10. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM, 61(4):23:1-23:27, 2014. Google Scholar
  11. Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010. Google Scholar
  12. Andrew Drucker. New limits to classical and quantum instance compression. SIAM Journal on Computing, 44(5):1443-1479, 2015. Google Scholar
  13. Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, and Sue Whitesides. Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica, 52(2):167-176, 2008. Google Scholar
  14. Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt. Improved approximation algorithms for hitting 3-vertex paths. In Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, volume 9682 of Lecture Notes in Computer Science, pages 238-249, 2016. Google Scholar
  15. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  16. Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Subquadratic kernels for implicit 3-Hitting Set and 3-Set Packing problems. ACM Trans. Algorithms, 15(1):13:1-13:44, 2019. URL: https://doi.org/10.1145/3293466.
  17. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Theory of parameterized preprocessing. Cambridge University Press, Cambridge, 2019. Google Scholar
  18. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91-106, 2011. Google Scholar
  19. Jacob Fox, Hao Huang, and Benny Sudakov. On graphs decomposable into induced matchings of linear sizes. Bulletin of the London Mathematical Society, 49(1):45-57, 2017. Google Scholar
  20. Zoltán Füredi. Matchings and covers in hypergraphs. Graphs and Combinatorics, 4(1):115-206, 1988. Google Scholar
  21. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 104-113, 2012. Google Scholar
  22. 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. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  23. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450-459, 2012. URL: https://doi.org/10.1109/FOCS.2012.46.
  24. Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2-approximating feedback vertex set in tournaments. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1010-1018, 2020. Google Scholar
  25. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237, 2017. Google Scholar
  26. Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-approximation for feedback vertex sets in tournaments. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 67:1-67:14, 2016. Google Scholar
  27. George L Nemhauser and Leslie Earl Trotter. Properties of vertex packing and independence system polyhedra. Mathematical programming, 6(1):48-61, 1974. Google Scholar
  28. Imre Z Ruzsa and Endre Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939-945, 1978. Google Scholar
  29. Jie You, Jianxin Wang, and Yixin Cao. Approximate association via dissociation. Discrete Applied Mathematics, 219:202-209, 2017. 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