@inproceedings{14eb0c839174443ca16b45b686a9de3a,
title = "On Finding Longest Palindromic Subsequences Using Longest Common Subsequences",
abstract = "Two standard textbook problems illustrating dynamic programming are to find the longest common subsequence (LCS) between two strings and to find the longest palindromic subsequence (LPS) of a single string. A popular claim is that the longest palindromic subsequence in a string can be computed as the longest common subsequence between the string and the reversed string. We prove that the correctness of this claim depends on how the longest common subsequence is computed. In particular, we prove that the classical dynamic programming solution by Wagner and Fischer [JACM 1974] for finding an LCS in fact does find an LPS, while a slightly different LCS backtracking strategy makes the algorithm fail to always report a palindrome.",
keywords = "dynamic programming, longest common subsequence, Palindromic subsequence",
author = "Brodal, \{Gerth St{\o}lting\} and Rolf Fagerberg and Rysgaard, \{Casper Moldrup\}",
year = "2024",
month = sep,
doi = "10.4230/LIPIcs.ESA.2024.35",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl Publishing",
editor = "Timothy Chan and Johannes Fischer and John Iacono and Grzegorz Herman",
booktitle = "32nd Annual European Symposium on Algorithms, ESA 2024",
address = "Germany",
note = "32nd Annual European Symposium on Algorithms, ESA 2024 ; Conference date: 02-09-2024 Through 04-09-2024",
}