×

zbMATH — the first resource for mathematics

Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space. (English) Zbl 07256105
Summary: The known linear-time kernelizations for \(d\)-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size \(\operatorname{O}(k^d)\) for \(d\)-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for \(d\)-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.
MSC:
68Q Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abu-Khzam, F. N., A kernelization algorithm for d-Hitting Set, J. Comput. Syst. Sci., 76, 524-531 (2010) · Zbl 1197.68083
[2] Alber, J.; Betzler, N.; Niedermeier, R., Experiments on data reduction for optimal domination in networks, Ann. Oper. Res., 146, 105-117 (2006) · Zbl 1106.90011
[3] Bannach, M.; Heinrich, Z.; Reischuk, R.; Tantau, T., Dynamic kernels for Hitting Set and Set Packing (2019), ECCC preprint TR19-146
[4] Bannach, M.; Tantau, T., Computing hitting set kernels by AC_0-circuits, Theory Comput. Syst., 62, 374-399 (2020) · Zbl 1433.68177
[5] van Bevern, R., Fixed-Parameter Linear-Time Algorithms for NP-Hard Graph and Hypergraph Problems Arising in Industrial Applications, Foundations of Computing, vol. 1, 123-150 (2014), Universitätsverlag der TU Berlin: Universitätsverlag der TU Berlin Berlin, Germany, chapter 5
[6] van Bevern, R., Towards optimal and expressive kernelization for d-Hitting Set, Algorithmica, 70, 129-147 (2014) · Zbl 1314.68167
[7] van Bevern, R.; Fluschnik, T.; Tsidulko, O. Yu., On approximate data reduction for the Rural Postman Problem: theory and experiments, Networks (2020), accepted for publication
[8] van Bevern, R.; Moser, H.; Niedermeier, R., Approximation and tidying—a problem kernel for s-Plex Cluster Vertex Deletion, Algorithmica, 62, 930-950 (2012) · Zbl 1236.68100
[9] Bläsius, T.; Fischbeck, P.; Friedrich, T.; Schirneck, M., Understanding the effectiveness of data reduction in public transportation networks, (Avrachenkov, K.; Pralat, P.; Ye, N., WAW 2019. WAW 2019, Lecture Notes in Computer Science, vol. 11631 (2019), Springer), 87-101
[10] Bläsius, T.; Friedrich, T.; Lischeid, J.; Meeks, K.; Schirneck, M., Efficiently enumerating hitting sets of hypergraphs arising in data profiling, (Kobourov, S.; Meyerhenke, H., 2019 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX) (2019), SIAM), 130-143 · Zbl 1430.68178
[11] Brewka, G.; Thimm, M.; Ulbricht, M., Strong inconsistency, Artif. Intell., 267, 78-117 (2019) · Zbl 07099173
[12] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, Massachusetts, USA · Zbl 1047.68161
[13] Damaschke, P., Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theor. Comput. Sci., 351, 337-350 (2006) · Zbl 1087.68067
[14] Dell, H.; van Melkebeek, D., Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, J. ACM, 61, 23 (2014) · Zbl 1321.68274
[15] Fafianie, S.; Kratsch, S., Streaming kernelization, (Csuhaj-Varjú, E.; Dietzfelbinger, M.; Ésik, Z., MFCS 2014. MFCS 2014, Lecture Notes in Computer Science, vol. 8635 (2014), Springer), 275-286 · Zbl 1426.68120
[16] Fafianie, S.; Kratsch, S., A shortcut to (sun)flowers: kernels in logarithmic space or linear time, (Italiano, G. F.; Pighizzini, G.; Sannella, D. T., MFCS 2015. MFCS 2015, Lecture Notes in Computer Science, vol. 9235 (2015), Springer), 299-310 · Zbl 06482817
[17] Fazekas, K.; Bacchus, F.; Biere, A., Implicit hitting set algorithms for maximum satisfiability modulo theories, (Galmiche, D.; Schulz, S.; Sebastiani, R., IJCAR 2018. IJCAR 2018, Lecture Notes in Computer Science, vol. 10900 (2018), Springer), 134-151
[18] Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science, an EATCS Series (2006), Springer
[19] Fomin, F. V.; Lokshtanov, D.; Saurabh, S.; Zehavi, M., Kernelization (2019), Cambridge University Press: Cambridge University Press Cambridge, England · Zbl 1426.68003
[20] Froese, V.; van Bevern, R.; Niedermeier, R.; Sorge, M., Exploiting hidden structure in selecting dimensions that distinguish vectors, J. Comput. Syst. Sci., 82, 521-535 (2016) · Zbl 1333.68143
[21] Hüffner, F.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Fixed-parameter algorithms for cluster vertex deletion, Theory Comput. Syst., 47, 196-217 (2010) · Zbl 1205.68263
[22] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W.; Bohlinger, J. D., Complexity of Computer Computations. Complexity of Computer Computations, The IBM Research Symposia Series (1972), Springer), 85-103
[23] Kratsch, S., Polynomial kernelizations for MIN \(F{}^+\operatorname{\Pi}_1\) and MAX NP, Algorithmica, 63, 532-550 (2012) · Zbl 1236.68097
[24] Mellor, D.; Prieto, E.; Mathieson, L.; Moscato, P., A kernelisation approach for multiple d-hitting set and its application in optimal multi-drug therapeutic combinations, PLoS ONE, 5, Article e0013055 pp. (2010)
[25] Moreno-Centeno, E.; Karp, R. M., The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment, Oper. Res., 61, 453-468 (2013) · Zbl 1267.90125
[26] Moser, H., Finding Optimal Solutions for Covering and Matching Problems (2010), Cuvillier: Cuvillier Göttingen, Germany
[27] Niedermeier, R.; Rossmanith, P., A general method to speed up fixed-parameter-tractable algorithms, Inf. Process. Lett., 73, 125-129 (2000) · Zbl 1014.68064
[28] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-Hitting Set, J. Discret. Algorithms, 1, 89-102 (2003) · Zbl 1118.68511
[29] O’Callahan, R.; Choi, J.-D., Hybrid dynamic data race detection, (Eigenmann, R.; Rinard, M., PPoPP’03 (2003), ACM), 167-178
[30] Rahmann, S.; Wittkop, T.; Baumbach, J.; Martin, M.; Truss, A.; Böcker, S., Exact and heuristic algorithms for weighted cluster editing, (Markstein, P.; Xu, Y., Computational Systems Bioinformatics, vol. 6 (2007), World Scientific Publishing), 391-401
[31] Reiter, R., A theory of diagnosis from first principles, Artif. Intell., 32, 57-95 (1987) · Zbl 0643.68122
[32] Smirnov, P. V., Reduktsiya dannykh dlya zadachi o vershinnom pokrytii gipergrafa za lineinoe vremya s lineinoi pamyat’yu (2018), Novosibirsk State University: Novosibirsk State University Novosibirsk, Russian Federation, Bachelor’s thesis
[33] Sorge, M.; Moser, H.; Niedermeier, R.; Weller, M., Exploiting a hypergraph model for finding Golomb rulers, Acta Inform., 51, 449-471 (2014) · Zbl 1360.68520
[34] Vazquez, A., Optimal drug combinations and minimal hitting sets, BMC Syst. Biol., 3, 81 (2009)
[35] Weihe, K., Covering trains by stations or the power of data reduction, (Battiti, R.; Bertossi, A. A., Proceedings of Algorithms and Experiments. Proceedings of Algorithms and Experiments, ALEX 1998 (1998)), 1-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.