4
$\begingroup$

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous) subsequence of $S$, and likewise for $S_2$. But now I ask whether I can have matches $m_1$ and $m_2$ of $S_1$ and $S_2$ as subsequences of $S$ ($m_k$ for $k \in \{1, 2\}$ is a strictly increasing function from $\{1, \ldots, |S_k|\}$ to $\{1, \ldots, |S|\}$ such that, for all $i$, $S_k[i]$ and $S[m_k(i)]$ are the same letter) such that $m_1$ and $m_2$ are disjoint (that is, their images are disjoint). Intuitively, no character of $S$ matches $S_1$ and $S_2$ simultaneously.

Is there a PTIME algorithm to determine this (in the size of the input $S_1, S_2, S$), or can it be shown to be NP-hard? I would suspect it is NP-hard but I cannot see a reduction.

In case it is in PTIME, what about the straightforward generalization, for a constant $k$, where $k$ strings are given as input and I ask for the existence of pairwise disjoint matches of all $k$ strings?

(This problem is a bit related to How hard is unshuffling a string? except the candidate strings can be different, are provided as input, and are not required to cover the entire string $S$.)

$\endgroup$
  • $\begingroup$ It seems that cs.se had a question about a special case of this problem where $S_1=S_2$, and no answer about the hardness was reached. $\endgroup$ – R B Sep 25 '14 at 8:29
  • $\begingroup$ @RB: Thanks for pointing this out. I think neither problem is obviously "harder" than the other, though, as in my case you may have $S_1 \neq S_2$ but the specific strings to use are provided in the input. $\endgroup$ – a3nm Sep 25 '14 at 8:41
  • 2
    $\begingroup$ Did you try a big dynamic program? e.g. $v[i,j,k] = True$ if the problem is solvable when the input is the first $i$ characters of $S_1$, the first $j$ characters of $S_2$, and the first $k$ characters of $S$; $v[i,j,k] = False$ otherwise. $\endgroup$ – usul Sep 26 '14 at 2:39
  • $\begingroup$ @usul: You are right, I had missed it but this dynamic algorithm does seem to work. Thanks! $\endgroup$ – a3nm Sep 26 '14 at 6:33
4
$\begingroup$

Case k=2

Perhaps you can use the following polynomial time dynamic approach:

Keep a table $T_i$ of $(|S_1|+1)(|S_2|+1)$ pairs, in which element $(x,y)=1$ if and only if after scanning $i$ elements of the reference string $S$, $x$ characters of $S_1$ have been found, and $y$ characters of $S_2$ have been found (without overlaps).

Every pair of the table $T_0 (i=0)$ is zero except for the pair $(0,0)=1$. Copy $T_i$ to $T_{i+1}$ and read the next character $c=S[i+1]$ from $S$; if in $T_i$ there is an entry $(x,y)=1$ such that $S[x+1]=c$ then in $T_{i+1}$ set $(x+1,y)=1$; if in $T_i$ there is an entry $(x',y')=1$ such that $S[y'+1]=c$ then in $T_{i+1}$ set $(x',y'+1)=1$.

At the end of the scan, $S$ contains the merged distinct copies of $S_1$ and $S_2$ if and only if $(|S_1|,|S_2|)=1$.

Simple example:

S  =  a b a a c
S1 =  a a c
S2 =  b a  

S    0,0  0,1  0,2 1,0 1,1 1,2 2,0 2,1 2,2 3,0 3,1 3,2
     1    0    0   0   0   0   0   0   0   0   0   0  < T0
a    1    0    0   1   0   0   0   0   0   0   0   0  < T1
b    1    1    0   1   1   0   0   0   0   0   0   0  < T2
a    1    1    1   1   1   1   1   1   0   0   0   0  < T3   
a    1    1    1   1   1   1   1   1   1   0   0   0  < T4       
c    1    1    1   1   1   1   1   1   1   1   1  [1] < T5

Case k fixed

The same approach above can be used for any fixed $k >2$ (the table size grows polynomially).

Case k not fixed

If $k$ strings are given as input, and $k$ is NOT FIXED: in that case there is a quick reduction from the 3-PARTITION problem which is strongly NP-complete, so it remains NPC even when the input numbers are represented in unary.

Given a set of $A = \{x_1,x_2,...,x_{3m}\}$ of $3m$ positive integers (that can be specified in unary), and a target sum $B$ we must find $m$ disjoint subsets $A_1,A_2,...,A_m \subseteq A$ of $3$ elements ($|A_i|=3$), and the sum of the elements of each subset must be $B$.

Over alphabet $\{a,b,c\}$, set:

  • "reference" string $S = a^3 \; b^B\; c^3 \; a^3 \; b^B\; c^3 \; ... a^3 \; b^B\; c^3 \;$ ($a^3 b^B c^3$ repeated $m$ times)
  • for $i = 1,...,3m$ set string $S_i = a \; b^{x_i} \; c$

Informally: the $a^3$ parts of $S$ force to match $3$ of the $S_i$s (otherwise some $S_i$ will not be included); the $c^3$ parts force to "close" $3$ of the $S_i$s. And the $b^B$ blocks (there are $m$ of them) must be filled exactly with the $b^{x_i}$ substrings of $3$ distinct $S_i$.

Small example:

3-PARTITION instance: $A = \{ 3, 2, 1, 5, 4, 3\}, B=9, (m=2)$

S  = aaa bbbbbbbbb ccc aaa bbbbbbbbb ccc
S1 = a bbb c
S2 = a bb c
S3 = a b c
S4 = a bbbbb c
S5 = a bbbb c
S6 = a bbb c
$\endgroup$
  • $\begingroup$ Thanks! Thinking about it for a bit more I understand that the dynamic algorithm (the workings of which I already understood when the $S_i$'s had to cover the entire $S$) does indeed work without this assumption. This satisfies me. (So, in what you posted: this is not a greedy algorithm, for what I understand, but a dynamic algorithm.) And yes, I already knew (following a previous answer by you :)) that the problem for unbounded $K$ is strongly NP-hard by a reduction from 3-PARTITION. :) $\endgroup$ – a3nm Sep 26 '14 at 6:35
  • $\begingroup$ @a3nm: yes dynamic, changed :-) $\endgroup$ – Marzio De Biasi Sep 26 '14 at 6:49
  • $\begingroup$ Your version of 3-PARTITION is wrong. In the real 3-PARTITION, it is necessary to divide $A$ into $m$ sets of size $3$, not into $3$ sets of size $m$. Your version is not strongly NP-hard (unless P=NP), because there is a pseudopolynomial algorithm similar to that for knapsack problem. $\endgroup$ – abacabadabacaba Oct 2 '14 at 11:46
  • $\begingroup$ @abacabadabacaba: you are right, too many reductions in my mind :-) However the reduction I had in mind follows the correct definition (see another similar answer); I fixed the answer. $\endgroup$ – Marzio De Biasi Oct 2 '14 at 12:31

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.