TY - GEN
T1 - On the exact block cover problem
AU - Jiang, Haitao
AU - Su, Bing
AU - Xiao, Mingyu
AU - Xu, Yinfeng
AU - Zhong, Farong
AU - Zhu, Binhai
PY - 2014
Y1 - 2014
N2 - Minimum Common String Partition (MCSP) has drawn a lot of attention due to its application in genome rearrangement. The best approximation algorithm has a factor O(lognlog* n) and it was shown most recently that it is FPT (but with a very high running time). In this paper, we consider the decision version of the one-sided MCSP problem (formally called the exact block cover problem); namely, when one sequence is already partitioned into k blocks, how to decide whether the other sequence can be partitioned accordingly. While this decision problem is obviously in FPT, we show interesting results in this paper: (1) If each letter is allowed to appear at most twice (or three times), then the problem is polynomially solvable, (2) There is an FPT algorithm which runs in O*(2k) time, improving the trivial bound of O*(k!), and (3) If |∑| = c, c being a constant at least 2, then the problem is NP-complete.
AB - Minimum Common String Partition (MCSP) has drawn a lot of attention due to its application in genome rearrangement. The best approximation algorithm has a factor O(lognlog* n) and it was shown most recently that it is FPT (but with a very high running time). In this paper, we consider the decision version of the one-sided MCSP problem (formally called the exact block cover problem); namely, when one sequence is already partitioned into k blocks, how to decide whether the other sequence can be partitioned accordingly. While this decision problem is obviously in FPT, we show interesting results in this paper: (1) If each letter is allowed to appear at most twice (or three times), then the problem is polynomially solvable, (2) There is an FPT algorithm which runs in O*(2k) time, improving the trivial bound of O*(k!), and (3) If |∑| = c, c being a constant at least 2, then the problem is NP-complete.
UR - https://www.scopus.com/pages/publications/84903980845
U2 - 10.1007/978-3-319-07956-1_2
DO - 10.1007/978-3-319-07956-1_2
M3 - 会议稿件
AN - SCOPUS:84903980845
SN - 9783319079554
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 22
BT - Algorithmic Aspects in Information and Management - 10th International Conference, AAIM 2014, Proceedings
PB - Springer Verlag
T2 - 10th International Conference on Algorithmic Aspects of Information and Management, AAIM 2014
Y2 - 8 July 2014 through 11 July 2014
ER -