Exact and kernelization algorithms for Closet String





Closest String Problem, Combinatorial Optimization, Exact Algorithm, Fixed Parameter Algorithm, Kernelization


In this paper we address CLOSEST STRING problem that arises in web searching, coding theory and computational molecular biology. To solve it is to find a string that minimizes the maximum Hamming distance from a given set of strings. CLOSEST STRING is an NP-hard problem. This paper proposes two linear-time algorithms, one for the general case, a kernelization algorithm, and the other for three-strings, a linear-time algorithm called Minimization First Algorithm (MFA). A formal proof of the correctness and the computational complexity of the proposed algorithms are given.

Author Biography

Omar Latorre Vilca, Facultad de Ciencias, Universidade Estadual de Mato Grosso do Sul, Cidade Universitária de Dourados, Mato Grosso do Sul-Brazil.

Doutor em Informática pelo Instituto de Computação da Universidade Federal do Amazonas (IComp/UFAM). Possui o título de mestre em Ciência da Computação na Universidade Federal do ABC. Possui graduação (Bachalerado) em Sistemas da Informação na Universidad Nacional San Antonio Abad del Cusco diploma revalidado pelo IComp/UFAM. Atualmente é professor na UEMS nos cursos de Sistemas de Informação e Ciências da Computação. 


Amir A, Paryenty H, and Roditty L. Configurations and minority in the string consensus problem. Algorithmica. 2016; 74(4):1267-1292.

Basavaraju M, Panolan F, Rai A, Ramanujan MS, Saurabh S. On the kernelization complexity of string problems. Theoretical Comp. Science. 2018; 730:21–31.

Boucher C, Brown DG, and Durocher S. On the Structure of Small Motif Recognition Instances.. Berlin Heidelberg: Springer; 2009. p.269-281.

Fomin FV, Lokshtanov D, Saurabh S, Zehavi M. Kernelization: Theory of Parameterized Preprocessing. Great Britain: Cambridge University Press; 2019. chapter 1.

Frances M and Litman A. On covering problems of codes. Theor. Comput. Syst. 1997; 30:113-119.

Gramm J, Niedermeier R, Rossmanith P. Exact solutions for closest string and related problems. In: ISAAC ’01. Proceedings of the 12th International Symposium on Algorithms and Computation; 2001. p.441-453.

Gramm J, Niedermeier R, Rossmanith P. Fixed-parameter algorithms for closest string and related problems. Algorithmica. 2003; 37(1):25-42.

Lenstra Jr HW. Integer programming with a fixed number of variables. Mathematics of Operations Research. 1983; 8(4):538-548.

Liu X, Liu S, Hao Z, Mauch H. Exact algorithm and heuristic for the closest string problem. Computers & Operations Research. 1011; 38(11):1513-1520.

Ma B, Sun X. More Efficient Algorithms for Closest String and Substring Problems. Berlin Heidelberg; Springer; 2008. p.396-409.

Storer JA. Data compression: Methods and theory. New York: Computer Science Press, Inc. 1988. chapter 1.

Vilca OL. Combinatorial Approaches for the Closest String Problem.[ Doctoral thesis]. Amazonas: Federal university of Amazonas, Computing institute. 2019. Recovered from fttps://tede.ufam.edu.br/handle/tede/7449.




How to Cite

Latorre Vilca, O. (2020). Exact and kernelization algorithms for Closet String. Selecciones Matemáticas, 7(02), 257-266. https://doi.org/10.17268/sel.mat.2020.02.08