# Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange.

EVEN PALINDROME:

Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i|$ is even number.

Question: Is there a permutation $\sigma$ such that $w=v_{\sigma(1)}v_{\sigma(2)}... v_{\sigma(n)}$ $\in \{uu^R \in \Sigma^* \}$.

Is it NP-complete to determine if a given set of strings can be ordered to form a palindrome (of even length as defined above)? If yes, Is it still NP-complete for $|\Sigma|=2$?

EDIT: Marzio has given an elegant reduction which shows that Even Palindrome is NP-complete for binary alphabets.

• @Raphael The suggested reduction from partition is not suitable since reversing the digits of a number would change the value. – Mohammad Al-Turkistany May 11 '16 at 16:24
• Ouch ... the downvote suggests that there is a much simpler solution than mine ... ?!? ;-) :-D – Vor May 11 '16 at 16:25
• @Vor What could be simpler than polynomial time algorithm? :) – Mohammad Al-Turkistany May 11 '16 at 16:31
• @MohammadAl-Turkistany P offers rich levels of complexity, and simplicity is completely orthogonal. – Raphael May 11 '16 at 20:12
• @D.W. I think that it's unlikely that Partition can work because it is not strongly NP-complete. – Vor May 12 '16 at 9:08

After a wrong polynomial-time attempt, this is a more robust idea to prove that the problem is indeed NP-complete.

The reduction is from the 3-PARTITION problem which is strongly NP-complete; i.e. it is still NP-complete even if the numbers are represented in unary.

The problem is to decide whether a given multiset $S = \{a_1,a_2,...,a_n\}$ of $n = 3 m$ positive integers, can $S$ be partitioned into $m$ triplets $S_1, S_2, ..., S_m$ such that the sum of the numbers in each subset is equal?

Let $p = (\sum_i a_i) / m$

Note that the problem remains strongly NP-complete even if $p/4 < a_i < p/2$ (which forces each $S_i$ to contain at exactly three elements); see the original definition of 3-PARTITION in Garey&Johnson, Computers and Intractability.

We can build an equivalent EVEN PALINDROME instance in this way:

$$w = 1 \, 0^p \, 111 \, 0^p 11111 \, 0^p \, ... \, 0^p \, 1^{2m+1}$$

Then we add $n$ more strings:

$$v_i = 0^{a_i}\; , \;i = 1...n$$

and $1 + 3 + 5 + (2m+1) = \sum_{j=1}^{m+1} (2j-1)$ strings of length 1:

$$r_k = 1 \; , \; k = 1...\sum_{j=1}^{m+1} (2j-1)$$

Note that $|w| = \sum_{i=1}^n |v_i| + \sum_k |r_k|$

Proof:

By construction the $w$ contains substrings of odd increasing length $(1,111,11111, ...)$, so it cannot be "placed" in the middle of $u u^R$; but it must be placed entirely in $u$ or entirely in $u^R$ (without loss of generality suppose that it is placed in $u$.

Now the others $v_i$ must be arranged in the opposite part $u^R$ and in such a way that every $p$ zeroes (that can be "totalized" using the $v_i$) an odd number of the $r_k$ can be placed (to reflect the corresponding $1^{2j+1}$ substring of $w$). Furthermore all elements must be placed, so exactly 3 $v_i$ must be picked to reflect each of the $0^p$ substring of $w$. So if an EVEN PALINDROME can be found it induces a valid 3-partition of the $a_i$ of the original problem.

The opposite direction (a 3-partition exists $\Rightarrow$ there is an EVEN PALINDROME is immediate by construction).

Example:

3-Partition instance: $S = \{1, 1, 1, 2, 2, 3 \}$, strongly NP-complete; so we can also represent the numbers in unary: $S' = \{ 1_1, 1_1, 1_1, 11_1, 11_1, 111_1 \}$

EVEN PALINDROME reduction:

$w = 1000001110000011111$

$v_i = \{ 0, 0, 0, 00, 00, 000 \}$

$r_k = \{ 1,\quad 1,1,1,\quad 1,1,1,1,1 \}$

Solution of EVEN PALINDROME:

$$uu^R = 1000001110000011111 \quad 11111 \; 0 \; 00 \; 00 \; 111 \; 000 \; 0\; 0\; 1\}$$

which corresponds to the 3-partition:

$S_1 = \{ 1, 2, 2 \}, S_2 = \{ 3, 1, 1 \}$

• Does this reduction also proof NP-completeness if we require $w \in \{uu \in \Sigma^* \}$? – Mohammad Al-Turkistany Nov 21 '17 at 20:48
• @MohammadAl-Turkistany: yes the construction is similar. – Vor Nov 22 '17 at 13:11
• But I guess you we need to change W. Right? – Mohammad Al-Turkistany Nov 22 '17 at 13:28
• @D.W. : the problem remains NP-complete when every integer in S is strictly between p/4 and p/2 (see G&J) – Vor Aug 15 '18 at 1:16
• @Vor Is it strongly NP-complete if every integer is strictly between p/4 and p/2? In addition, I think this point is a key point thus should be added to the answer. – xskxzr Aug 15 '18 at 3:58