×

zbMATH — the first resource for mathematics

A top-down approach to search-trees: Improved algorithmics for 3-hitting set. (English) Zbl 1184.68598
Summary: We show how to systematically improve on parameterized algorithms and their analysis, focusing on search-tree based algorithms for 3-Hitting Set. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been designed previously to improve on the exponential base in the algorithms.
However, this necessitates a more complex algorithm analysis based on a so-called auxiliary parameter, a technique which we believe can be used in other circumstances, as well.

MSC:
68W05 Nonnumerical algorithms
68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abu-Khzam, F., Fernau, H.: Kernels: annotated, proper and induced. In: International Workshop on Parameterized and Exact Computation IWPEC. LNCS, vol. 4169, pp. 264–275. Springer, Berlin (2006) · Zbl 1154.68559
[2] Abu-Khzam, F.N.: Kernelization algorithms for d-hitting set problems. In: Workshop on Algorithms and Data Structures WADS. LNCS, vol. 4619, pp. 434–445. Springer, Berlin (2007) · Zbl 1209.68610
[3] Alber, J., Gramm, J., Niedermeier, R.: Faster exact algorithms for hard problems: a parameterized point of view. Discrete Math. 229(1), 3–27 (2001) · Zbl 0973.68256 · doi:10.1016/S0012-365X(00)00199-0
[4] Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined search tree techniques for dominating set on planar graphs. J. Comput. Syst. Sci. 71, 385–405 (2005) · Zbl 1101.68712 · doi:10.1016/j.jcss.2004.03.007
[5] Anand, R.S., Erlebach, T., Hall, A., Stefanakos, S.: Call control with k rejections. J. Comput. Syst. Sci. 67, 707–722 (2003) · Zbl 1076.68016 · doi:10.1016/S0022-0000(03)00076-X
[6] Berry, V., Nicolas, F.: Maximum agreement and compatible supertrees. In: Combinatorial Pattern Matching Symposium (CPM). LNCS, vol. 3109, pp. 205–219. Springer, Berlin (2004) · Zbl 1103.68966
[7] Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280–301 (2001) · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186
[8] Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43, 245–273 (2005) · Zbl 1086.68099 · doi:10.1007/s00453-004-1145-7
[9] Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Mathematical Foundations of Computer Science MFCS. LNCS, vol. 4162, pp. 238–249. Springer, Berlin (2006) · Zbl 1132.68421
[10] Damaschke, P.: The union of minimal hitting sets: parameterized combinatorial bounds and counting. In: 24th Symposium on Theoretical Aspects of Computer Science STACS. LNCS, vol. 4393, pp. 332–343. Springer, Berlin (2007) · Zbl 1186.05087
[11] Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 595–601 (2003) · Zbl 1192.68290
[12] Dom, M., Guo, J., Hüffner, F., Niedermeier, R., Truß, A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Conference on Algorithms and Complexity CIAC. LNCS, vol. 3998, pp. 320–331. Springer, Berlin (2006) · Zbl 1183.68419
[13] Downey, R.G., Fellows, M.R., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pp. 49–99. AMS, Providence (1999) · Zbl 0935.68046
[14] Dujmović, V., Fellows, M.R., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to two-layer planarization. In: 9th International Symposium on Graph Drawing GD. LNCS, vol. 2265, pp. 1–15. Springer, Berlin (2002) · Zbl 1054.68576
[15] Fernau, H.: A top-down approach to search-trees: Improved algorithmics for 3-Hitting Set. Technical Report TR04-073, Electronic Colloquium on Computational Complexity ECCC (2004) · Zbl 1184.68598
[16] Fernau, H.: Two-layer planarization: improving on parameterized algorithmics. J. Graph Algorithms Appl. 9, 205–238 (2005) · Zbl 1108.68062
[17] Fernau, H.: Parameterized algorithms for hitting set: the weighted case. In: Conference on Algorithms and Complexity CIAC. LNCS, vol. 3998, pp. 332–343. Springer, Berlin (2006) · Zbl 1183.68426
[18] Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination–a case study. In: Automata, Languages and Programming, 32nd International Colloquium, ICALP. LNCS, vol. 3580, pp. 191–203. Springer, Berlin (2005) · Zbl 1082.68866
[19] Garfinkel, R.S., Nemhauser, G.L.: Integer Programming. Wiley, New York (1972)
[20] Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39, 321–347 (2004) · Zbl 1090.68027 · doi:10.1007/s00453-004-1090-5
[21] Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223, 1–72 (1999) · Zbl 0930.68066 · doi:10.1016/S0304-3975(98)00017-6
[22] Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-Hitting Set. J. Discrete Algorithms 1, 89–102 (2003) · Zbl 1118.68511 · doi:10.1016/S1570-8667(03)00009-1
[23] Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32, 57–95 (1987) · Zbl 0643.68122 · doi:10.1016/0004-3702(87)90062-2
[24] Suderman, M.: Layered graph drawing. Ph.D. thesis, McGill University, Montréal (2005)
[25] Wahlström, M.: Exact algorithms for finding minimum transversals in rank-3 hypergraphs. J. Algorithms 51, 107–121 (2004) · Zbl 1091.68083 · doi:10.1016/j.jalgor.2004.01.001
[26] Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Department of Computer and Information Science, Linköpings universitet, Sweden (2007). Available through http://www.diva-portal.org/diva/getDocument?urn_nbn_se_liu_diva-8714-1_fulltext.pdf
[27] Weihe, K.: Covering trains by stations or the power of data reduction. In: Algorithms and Experiments ALEX 98, pp. 1–8 (1998). http://rtm.science.unitn.it/alex98/proceedings.html
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.