×

zbMATH — the first resource for mathematics

Towards optimal and expressive kernelization for \(d\)-hitting set. (English) Zbl 1314.68167
Summary: A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as \(d\)-Hitting Set, the problem of covering all hyperedges (whose cardinality is bounded from above by a constant \(d\)) of a hypergraph by at most \(k\) vertices. Additionally, in fault diagnosis, sunflowers yield concise explanations for “highly defective structures”.
We provide a linear-time algorithm that, by finding sunflowers, transforms an instance of \(d\)-Hitting Set into an equivalent instance comprising at most \(O(k^d)\) hyperedges and vertices. In terms of parameterized complexity, we show a problem kernel with asymptotically optimal size (unless \(\operatorname {coNP}\subseteq\operatorname {NP/poly}\)) and provide experimental results that show the practical applicability of our algorithm.
Finally, we show that the number of vertices can be reduced to \(O(k^{d-1})\) with additional processing in \(O(k^{1.5d})\) time – nontrivially combining the sunflower technique with problem kernels due to Abu-Khzam and Moser.

MSC:
68Q25 Analysis of algorithms and problem complexity
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abtreu, R.; Zoeteweij, P.; Gemund, A.J.C., A dynamic modeling approach to software multiple-fault localization, Blue Mountains, NSW, Australia
[2] Abu-Khzam, F.N., A kernelization algorithm for \(d\)-hitting set, J. Comput. Syst. Sci., 76, 524-531, (2010) · Zbl 1197.68083
[3] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (1983) · Zbl 0487.68005
[4] Bevern, R.; Hartung, S.; Kammer, F.; Niedermeier, R.; Weller, M., Linear-time computation of a linear problem kernel for dominating set on planar graphs, No. 7112, 194-206, (2012), Berlin · Zbl 1352.68119
[5] 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
[6] Bodlaender, H.L., Kernelization: new upper and lower bound techniques, No. 5917, 17-37, (2009), Berlin · Zbl 1273.68158
[7] Brankovic, L.; Fernau, H., Parameterized approximation algorithms for hitting set, 63-76, (2012), Berlin · Zbl 1242.68368
[8] Damaschke, P., Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theor. Comput. Sci., 351, 337-350, (2006) · Zbl 1087.68067
[9] Kleer, J.; Williams, B.C., Diagnosing multiple faults, Artif. Intell., 32, 97-130, (1987) · Zbl 0642.94045
[10] Dell, H.; Melkebeek, D., Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, 251-260, (2010), New York · Zbl 1293.68132
[11] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
[12] Erdős, P.; Rado, R., Intersection theorems for systems of sets, J. Lond. Math. Soc., 35, 85-90, (1960) · Zbl 0103.27901
[13] Fernau, H., Edge dominating set: efficient enumeration-based exact algorithms, No. 4169, 142-153, (2006), Berlin · Zbl 1154.68452
[14] Fernau, H., Parameterized algorithms for \(d\)-hitting set: the weighted case, Theor. Comput. Sci., 411, 1698-1713, (2010) · Zbl 1192.68824
[15] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
[16] Fomin, F.V.; Saurabh, S.; Villanger, Y., A polynomial kernel for proper interval vertex deletion, No. 7501, 467-478, (2012), Berlin · Zbl 1366.68092
[17] Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, SIGACT News, 38, 31-45, (2007)
[18] Hagerup, T., Linear-time kernelization for planar dominating set, No. 7112, 181-193, (2011), Berlin · Zbl 1352.68109
[19] Hagerup, T., Kernels for edge dominating set: simpler or smaller, No. 7464, 491-502, (2012), Berlin · Zbl 1365.68281
[20] 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
[21] Khot, S.; Regev, O., Vertex cover might be hard to approximate to within 2−\(ε\), J. Comput. Syst. Sci., 74, 335-349, (2008) · Zbl 1133.68061
[22] Kratsch, S., Polynomial kernelizations for \(\mbox{MIN F}^{+} \text{\varPi}_{1}\) and MAX NP, Algorithmica, 63, 532-550, (2012) · Zbl 1236.68097
[23] Moser, H.: Finding optimal solutions for covering and matching problems. PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena (2010)
[24] Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press, New York (2006) · Zbl 1095.68038
[25] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms, 1, 89-102, (2003) · Zbl 1118.68511
[26] Nishimura, N.; Ragde, P.; Thilikos, D.M., Smaller kernels for hitting set problems of constant arity, No. 3162, 121-126, (2004), Berlin · Zbl 1104.68519
[27] Protti, F.; Silva, M.; Szwarcfiter, J., Applying modular decomposition to parameterized cluster editing problems, Theory Comput. Syst., 44, 91-104, (2009) · Zbl 1179.68111
[28] Reiter, R., A theory of diagnosis from first principles, Artif. Intell., 32, 57-95, (1987) · Zbl 0643.68122
[29] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. A. Springer, Berlin (2003) · Zbl 1041.90001
[30] Shi, L.; Cai, X., An exact fast algorithm for minimum hitting set, 64-67, (2010), Los Alamitos
[31] Sorge, M.; Moser, H.; Niedermeier, R.; Weller, M., Exploiting a hypergraph model for finding golomb rulers, No. 7422, 368-379, (2012), Berlin · Zbl 1360.68519
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.