[Solved]: Time complexity of a problem inspired by palindromes

Problem Detail: 

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

EVEN PALINDROME:

Input: Given a list of strings $[v_i, 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.

Asked By : Mohammad Al-Turkistany

Answered By : Vor

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$

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

We add the long string:

$$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 \}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57335

3.2K people like this

 Download Related Notes/Documents