zbMATH — the first resource for mathematics

An efficient fixed-parameter algorithm for 3-hitting set. (English) Zbl 1118.68511
Summary: Given a collection \(C\) of subsets of size three of a finite set \(S\) and a positive integer \(k\), the 3-Hitting Set problem is to determine a subset \(S^{\prime} \subseteq S\) with \(|S^{\prime}| \leqslant k\), so that \(S^{\prime}\) contains at least one element from each subset in \(C\). The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O\((2.270^{k}+n)\) time algorithm for 3-Hitting Set, which is efficient for small values of \(k\), a typical occurrence in some applications. For \(d\)-Hitting Set we present an O\((c^{k}+n)\) time algorithm with \(c=d - 1+\mathrm O(d^{ - 1})\).

68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Alber, J.; Bodlaender, H.L.; Fernau, H.; Kloks, T.; Niedermeier, R., Fixed parameter algorithms for planar dominating set and related problems on planar graphs, Algorithmica, 33, 461-493, (2002) · Zbl 1016.68055
[2] Alber, J.; Fan, H.; Fellows, M.R.; Fernau, H.; Niedermeier, R.; Rosamond, F.; Stege, U., Refined search tree technique for dominating set on planar graphs, (), 111-122 · Zbl 0999.68158
[3] Alber, J.; Gramm, J.; Niedermeier, R., Faster exact solutions for hard problems: A parameterized point of view, Discrete math., 229, 3-27, (2001) · Zbl 0973.68256
[4] Arora, S.; Lund, C., Hardness of approximation, (), 399-446
[5] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and approximation—combinatorial optimization problems and their approximability properties, (1999), Springer-Verlag · Zbl 0937.68002
[6] Ausiello, G.; D’Atri, A.; Protasi, M., Structure preserving reductions among convex optimization problems, J. comput. system sci., 21, 136-153, (1980) · Zbl 0441.68049
[7] Balasubramanian, R.; Fellows, M.R.; Raman, V., An improved fixed parameter algorithm for vertex cover, Inform. process. lett., 65, 163-168, (1998) · Zbl 1337.05095
[8] Bansal, N.; Raman, V., Upper bounds for maxsat: further improved, (), 247-258 · Zbl 0971.68069
[9] Bar-Yehuda, R.; Even, S., A linear-time approximation algorithm for the weighted vertex cover problem, J. algorithms, 2, 198-203, (1981) · Zbl 0459.68033
[10] Beigel, R., Finding maximum independent sets in sparse and general graphs, (), 856-857 · Zbl 0938.68073
[11] D. Bryant, M. Fellows, V. Raman, U. Stege, On the parameterized complexity of MAST and 3-Hitting Sets, 1998, unpublished manuscript
[12] Chen, J.; Kanj, I.; Jia, W., Vertex cover: further observations and further improvements, J. algorithms, 41, 280-301, (2001) · Zbl 1017.68087
[13] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press · Zbl 1158.68538
[14] Crescenzi, P.; Kann, V., A compendium of NP optimization problems, August 1998
[15] Crescenzi, P.; Kann, V., How to find the best approximation results—a follow-up to garey and Johnson, ACM SIGACT news, 29, 90-97, (1998)
[16] Dantsin, E.; Goerdt, A.; Hirsch, E.A.; Kannan, R.; Kleinberg, J.; Papadimitriou, C.; Raghavan, P.; Schöning, U., A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search, Theoret. comput. sci., 289, 1, 69-83, (2002) · Zbl 1061.68071
[17] Fernandez de la Vega, W.; Paschos, V.Th.; Saad, R., Average case analysis of a greedy algorithm for the minimum hitting set problem, (), 130-138
[18] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer-Verlag
[19] Downey, R.G.; Fellows, M.R., Parameterized complexity after (almost) ten years: review and open questions, (), 1-33 · Zbl 0961.68533
[20] Downey, R.G.; Fellows, M.R.; Stege, U., Parameterized complexity: A framework for systematically confronting computational intractability, (), 49-99 · Zbl 0935.68046
[21] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[22] J. Gramm, E.A. Hirsch, R. Niedermeier, P. Rossmanith, New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT, to appear in Discrete Applied Mathematics. Preliminary version available as ECCC Technical Report R00-037, Trier, Fed. Rep. of Germany, May 2000
[23] Greene, D.H.; Knuth, D.E., Mathematics for the analysis of algorithms progress in computer science, (1982), Birkhäuser
[24] M.M. Halldórsson, Approximating k-set cover and complementary graph coloring, in: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, in: Lecture Notes in Computer Science, Vol. 1084, Springer-Verlag, pp. 118-131
[25] Halldórsson, M.M.; Tanaka, K., Approximation and special cases of common subtrees and editing distances, (), 74-84
[26] Håstad, J., Some optimal inapproximability results, J. ACM, 48, 798-859, (2001) · Zbl 1127.68405
[27] Hirsch, E.A., New worst-case upper bounds for SAT, J. automat. reason., 24, 397-420, (2000) · Zbl 0960.03009
[28] ()
[29] Jian, T., An o(2^0.304n) algorithm for solving maximum independent set problem, IEEE trans. comput., 35, 847-851, (1986) · Zbl 0606.68062
[30] Mahajan, M.; Raman, V., Parameterizing above guaranteed values: maxsat and maxcut, J. algorithms, 31, 335-354, (1999) · Zbl 0921.68052
[31] Niedermeier, R., Some prospects for efficient fixed parameter algorithms (invited paper), (), 168-185
[32] Niedermeier, R.; Rossmanith, P., Upper bounds for vertex cover further improved, (), 561-570 · Zbl 0921.05046
[33] Niedermeier, R.; Rossmanith, P., A general method to speed up fixed-parameter-tractable algorithms, Inform. process. lett., 73, 125-129, (2000) · Zbl 1014.68064
[34] Niedermeier, R.; Rossmanith, P., New upper bounds for maximum satisfiability, J. algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[35] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley · Zbl 0833.68049
[36] Robson, J.M., Algorithms for maximum independent sets, J. algorithms, 7, 425-440, (1986) · Zbl 0637.68080
[37] Schöning, U., A probabilistic algorithm for k-SAT and constraint satisfaction problems, (), 410-414
[38] Sedgewick, R.; Flajolet, P., An introduction to the analysis of algorithms, (1996), Addison-Wesley
[39] U. Stege, M. Fellows, An improved fixed-parameter-tractable algorithm for vertex cover, Technical Report 318, Department of Computer Science, ETH Zürich, 1999
[40] Tarjan, R.E.; Trojanowski, A.E., Finding a maximum independent set, SIAM J. comput., 6, 537-550, (1977) · Zbl 0357.68035
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.