×

zbMATH — the first resource for mathematics

A kernelization algorithm for \(d\)-hitting set. (English) Zbl 1197.68083
Summary: For a given parameterized problem, \(\pi \), a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of \(\pi \) into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kernelization algorithm for the 3-Hitting Set problem is presented along with a general kernelization for \(d\)-Hitting Set. For 3-Hitting Set, an arbitrary instance is reduced into an equivalent one that contains at most \(5k^{2}+k\) elements. This kernelization is an improvement over previously known methods that guarantee cubic-order kernels. Our method is used also to obtain quadratic kernels for several other problems. For a constant \(d \geqslant 3\), a kernelization of \(d\)-Hitting Set is achieved by a non-trivial generalization of the 3-Hitting Set method, and guarantees a kernel whose order does not exceed \((2d - 1)k^{d - 1}+k\).

MSC:
68W05 Nonnumerical algorithms
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F.N. Abu-Khzam, R.L. Collins, M.R. Fellows, M.A. Langston, W.H. Suters, C.T. Symons, Kernelization algorithms for the vertex cover problem: Theory and experiments, in: Workshop on Algorithm Engineering and Experiments (ALENEX), 2004, pp. 62-69
[2] Abu-Khzam, F.N.; Fellows, M.R.; Langston, M.A.; Suters, W.H., Crown structures for vertex cover kernelization, Theory comput. syst., 41, 3, 411-430, (2007) · Zbl 1148.68035
[3] F.N. Abu-Khzam, H. Fernau, Kernels: Annotated, proper and induced, in: International Workshop on Parameterized and Exact Computation (IWPEC), 2006, pp. 264-275 · Zbl 1154.68559
[4] Abu-Khzam, F.N., A quadratic kernel for 3-set packing, (), 81-87 · Zbl 1241.68127
[5] Buss, J.F.; Goldsmith, J., Nondeterminism within \(\mathcal{P}\), SIAM J. comput., 22, 560-572, (1993) · Zbl 0773.68031
[6] B. Chor, M.R. Fellows, D. Juedes, Linear kernels in linear time, or how to save k colors in O(n2) steps, in: International Workshop on Graph Theoretic Concepts in Computer Science (WG), 2004, pp. 257-269 · Zbl 1112.68412
[7] H. Dell, Private communication, 2009
[8] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer · Zbl 0914.68076
[9] H. Fernau, A top-down approach to search-trees: Improved algorithmics for 3-Hitting Set, in: Electronic Colloquium on Computational Complexity (ECCC), 2004, p. 073 · Zbl 1184.68598
[10] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer
[11] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), W.H. Freeman New York · Zbl 0411.68039
[12] Falk Hüffner, Algorithms and experiments for parameterized approaches to hard graph problems, PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2007
[13] Jones, James A.; Harrold, Mary Jean, Test-suite reduction and prioritization for modified condition/decision coverage, IEEE trans. software eng., 29, 3, 195-209, (2003)
[14] Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, Aaron Zollinger, Interference in cellular networks: The minimum membership set cover problem, in: 11th International Computing and Combinatorics Conference (COCOON), Kunming, Yunnan, China, August 2005 · Zbl 1128.90319
[15] Mozer, Hannes, A problem kernelization for graph packing, (), 401-412 · Zbl 1206.68239
[16] Nemhauser, G.L.; Trotter, L.E., Vertex packings: structural properties and algorithms, Math. program., 8, 232-248, (1975) · Zbl 0314.90059
[17] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, J. discrete algorithms, 1, 89-102, (2003) · Zbl 1118.68511
[18] Nishimura, N.; Ragde, P.; Thilikos, D.M., Smaller kernels for hitting set problems of constant arity, (), 121-126 · Zbl 1104.68519
[19] Ruchkys, D.; Song, S., A parallel approximation hitting set algorithm for gene expression analysis, (), 75
[20] D.M. Thilikos, Private communication, 2005
[21] K. Weihe, Covering trains by stations or the power of data reduction, in: R. Battiti, A.A. Bertossi (Eds.), International Conference on Algorithms and Experiments, 1998, pp. 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.