5
$\begingroup$

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.

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

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:

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

$\endgroup$
  • $\begingroup$ Does this reduction also proof NP-completeness if we require $w \in \{uu \in \Sigma^* \}$? $\endgroup$ – Mohammad Al-Turkistany Nov 21 '17 at 20:48
  • $\begingroup$ @MohammadAl-Turkistany: yes the construction is similar. $\endgroup$ – Vor Nov 22 '17 at 13:11
  • $\begingroup$ But I guess you we need to change W. Right? $\endgroup$ – Mohammad Al-Turkistany Nov 22 '17 at 13:28
  • 1
    $\begingroup$ @D.W. : the problem remains NP-complete when every integer in S is strictly between p/4 and p/2 (see G&J) $\endgroup$ – Vor Aug 15 '18 at 1:16
  • 1
    $\begingroup$ @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. $\endgroup$ – xskxzr Aug 15 '18 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.