Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem
Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem
复制标题
有界重复最长公共子序列问题的精确算法
DOI：
10.1016/j.tcs.2020.07.042
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Tadatoshi Utashima
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Jesper Jansson;Guohui Lin;Eiji Miyano;Hirotaka Ono;Tadatoshi Utashima
本文研究了经典最长公共子序列问题的一个变种--有界重复最长公共子序列问题的精确指数时间算法：设字母表S是符号的有限集合，出现约束Cc是函数Cc：S→N，给出每个符号在S中出现的次数的一个上界，给定字母表S上的两个序列X和Y，以及出现约束Cocc，RBLCS的目标是找到一个X和Y的最长公共子序列，使得每个符号S∈S在所得到的子序列中最多出现C o c c(S)次。对于每一个符号，C o c c(S)=1的特例被称为无重复最长公共子序列问题，称为无重复最长公共子序列问题，例如在[1]中，∈Adi等人.给出了一种简单的(指数时间)精确算法。然而，他们并没有对其时间复杂性进行详细的分析，而且据我们所知，目前还没有关于这个问题的任何确切算法的运行时间的结果。在不失一般性的前提下，我们将假设|X|≤|Y|和|X|=n。在本文中，我们首先基于文[1]中的策略提出了一个更简单的算法，并明确地证明了它的运行时间为O(1.44225 n)。其次，给出了一种基于动态规划(DP)的RBLCS算法，证明了对于任意出现约束Cocc，该算法的运行时间为O(1.44225 n)，在某些特殊情况下运行时间更短。特别是，对于RFLCS，我们的基于DP的算法的运行时间为O(1.41422 n)，比以前的算法快。此外，我们还证明了受限实例上RBLCS的NP-硬度和APX-硬度结果。
In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C o c c be a function C o c c: S→ N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint C o c c, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s∈ S appears at most C o c c (s) times in the obtained subsequence. The special case where C o c c (s)= 1 for every symbol s∈ S is known as the Repetition-Free Longest Common Subsequence problem (RFLCS) and has been studied previously; eg, in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that| X|≤| Y| and| X|= n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O (1.44225 n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O (1.44225 n) for any occurrence constraint C o c c, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O (1.41422 n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.