palindromic subsequences

Question

I'd like any insight or references to the following two conjectures (see the glossary below for definitions):

Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and its reversal $x^R$ that is a palindrome.

Conjecture 2: For any string $x$ over a two-letter alphabet, all longest common subsequences of $x$ and $x^R$ are palindromes.

Conjecture 2 is not true for strings over a three-letter alphabet, a counterexample being $abacbab$, which has $abcab$ and $bacba$ as longest common subsequences.

Glossary:

A string (or word) is any finite sequence of objects ("letters") drawn from some finite set (the "alphabet").

For any string $x = x_1x_2\cdots x_{n-1}x_n$ of length $n$, the reversal of $x$ is $x^R := x_nx_{n-1}\cdots x_2x_1$.

A string $x$ is a palindrome if $x = x^R$.

A string $x$ is a subsequence of a string $y$ if $x$ results from $y$ by removing zero or more letters (in arbitrary locations, closing up any gaps that result).

A longest common subsequence (LCS) of two strings $x$ and $y$ is a string $z$ that is a subsequence of both $x$ and $y$ such that no string longer than $z$ has this property. Generally, $x$ and $y$ may have several different LCSs. There is a well-known algorithm to find an LCS of two given strings that runs in quadratic time (see e.g., Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms).

Answer 1

OK. Having failed to make a counterexample, let's attempt a proof of Conjecture 1.

Suppose that $x$ and $x^R$ have a common subsequence $s$ of length $k$. This means that there are $n_1 < n_2 < \ldots < n_k$ and $m_1 > m_2 > \ldots > m_k$ such that $x_{n_i}=x_{m_i}$.

Now look for the place where they cross: $j=\max\{i\colon n_i\le m_i\}$. Terms prior to $j$ are paired with things in front of them; terms after are paired with things behind them. The $j$ term could be paired either with itself or something in front. By reversing the sequence if necessary you can assume that $j\ge k/2$. Further if $j=k/2$ you can assume that $n_j < m_j$ as otherwise by reversing the sequence you get $j=k/2+1$.

Now you can construct a palindromic subsequence: $x_{n_1}x_{n_2}\ldots x_{n_{k/2}}x_{m_{k/2}}x_{m_{k/2-1}}\ldots x_{m_1}$ in the case where $k$ is even or $x_{n_1}x_{n_2}\ldots x_{n_{(k+1)/2}}x_{m_{(k-1)/2}}\ldots x_{m_1}$ in the case where $k$ is odd.

Answer 2

This problem is discussed and solved here .