A hardness result and new algorithm for the longest common palindromic subsequence problem

Shunsuke Inenaga, Heikki Hyyrö

The 2-LCPS problem, first introduced by Chowdhury et al. [Fundam. Inform., 129(4):329-340, 2014], asks one to compute (the length of) a longest palindromic common subsequence betwe…