Abstract
The problem of finding the longest common subsequence (LCS) of two given strings A 1 and A 2 is a well-studied problem. The constrained longest common subsequence (C-LCS) for three strings A 1, A 2 and B 1 is the longest common subsequence of A 1 and A 2 that contains B 1 as a subsequence. The fastest algorithm solving the C-LCS problem has a time complexity of O(m 1 m 2 n 1) where m 1, m 2 and n 1 are the lengths of A 1, A 2 and B 1 respectively. In this paper we consider two general variants of the C-LCS problem. First we show that in case of two input strings and an arbitrary number of constraint strings, it is NP-hard to approximate the C-LCS problem. Moreover, it is easy to see that in case of an arbitrary number of input strings and a single constraint, the problem of finding the constrained longest common subsequence is NP-hard. Therefore, we propose a linear time approximation algorithm for this variant, our algorithm yields a \(1 / \sqrt{m_{min}|\Sigma|}\) approximation factor, where m min is the length of the shortest input string and |Σ| is the size of the alphabet.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aho, A.V., Hirschberg, D.S., Ullman, J.D.: Bounds on the Complexity of the Longest Common Subsequence Problem. Journal of the ACM 23(1), 1–12 (1976)
Arslan, A.N., Egecioglu, Ö.: Algorithms For The Constrained Longest Common Subsequence Problems. International Journal of Foundations of Computer Science 16(6), 1099–1109 (2005)
Bergroth, L., Hakonen, H., Raita, T.: A Survey of Longest Common Subsequence Algorithms. In: Proc. SPIRE 2000, pp. 39–48 (2000)
Chin, F.Y.L., De Santis, A., Ferrara, A.L., Ho, N.L., Kim, S.K.: A simple algorithm for the constrained sequence problems. Information Processing Letters 90(4), 175–179 (2004)
Gotthilf, Z., Lewenstein, M.: Approximating Constrained LCS. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol. 4726, pp. 164–172. Springer, Heidelberg (2007)
Hirschberg, D.S.: A Linear Space Algorithm for Computing Maximal Common Subsequences. Communications of the ACM 18(6), 341–343 (1975)
Hirschberg, D.S.: Algorithms for the Longest Common Subsequence Problem. Journal of the ACM 24(4), 664–675 (1977)
Maier, D.: The Complexity of Some Problems on Subsequences and Supersequences. Journal of the ACM 25(2), 322–336 (1978)
Masek, W.J., Paterson, M.: A Faster Algorithm Computing String Edit Distances. Journal of Computer and System Sciences 20(1), 18–31 (1980)
Tsai, Y.-T.: The constrained longest common subsequence problem. Information Processing Letters 88(4), 173–176 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gotthilf, Z., Hermelin, D., Lewenstein, M. (2008). Constrained LCS: Hardness and Approximation. In: Ferragina, P., Landau, G.M. (eds) Combinatorial Pattern Matching. CPM 2008. Lecture Notes in Computer Science, vol 5029. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69068-9_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-69068-9_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69066-5
Online ISBN: 978-3-540-69068-9
eBook Packages: Computer ScienceComputer Science (R0)