zbMATH — the first resource for mathematics

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. (English) Zbl 1087.68067
Summary: We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (FPT) results.) Two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. In particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most \(k\) elements. As an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology.

68R10 Graph theory (including graph drawing) in computer science
92D15 Problems related to evolution
Full Text: DOI
[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, Sixth Workshop on Algorithm Engineering and Experiments ALENEX’04, 2004.
[2] Agarwala, R.; Fernández-Baca, D., A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed, SIAM J. comput., 23, 1216-1224, (1994) · Zbl 0835.68052
[3] Bodlaender, H.; Fellows, M.; Warnow, T., Two strikes against perfect phylogeny, (), 273-283
[4] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, Generating dual-bounded hypergraphs, DIMACS Technical Report 2002-23, 2002. · Zbl 1065.05066
[5] Buss, J.F.; Goldsmith, J., Nondeterminism within P, SIAM J. comput., 22, 560-572, (1993) · Zbl 0773.68031
[6] Chen, J.; Kanj, I.A.; Jia, W., Vertex cover: further observations and further improvements, J. algorithms, 41, 280-301, (2001) · Zbl 1017.68087
[7] M. Chlebík, J. Chlebíková, Crown reductions for the minimum weighted vertex cover problem, ECCC Technical Report TR04-101, 2004.
[8] Damaschke, P., Incremental haplotype inference, phylogeny and almost bipartite graphs, (), 1-11
[9] R.G. Downey, Parameterized complexity for the skeptic, 18th IEEE Conf. on Computational Complexity 2003, 2003, pp. 147-170.
[10] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[11] Downey, R.G.; Fellows, M.R.; Stege, U., Parameterized complexity, a framework for systematically confronting computational intractability, (), 49-99 · Zbl 0935.68046
[12] Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. comput., 24, 1278-1304, (1995) · Zbl 0842.05070
[13] T. Eiter, G. Gottlob, Hypergraph transversal computation and related problems in logic and AI, Eighth European Conf. on Logics in Artificial Intelligence JELIA’2002, Lecture Notes in Computer Science, Vol. 2424, Springer, Berlin, 2002, pp. 549-564. · Zbl 1013.68143
[14] Fernández-Baca, D.; Lagergren, J., A polynomial-time algorithm for near-perfect phylogeny, SIAM J. comput., 32, 1115-1127, (2003) · Zbl 1026.68064
[15] H. Fernau, On parameterized enumeration, COCOON’2002, Lecture Notes in Computer Science, Vol. 2387, Springer, Berlin, 2002, pp. 564-573. · Zbl 1077.68658
[16] Freidman, M.L.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. algorithms, 21, 618-628, (1996) · Zbl 0864.68038
[17] 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
[18] J. Gramm, R. Niedermeier, Quartet inconsistency is fixed-parameter tractable, 12th CPM’2001, Lecture Notes in Computer Science, Vol. 2089, Springer, Berlin, 2001, pp. 241-256. · Zbl 0990.68097
[19] J. Gramm, R. Niedermeier, Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach, First European Conf. on Computational Biology 2002, Bioinformatics 18 (Suppl. 2) (2002) 128-139.
[20] Gusfield, D., Efficient algorithms for inferring evolutionary trees, Networks, 21, 19-28, (1991) · Zbl 0719.92015
[21] E. Halperin, R.M. Karp, Perfect phylogeny and haplotype inference, Eighth RECOMB’2004, 2004, pp. 10-19.
[22] Jansson, J., Consensus algorithms for trees and strings, dissertation 17, (2003), Department of Computer Science, Lund University
[23] Johnson, D.S.; Yannakakis, M.; Papadimitriou, C.H., On generating all maximal independent sets, Inform. process. lett., 27, 119-123, (1988) · Zbl 0654.68086
[24] Kannan, S.; Warnow, T., A fast algorithm for the computation and enumeration of perfect phylogenies, SIAM J. comput., 26, 1749-1763, (1997) · Zbl 0885.68073
[25] D.J. Kavvadias, E.C. Stavropoulos, A new algorithm for the transversal hypergraph problem, WAE’99, Lecture Notes in Computer Science, Vol. 1668, Springer, Berlin, 1999, pp. 72-84.
[26] Kullmann, O., New methods for 3-SAT decision and worst-case analysis, Theor. comput. sci., 223, 1-72, (1999) · Zbl 0930.68066
[27] Nemhauser, G.L.; Trotter, L.E., Vertex packing: structural properties and algorithms, Math. programming, 8, 232-248, (1975) · Zbl 0314.90059
[28] R. Niedermeier, P. Rossmanith, Upper bounds for vertex cover further improved, 16th STACS’99, Lecture Notes in Computer Science, Vol. 1563, Springer, Berlin, 1999, pp. 561-570. · Zbl 0921.05046
[29] Niedermeier, R.; Rossmanith, P., An efficient fixed parameter algorithm for 3-hitting set, J. discrete algorithms, 1, 89-102, (2003) · Zbl 1118.68511
[30] N. Nishimura, P. Ragde, D. Thilikos, Smaller kernels for hitting set problems of constant arity, First International Workshop on Parameterized and Exact Computation IWPEC’2004, Lecture Notes in Computer Science, Vol. 3162, Springer, Berlin, 2004, pp. 121-126. · Zbl 1104.68519
[31] I. Pe’er, R. Shamir, R. Sharan, Incomplete directed perfect phylogeny, 11th CPM’2000, Lecture Notes in Computer Science, Vol. 1848, Springer, Berlin, 2000, pp. 143-153. · Zbl 0964.92040
[32] I. Pe’er, R. Shamir, R. Sharan, On the generality of phylogenies from incomplete directed characters, Eighth SWAT’2002, Lecture Notes in Computer Science, Vol. 2368, Springer, Berlin, 2002, pp. 358-367. · Zbl 1078.92503
[33] Reiter, R., A theory of diagnosis from first principles, Artificial intelligence, 32, 57-95, (1987) · Zbl 0643.68122
[34] Steel, M.A., The complexity of reconstructing trees from qualitative characters and subtrees, J. classification, 9, 91-116, (1992) · Zbl 0766.92002
[35] Wahlström, M., Exact algorithms for finding minimum transversals in rank-3 hypergraphs, J. algorithms, 51, 107-121, (2004) · Zbl 1091.68083
[36] T. Warnow, D. Ringe, A. Taylor, Reconstructing the evolutionary history of natural languages, Seventh SODA’96, 1996, pp. 314-322. · Zbl 0960.68689
[37] Waterman, M.S., Introduction to computational biology, (1995), Chapman & Hall London · Zbl 0831.92011
[38] S. Wernicke, J. Alber, J. Gramm, J. Guo, R. Niedermeier, Avoiding forbidden submatrices by row deletions, 30th SOFSEM’2004, Lecture Notes in Computer Science, Vol. 2932, Springer, Berlin, 2004, pp. 349-360. · Zbl 1202.68212
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.