Dynamic Kernels for Hitting Sets and Set Packing

Authors Max Bannach , Zacharias Heinrich , Rüdiger Reischuk, Till Tantau



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.7.pdf
  • Filesize: 0.8 MB
  • 18 pages

Document Identifiers

Author Details

Max Bannach
  • Universität zu Lübeck, Germany
Zacharias Heinrich
  • Universität zu Lübeck, Germany
Rüdiger Reischuk
  • Universität zu Lübeck, Germany
Till Tantau
  • Universität zu Lübeck, Germany

Cite AsGet BibTex

Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.7

Abstract

Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k^d (which is a polynomial kernel size as d is a constant), and they do so in time m⋅ 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k^d hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c^k) where c = d - 1 + O(1/d) equals the best base known for the static setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Fixed parameter tractability
Keywords
  • Kernelization
  • Dynamic Algorithms
  • Hitting Set
  • Set Packings

Metrics

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

References

  1. F. N. Abu-Khzam. A Kernelization Algorithm for d-Hitting Set. Journal of Computer and System Sciences, 76(7):524-531, 2010. URL: https://doi.org/10.1016/j.jcss.2009.09.002.
  2. Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams. Dynamic parameterized problems and algorithms. ACM Trans. Algorithms, 16(4):1-46, July 2020. URL: https://doi.org/10.1145/3395037.
  3. Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic kernels for hitting sets and set packing. Technical Report TR19-146, Computational Complexity Foundation, 2019. URL: https://eccc.weizmann.ac.il/report/2019/146.
  4. Max Bannach, Malte Skambath, and Till Tantau. Kernelizing the hitting set problem in linear sequential and constant parallel time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, pages 9:1-9:16, 2020. URL: https://doi.org/10.4230/LIPIcs.SWAT.2020.9.
  5. Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC⁰-Circuits. Theory Comput. Syst., 64(3):374-399, 2020. URL: https://doi.org/10.1007/s00224-019-09941-z.
  6. S. Bhattacharya, M. Henzinger, and G. F. Italiano. Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 785-804, 2015. URL: https://doi.org/10.1137/1.9781611973730.54.
  7. J. F. Buss and J. Goldsmith. Nondeterminism Within P. SIAM Journal on Computing, 22(3):560-572, 1993. URL: https://doi.org/10.1137/0222038.
  8. Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, and Anna Zych-Pawlewicz. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 796-809. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.50.
  9. Y. Chen, J. Flum, and X. Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, CSL 2017, August 20-24, 2017, Stockholm, Sweden, pages 19:1-19:16, 2017. URL: https://doi.org/10.4230/LIPIcs.CSL.2017.19.
  10. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer Berlin Heidelberg, 2015. Google Scholar
  11. P. Damaschke. Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction. Theoretical Computer Science, 351(3):337-350, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.004.
  12. S. Datta, R. Kulkarni, A. Mukherjee, T. Schwentick, and T. Zeume. Reachability Is in DynFO. Journal of the ACM, 65(5):33:1-33:24, 2018. URL: https://doi.org/10.1145/3212685.
  13. H. Dell and D. van Melkebeek. Satisfiability Allows No Nontrivial Sparsification Unless the Polynomial-Time Hierarchy Collapses. Journal of the ACM, 61(4):23:1-23:27, 2014. URL: https://doi.org/10.1145/2629620.
  14. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  15. Rodney G. Downey, Michael R. Fellows, and Ulrike Stege. Parameterized complexity: A framework for systematically confronting computational intractability. In Ronald L. Graham, Jan Kratochvíl, Jaroslav Nesetril, and Fred S. Roberts, editors, Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, Proceedings of a DIMACS Workshop, Stirín Castle, Czech Republic, May 19-25, 1997, volume 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 49-99. DIMACS/AMS, 1997. URL: https://doi.org/10.1090/dimacs/049/04.
  16. P. Erdős and R.Rado. Intersection Theorems for Systems of Sets. Journal of the London Mathematical Society, 1(1):85-90, 1960. Google Scholar
  17. Stefan Fafianie and Stefan Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, Milan, Italy, August 24-28, 2015, volume 9235 of Lecture Notes in Computer Science, pages 299-310. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48054-0_25.
  18. 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. URL: https://doi.org/10.1016/j.jcss.2017.11.001.
  19. Henning Fernau. A top-down approach to search-trees: Improved algorithmics for 3-hitting set. Algorithmica, 57(1):97-118, 2010. URL: https://doi.org/10.1007/s00453-008-9199-6.
  20. J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  21. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. Iterative compression and exact algorithms. Theor. Comput. Sci., 411(7-9):1045-1053, 2010. URL: https://doi.org/10.1016/j.tcs.2009.11.012.
  22. M. Henzinger and V. King. Maintaining Minimum Spanning Forests in Dynamic Graphs. SIAM Journal on Computing, 31(2):364-374, 2001. URL: https://doi.org/10.1137/S0097539797327209.
  23. J. Holm, K. de Lichtenberg, and M. Thorup. Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. Journal of the ACM, 48(4):723-760, 2001. URL: https://doi.org/10.1145/502090.502095.
  24. Y. Iwata and K. Oka. Fast Dynamic Graph Algorithms for Parameterized Problems. In Proceedings of the 14th Scandinavian Symposium and Workshop on Algorithm Theory, SWAT 2014, Copenhagen, Denmark, July 2-4, 2014, pages 241-252, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_21.
  25. 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, USA, pages 85-103, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  26. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  27. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1984. Google Scholar
  28. R. Niedermeier and P. Rossmanith. An Efficient Fixed-Parameter Algorithm for 3-Hitting Set. Journal of Discrete Algorithms, 1(1):89-102, 2003. URL: https://doi.org/10.1016/S1570-8667(03)00009-1.
  29. S. Patnaik and N. Immerman. DynFO: A Parallel, Dynamic Complexity Class. Journal of Computer and System Sciences, 55(2):199-209, 1997. URL: https://doi.org/10.1006/jcss.1997.1520.
  30. R. van Bevern. Towards Optimal and Expressive Kernelization for d-Hitting Set. Algorithmica, 70(1):129-147, September 2014. URL: https://doi.org/10.1007/s00453-013-9774-3.
  31. René van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications, volume 1 of Foundations of Computing. Universitätsverlag der TU Berlin, 2014. URL: https://doi.org/10.14279/depositonce-4131.
  32. René van Bevern and Pavel V. Smirnov. Optimal-size problem kernels for d-hitting set in linear time and space. Information Processing Letters, 163(105998), 2020. URL: https://doi.org/10.1016/j.ipl.2020.105998.
  33. Magnus Wahlström. Algorithms, measures and upper bounds for satisfiability and related problems. PhD thesis, Linköping University, Sweden, 2007. 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