Solving longest common subsequence problems via a transformation to the maximum clique problem. (January 2021)

• Record Type: Journal Article
• Authors: Blum, Christian; Djukanovic, Marko; Santini, Alberto; Jiang, Hua; Li, Chu-Min; Manyà, Felip; Raidl, Günter R.
• Is Part Of: Computers & operations research. Volume 125(2021)
• Publication Date: 2021-01
• Subjects: Longest common subsequence -- Transformation to maximum clique -- Exact and heuristic solvers; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105089
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We define a new way to transform longest common subsequence problem instances into instances of the maximum clique problem. Moreover, the resulting graphs are reduced by making use of problem-specific information. Finally, we apply heuristic and exact maximum clique solvers to the resulting problem instances. As a result we were able to solve numerous problem instances from the literature to proven optimality. Abstract: Longest common subsequence problems find various applications in bioinformatics, data compression and text editing, just to name a few. Even though numerous heuristic approaches were published in the related literature for many of the considered problem variants during the last decades, solving these problems to optimality remains an important challenge. This is particularly the case when the number and the length of the input strings grows. In this work we define a new way to transform instances of the classical longest common subsequence problem and of some of its variants into instances of the maximum clique problem. Moreover, we propose a technique to reduce the size of the resulting graphs. Finally, a comprehensive experimental evaluation using recent exact and heuristic maximum clique solvers is presented. Numerous, so-far unsolved problem instances from benchmark sets taken from the literature were solved to optimality in this way.