LIGM, CNRS, Université Gustave Eiffel, Marne-la-Vallée
Francelaurent.bulteau@univ-eiffel.frhttps://orcid.org/0000-0003-1645-9345
Department of Informatics University of Bergen Bergen, Norway
<EMAIL_ADDRESS>Fachbereich für Mathematik und Informatik, Philipps-
Universität Marburg<EMAIL_ADDRESS>marburg.dehttps://orcid.org/0000-0003-0829-7032 Department of Informatics
University of Bergen Bergen<EMAIL_ADDRESS>Laurent Bulteau,
Michael R. Fellows,
Christian Komusiewicz, Frances Rosamond [100]Theory of computation
Parameterized complexity and exact algorithms

###### Acknowledgements.

We want to thank Shonan Workshop 045 in which this work was initiatedJohn Q.
Open and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016)
ARXIV 2021 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 X

# Parameterized String Equations

Laurent Bulteau  Michael R. Fellows  Christian Komusiewicz  Frances Rosamond

###### Abstract

We study systems of _String Equations_ where block variables need to be
assigned strings so that their concatenation gives a specified target string.
We investigate this problem under a multivariate complexity framework,
searching for tractable special cases such as systems of equations with few
block variables or few equations. Our main results include a polynomial-time
algorithm for size-2 equations, and hardness for size-3 equations, as well as
hardness for systems of two equations, even with tight constraints on the
block variables. We also study a variant where few deletions are allowed in
the target string, and give XP algorithms in this setting when the number of
block variables is constant.

###### keywords:

String Equations, String Morphism, Parameterized Algorithms, Parameterized
Complexity

###### category:

##  1 Introduction

_String equations_ are equations in which the variables, called _block
variables_ in this work, can be assigned arbitrary strings. We study the case
where a string equation can express that the concatenation of a given list of
blocks must equal a specific string. We study the problem of finding a
solution for a given set of string equations within a multivariate complexity
framework, searching for tractable special cases such as systems of equations
with few blocks variables or few equations.

### Related Work

The single-equation problem can be seen as a _String Morphism_ question, for
which many variants have been extensively studied in the literature (see
Fernau et al. [8] for an overview of related works). A possible starting point
is the _pattern discovery_ problem [1]: given a set of strings, find a pattern
(i.e. a string of characters and variables), of minimal length, that may
generate each input string by assigning values to each block variable.
Deciding if a given pattern generates a string can be seen, in our setting, as
a single string equation. Angluin [1, Theorem 3.2.3] proves that this problem
is NP-hard, by reduction from SAT. She also identifies the brute-force
$O(n^{k})$ algorithm (which requires linear space [9]). Fernau et al. [7, 8]
further prove (among other variants) W[1]-hardness when parameterized by the
number of block variables. A notable variant is the _injective_ case (where
blocks must be assigned distinct strings) which in its simplest version can be
formulated as the following NP-hard problem [6]: given a string $T$ and an
integer $k$, can $T$ be split into $k$ distinct factors?

For two equations, if the blocks are used once in each equation, the String
Equations formulation can be related to Minimum Common String Partition (where
two target strings are given, but the block variables can be permuted in any
order). Interestingly, this problem is FPT for the number of blocks [3] but
becomes W[1]-hard if the permutation of the blocks is fixed (Theorem 4.5).

### Formal definitions

Given a string $S$, we write $|S|$ for the length of $S$, and $S[i]$ for the
$i$th letter of $S$ (for $1\leq i\leq|S|$). We use
$\prod_{i=1}^{n}S_{i}:=S_{1}S_{2}\ldots S_{n}$ to denote the concatenation of
strings $S_{1}$ to $S_{n}$. We distinguish _substrings_ (obtained by taking
consecutive characters from $s$) from _subsequences_ (obtained by taking not-
necessarily consecutive characters from $s$).

Given an alphabet $\Sigma$ and a set ${\mathcal{B}}$ of _block variables_
(also called _blocks_ for simplification), with $\Sigma$ and ${\mathcal{B}}$
being disjoint, a _string equation_ over $(\Sigma,{\mathcal{B}})$ is a pair
$(T,{\mathcal{X}})$, written $T\equiv{\mathcal{X}}$, where $T$ (resp.
${\mathcal{X}}$) is a non-empty string over $\Sigma$ (resp. ${\mathcal{B}}$).
$T$ is the _target string_ of the equation. A _system of equations_ is a set
of string equations. A block which appears only once in a given system of
equations is said to be a _joker_ , and is denoted ${*}$. A system of
equations is _duplicate-free_ if no block appears twice in the same string
${\mathcal{X}}$.

An _assignment_ of the block variables is a function
$\sigma:{\mathcal{B}}\rightarrow\Sigma^{+}$ that assigns to each block
variable a non-empty string over $\Sigma$. For ${\mathcal{X}}=X_{1}X_{2}\ldots
X_{c}\in{\mathcal{B}}^{+}$, we write
$\sigma({\mathcal{X}})=\prod_{i=1}^{c}\sigma(X_{i})$. An equation
$T\equiv{\mathcal{X}}$ is _satisfied_ by an assignment $\sigma$ if
$T=\sigma({\mathcal{X}})$, that is, replacing ${\mathcal{X}}$ by the
concatenation of the corresponding strings yields exactly $T$. A system of
equations is satisfied if all equations are satisfied. An example is given in
Figure 1.

$a\,b\,c$
---
$a\,b$
---
$\displaystyle\equiv{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$A$}}\cr\rule[-5.5pt]{10.83334pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}$ $\displaystyle\sigma(A)$
$\displaystyle:={\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a\,b\,c$}}\cr\rule[-5.5pt]{20.57169pt}{1.5pt}}}}$ $a\,b\,c$
---
$d$
---
$a\,b\,c$
---
$d$
---
$\displaystyle\equiv{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$A$}}\cr\rule[-5.5pt]{10.83334pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$C$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\,{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$A$}}\cr\rule[-5.5pt]{10.83334pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$C$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}$ $\displaystyle\sigma(B)$
$\displaystyle:={\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a\,b$}}\cr\rule[-5.5pt]{14.5775pt}{1.5pt}}}}$ $a\,b$
---
$d$
---
$\displaystyle\equiv{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$C$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}$ $\displaystyle\sigma(C)$
$\displaystyle:={\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}$ Figure 1:  Left: a string equation
system with alphabet $\Sigma=\\{a,b,c,d\\}$ and block variables
${\mathcal{B}}=\\{A,B,C\\}$. Right: a solution (assignment) $\sigma$ for this
system, with the corresponding substrings highlighted with different colors in
the target strings.

### The String Equations Problem and its Variants

We define the String Equations problem as follows:

Input: A system of equations
${\mathcal{E}}=\\{T_{1}\equiv{\mathcal{X}}_{1},T_{2}\equiv{\mathcal{X}}_{2},\ldots,T_{r}\equiv{\mathcal{X}}_{r}\\}$.
Question: Does ${\mathcal{E}}$ admit a satisfying assignment $\sigma$?

We consider the _duplicate-free_ restriction of String Equations, where no
block may appear twice in any ${\mathcal{X}}_{i}$. We also consider a more
general problem where a number of deletions is allowed, String Equations with
Deletions.

Input: A system of equations
${\mathcal{E}}=\\{T_{1}\equiv{\mathcal{X}}_{1},T_{2}\equiv{\mathcal{X}}_{2},\ldots,T_{r}\equiv{\mathcal{X}}_{r}\\}$,
an integer $d$
Question: Does there exist $r$ strings $T_{1}^{\prime},\ldots,T_{r}^{\prime}$
obtained from $T_{1},\ldots,T_{r}$ by removing a total of at most $d$ letters,
such that the equations $T_{i}^{\prime}\equiv{\mathcal{X}}_{i}$ admit a
satisfying assignment $\sigma$?

Finally, motivated by the similarities with the Minimum Common String
Partition problem, we are interested in the restriction with $r=2$ duplicate-
free equations without joker blocks. In this setting, we consider the
variation where blocks may be assigned empty strings (remember that by
default, $\sigma$ must be _non-erasing_ , i.e. $\sigma(T)$ is not empty), see
Theorem 4.5.

Since the size of each $\sigma(A)$ can be bounded by the input size, and it is
trivial to verify whether an equation is satisfied by a given assignment,
String Equations is clearly in NP. Similarly, String Equations with Deletions
and all variants mentioned here are also clearly in NP.

### Parameterized Complexity

For an introduction to parameterized complexity theory, we refer to the
monograph of Downey and Fellows [4]. An instance $(x,\kappa)$ of a
parameterized problem consists of a classical problem instance $x$ and a
parameter $\kappa\in\mathds{N}$. A parameterized problem is _fixed-parameter
tractable_. or equivalently is in FPT, if there exists an algorithm that
solves every instance $(x,\kappa)$ in $f(\kappa)\cdot|x|^{{\mathcal{O}}(1)}$
time. A parameterized problem has an XP-algorithm, or equivalently is in XP,
if there exists an algorithm that solves every instance $(x,\kappa)$ in
$|x|^{g(\kappa)}$ time. To show that problems in XP are unlikely to be in FPT,
one may use parameterized reductions from W[1]-hard problems, i.e.,
polynomial-time reduction between parameterized problems such that the
parameter of the reduced instance is a function of the orginal parameter.

We use the following classic W[1]-hard problem in our reduction.

Clique
Input: A graph $G=(V,E)$
Question: Does $G$ contain a clique of size $\kappa$?

In addition, we use a constrained version of the problem, where the vertices
are colored so that a clique must use exactly one vertex with each color :

Multicolored Clique
Input: A $\kappa$-partite graph $G=(V=\bigcup_{i=1}^{\kappa}V_{i},E)$.
Question: Does $G$ contain a clique of size $\kappa$ in $G$?

Multicolored Clique is W[1]-hard for parameter $\kappa$ [5, 10]. An example
instance is given in Figure 2, it will be used as an example for our
reductions. By convention we write $n=|V|$, $m=|E|$,
$V=\\{v_{1},\ldots,v_{n}\\}$, $E=\\{e_{1},\ldots,e_{m}\\}$. For convenience,
we assume that edges are size-2 strings over alphabet $V$, that is,
$e_{j}=v_{s}v_{t}$ for an edge $\\{v_{s},v_{t}\\}$ with $s<t$. Moreover, we
assume that $E$ is sorted lexicographically, that is, for $e_{j}=v_{s}v_{t}$
and $e_{j^{\prime}}=v_{s^{\prime}}v_{t^{\prime}}$ we have $j<j^{\prime}$ iff
$s<s^{\prime}$ or $s=s^{\prime}$ and $t<t^{\prime}$.

$a$$c$$d$$b$ Figure 2:  Running example for reductions from Clique (or Multi-
colored Clique): a (3-colored) graph $G=(V,E)$ where $V=\\{a,b,c,d\\}$ and
$E=\\{ab,ac,bc,bd,cd\\}$. For $\kappa=3$, $G$ contains two triangles:
$\\{a,b,c\\}$ and $\\{b,c,d\\}$.

##  2 Overview of the results

In our complexity study, we consider the following five quantities:

  * •

$t$, the maximum size of any target string

  * •

$r$, the number of equations

  * •

$c$, the maximum number of blocks per equation,

  * •

$k$, the overall number of blocks

  * •

$d$, the number of deletions (for String Equations with Deletions)

We only only consider $r$, $c$, $k$ and $d$ as possible parameters (i.e. we
always assume $t$ to be unbounded). Observe that $k\leq rc$. Consequently, a
positive result for parameter $k$ implies a positive result for $rc$ and a
running time lower bound for $r+c$ implies a running time lower bound for $k$.
An overview of our results is given in Table 1.

We first show in Section 3 that the problem is polynomial-time solvable when
$k$ is any constant (i.e. XP for $k$, Proposition 3.1) using brute-force
enumeration. This raises the possibility of an FPT algorithm for parameter
$k$, which will be ruled out in the next sections, with hardness results
proving W[1]-hardness for parameter $k$ even in more restricted settings. We
also consider the deletions variant: our XP algorithm extends to parameter
$k+d$ (Proposition 3.3), but with parameter $k$ alone, we show that it is
already NP-hard for $k=1$ (Theorem 3.5). However, it is in XP for parameter
$r+c$ (Proposition 3.7).

We then focus, in Section 4, on the number $r$ of equations. W[1]-hardness is
already known for $r=1$ and parameter $c$ [1, 8]. We prove a similar result in
the duplicate-free setting when $r=2$ ($r=1$ is a trivial case for duplicate-
free equations). Note that W[1]-hardness follows for parameter $k$, since
$k\in{\mathcal{O}}(c)$ for constant $r$. We consider two slightly stronger
cases: one where both target strings are equal, and the other where block
variables may be assigned empty strings.

Finally, Section 5 is devoted to small-size equations (constant $c$). On the
negative side, String Equations remains W[1]-hard for parameter $r$ (and $k$)
when $c=3$. On the positive side, we give a polynomial-time algorithm for
size-2 equations, which generalizes to the case where non-joker blocks must
all be prefixes or suffixes of their equations. As a final attempt towards
generalizing this algorithm to other cases, we consider equation systems with
$(r-1)$ size-2 equations together with a single size-$c$ duplicate-free
equation. We show, however, that this special case is W[1]-hard for parameter
$r+c$ (Theorem 5.5).

| $k$ | $r$ | $c$ | $d$ |  | Complexity of String Equations
---|---|---|---|---|---|---
Constant number of blocks (Section 3) | C | $\star$ | $\star$ | 0 |  | XP | (Proposition 3.1)
C | $\star$ | $\star$ | C |  | XP | (Proposition 3.3)
C | $\star$ | $\star$ | P |  | open
1 | 1 | P | $\star$ |  |  W[2]-hard | (Theorem 3.5)
1 | P | 1 | $\star$ |  |  W[2]-hard | (Theorem 3.5)
C | C | C | $\star$ |  | XP | (Proposition 3.7)
Constant number of equations (Section 4) | P | 1 | P | 0 |  |  W[1]-hard |  [1, 8] (see also Theorem 4.1)
P | 2 | P | 0 | † |  W[1]-hard | (Theorems 4.3 and 4.5)
Constant equation sizes (Section 5) | $\star$ | $\star$ | 2 | 0 | † | P | (Proposition 5.1)
$\star$ | $\star$ | 2 | P |  | open
P | P | 3 | 0 |  |  W[1]-hard | (Theorem 5.3)
P | P | P | 0 | † |  W[1]-hard | (Theorem 5.5)
Table 1: Summary of our results . For each of $k$ (number of block variables),
$r$ (number of equations), $c$ (equation size) and $d$ (number of deletions),
we indicate if the result holds for the given integer, for any fixed constant
(C, for XP algorithms), when seen as a parameter (P, for FPT or W[1]-hardness)
or is unbounded ($\star$).
† These results still hold in a stronger setting: Theorem 4.3 holds for
duplicate-free equations with a unique target. Theorem 4.5 holds for
duplicate-free equations allowing empty blocks. Proposition 5.1 holds for
arbitrarily large equations, provided non-border blocks are all jokers.
Theorem 5.5 holds for duplicate-free equations, and all equations except one
have size 2.

##  3 Constant number of blocks

A straightforward brute-force algorithm that guesses endpoints of each block
shows that String Equations is in XP.

######  Proposition 3.1.

String Equations can be solved in ${\mathcal{O}}^{*}(t^{2k})$ time.

######  Proof 3.2.

For each block $X\in{\mathcal{B}}$, pick an equation $T\equiv{\mathcal{X}}$
where $X$ appears in ${\mathcal{X}}$, and branch into all possibilities to
choose integers $1\leq i\leq j\leq|T|\leq t$ such that $\sigma(X):=T[i]\ldots
T[j]$. Overall, this creates ${\mathcal{O}}(t^{2k})$ branches. For each
branch, it remains to check whether the resulting assignment satisfies
${\mathcal{E}}$, which can be done in linear time. The total running time is
thus ${\mathcal{O}}^{*}(t^{2k})$.

The algorithm above can be extended to the case where we allow for deletions
in the target strings.

######  Proposition 3.3.

String Equations with Deletions is in XP for parameter $k+d$.

######  Proof 3.4.

Branch into the at most $\binom{tr}{d}$ ways of building strings
$T_{1}^{\prime},\ldots,T_{r}^{\prime}$ out of $T_{1},\ldots,T_{r}$. Testing
each time if the resulting String Equation problem has a solution can be done
via Proposition 3.1, so the overall running time is $O^{*}((nr)^{d}t^{2k})$.

######  Theorem 3.5.

String Equations with Deletions is NP-hard for $k=1$. Moreover, String
Equations with Deletions is W[2]-hard for parameter $r$ when $k=c=1$ and
W[2]-hard for parameter $c$ when $k=r=1$.

######  Proof 3.6.

We note that String Equations with Deletions contains Longest Common
Subsequence as a sub-problem, using a single block $X$ and equations
$T_{1}\equiv X,\ldots,T_{r}\equiv X$ to denote the fact that $\sigma(X)$
should be a common subsequence of each $T_{i}$. In this setting, minimizing
the number of deletions $d=\sum_{i=1}^{r}|T_{i}|-r|\sigma(X)|$ is equivalent
to maximizing $|\sigma(X)|$, i.e. the length of the common subsequence. Since
LCS is W[2]-hard for the parameter number of strings $r$ [2], the same result
applies to String Equations with Deletions for $k=c=1$.

For the case with a single equation ($r=1$), it suffices to insert a
sufficiently long prefix $P=\$^{d}$ before each string, then again
$PT_{1}PT_{2}\ldots PT_{r}\equiv XX\ldots X$ has a solution reaching the
target number of deletions $d$ iff $T_{1},\ldots,T_{r}$ have an LCS reaching
the corresponding target size $\frac{1}{r}(\sum_{i=1}^{r}|T_{i}|-d)$.

######  Proposition 3.7.

String Equations with Deletions is in XP for parameter $r+c$.

######  Proof 3.8.

We introduce the following notation: given an equation $T\equiv{\mathcal{X}}$
satisfied by an assignment $\sigma$, the _starting point_ for block $i$ is the
index $j$, $1\leq j\leq|T|$, such that the first character of
$\sigma({\mathcal{X}}[i])$ is mapped to $T[j]$. Thus, if $j$ is the starting
point of block $i$ and $j^{\prime}$ is the starting point of block $i+1$ (or
$j^{\prime}=|T|+1$ if $i=|{\mathcal{X}}|$), then $\sigma({\mathcal{X}}[i])$ is
a subsequence of $T[j]\ldots T[j^{\prime}-1]$.

Consider a solution $\sigma$ for an instance $({\mathcal{E}},d)$ of String
Equations with Deletions. Compute the starting points of each block in each
equation: by the above remark, for each $X\in{\mathcal{B}}$ there exist
substrings of $T_{i}$s denoted $F_{1},\ldots,F_{h}$ such that $\sigma(X)$ is a
common subsequence of strings $F_{1},\ldots,F_{h}$ (with $h\leq rc$
corresponding to the number of occurrences of block $X$). Note that replacing
$\sigma(X)$ by any longest common subsequence of these strings still yield a
valid solution for the same problem, since the number of deletions performed
in target strings does not increase.

This leads to the following XP algorithm: branch into all possibilities to
choose a starting point of every block of ${\mathcal{E}}$; the number of
branches is ${\mathcal{O}}(t^{rc})$. For each block $X$, compute strings
$F_{1},\ldots,F_{h}$ as described above. Set $\sigma(X)$ to be a longest
common subsequence of these strings in time $O^{*}(t^{h})$: it remains to
check whether $\sigma$ is a solution to the original problem, which can be
done in linear time.

##  4 Constant number of equations

For the sake of completeness (and as a warm-up for following, more complex
reductions), we give a W[1]-hardness proof for the single-equation case (see
also Fernau et al. [8]).

######  Theorem 4.1.

String Equations with one equation (that is, $r=1$) is W[1]-hard for $c$.

######  Proof 4.2.

$\displaystyle T$ $\displaystyle=y_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\ y_{1}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y_{2}\ b\,c\ y_{3}\ b\,d\ y_{4}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y_{5}$ $\displaystyle T$
$\displaystyle\equiv{*}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R$}}\cr\rule[-5.5pt]{11.00348pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\ {*}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R$}}\cr\rule[-5.5pt]{11.00348pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\ {*}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\ {*}$ Figure 3:  Reduction of
Theorem 4.1 (using $r=1$ equation) applied to the graph from Figure 2 (using a
single string equation, with the target string described first, then its block
decomposition). In this and following examples, in order to lighten notations,
we use color initials $R,G,B$ or $r,g,b$ instead of indices $1,2,3$ to
highlight the fact that we select a vertex of the corresponding color in the
graph (or an edge between corresponding colors, i.e. $R,G,B$ designate
$X_{1},X_{2},X_{3}$ respectively, $R_{g},R_{b}$ designate $X_{1,2},X_{1,3}$,
etc). A satisfying assignment is given by colored underlines: $\sigma(R)=a$,
$\sigma(G)=c$, $\sigma(B)=d$.

See Figure 3. Consider an instance $(G=(V,E),\kappa)$ of Clique. Introduce
$m+1$ separators (i.e., new characters) denoted $y_{0},\ldots,y_{m}$, let
$\Sigma=V\cup\\{y_{0},\ldots,y_{m}\\}$. Introduce $\kappa$ non-joker blocks
$\\{X_{1},\ldots,X_{\kappa}\\}$ and ${\kappa\choose 2}+1$ joker blocks (for a
total of $k={\mathcal{O}}(\kappa^{2})$ blocks). Let

${\mathcal{E}}:=\\{T\equiv{\mathcal{X}}\\}\text{ where
}T:=y_{0}\prod_{i=1}^{m}(e_{j}y_{j})\text{ and }{\mathcal{X}}:={*}\prod_{1\leq
i<\kappa}\prod_{i<j\leq\kappa}(X_{i}X_{j}{*})$

This concludes the construction of the instance. We now show the correctness
of the reduction.

($\Rightarrow$) Assume that $G$ has a $\kappa$-clique
$\\{u_{1},\ldots,u_{\kappa}\\}$. Set $X_{i}:=u_{i}$. Then each $X_{i}X_{j}$
with $1\leq i<j\leq\kappa$ corresponds to an edge in $G$, hence it appears as
a substring in $T$, in lexicographical order (recall that we assume that the
edges of $G$ are ordered). Finally, joker blocks can be matched to the gaps
around selected edges, which are non-empty (they contain at least one
separator), so this assignment satisfies ${\mathcal{E}}$.

($\Leftarrow$) Assume that ${\mathcal{E}}$ has a satisfying assignment
$\sigma$. First, note that $\sigma(X_{i})$ may contain only characters from
$V$ (since $X_{i}$ is repeated $\kappa-1$ times and separators only once), and
at most one character (otherwise, $\sigma(X_{i}X_{j})$ contains three
characters, so by definition of $T$ at least one separator). Thus $X_{i}\in
V$. Furthermore, $X_{i}X_{j}$ is an edge of $E$ for each $1\leq
i<j\leq\kappa$, so $\\{X_{1},\ldots,X_{\kappa}\\}$ is a $\kappa$-clique.

Only with one equation the problem is already hard, but this definitely needs
duplications (since an instance having 1 duplicate-free equation is trivial).
Hence we look at instances with a constant number of equations, but no
duplicates: we show this case is hard as well, even in the _unique target_
case, i.e. when all target strings are equal.

######  Theorem 4.3.

String Equations with $r=2$ duplicate-free equations, a unique target and
parameter $c$ is W[1]-hard.

$\displaystyle T$ $\displaystyle=z\ x_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\ x_{1}\ b\,b\ x_{2}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\ x_{3}\
{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ x_{4}\ z^{\prime}\ y_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\ y_{1}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y_{2}\ b\,c\ y_{3}\ b\,d\ y_{4}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y_{5}$ $\displaystyle T$
$\displaystyle\equiv Z\ A_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\ A_{1}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\ A_{2}\
{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\ A_{3}\ Z^{\prime}\ B_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}^{\prime}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}^{\prime}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}\ B_{1}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}^{\prime}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}\ B_{2}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}^{\prime}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\ B_{3}$
$\displaystyle T$ $\displaystyle\equiv Z^{\prime}\ A_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}^{\prime}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\ A_{1}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}^{\prime}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\ A_{2}\
{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}^{\prime}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}^{\prime}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\ A_{3}\ Z\ B_{0}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}\ B_{1}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}\ B_{2}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\ B_{3}$ Figure 4:  Reduction
of Theorem 4.3 (using $r=2$ duplicate-free equations) applied to the graph
from Figure 2.

######  Proof 4.4.

See Figure 4. Consider an instance $G=(V,E),\kappa$ of Clique. Introduce
$n+m+3$ separators (i.e., new characters) denoted $x_{0},\ldots,x_{n}$,
$y_{0},\ldots,y_{m}$ and $z$. Let $\Sigma$ consist of $V$ and the set of
separators. Introduce $2\kappa(\kappa-1)$ _coding_ blocks
$\\{X_{i,j},X_{i,j}^{\prime}\\}$ for $i\neq j$, a _starting_ block $Z$ and
$\kappa+{\kappa\choose 2}+2$ _gap_ blocks $A_{0},\ldots,A_{\kappa},B_{0}$ and
$B_{i,j}$ for $1\leq i<j\leq\kappa$. Define the following string equations (we
decompose the strings into _vertex_ and _edge_ sections for ease of
presentation):

$\displaystyle{\mathcal{E}}$
$\displaystyle:=\\{T\equiv{\mathcal{X}},T\equiv{\mathcal{X}}^{\prime}\\}$
$\displaystyle\text{ where }T$ $\displaystyle:=z\quad x_{0}\
\prod_{i=1}^{n}(v_{i}^{k-1}\ x_{i})$ $\displaystyle z\quad y_{0}\
\prod_{j=1}^{m}(e_{j}\ y_{j})$ $\displaystyle{\mathcal{X}}$ $\displaystyle:=Z\
A_{0}\ \prod_{1\leq i\leq\kappa}\prod_{j\neq i}(X_{i,j}\ A_{i,j})$
$\displaystyle Z^{\prime}\ B_{0}\ \prod_{1\leq
i<\kappa}\prod_{i<j\leq\kappa}(X^{\prime}_{i,j}X^{\prime}_{j,i}\ B_{i,j})$
$\displaystyle{\mathcal{X}}^{\prime}$ $\displaystyle:=\underbrace{Z^{\prime}\
A_{0}\ \prod_{1\leq i\leq\kappa}\prod_{j\neq i}(X^{\prime}_{i,j}\
A_{i,j})}_{\text{vertex section}}$ $\displaystyle\underbrace{Z\ B_{0}\
\prod_{1\leq i<\kappa}\prod_{i<j\leq\kappa}(X_{i,j}X_{j,i}\
B_{i,j})}_{\text{edge section}}$

This concludes the construction of the instance. We now show the correctness
of the reduction.

($\Rightarrow$) If $G$ has a $\kappa$-clique $K=\\{w_{1},\ldots
w_{\kappa}\\}$. Set $\sigma(Z)=\sigma(Z^{\prime})=z$ and
$\sigma(X_{i,j})=\sigma(X^{\prime}_{i,j})=w_{i}$ for all $j\neq i$. Then each
$\sigma(\prod_{j\neq i}X_{i,j})$ equals $x_{i}^{k-1}$, and these substrings
appear in the same order as in ${\mathcal{X}}$ in the vertex section of $T$,
and $\sigma(X^{\prime}_{i,j}X^{\prime}_{j,i})$, with $i<j$, correspond to
edges of $G$ which appear in this order in the edge section of $T$. Pick
$\sigma(A_{i})$ to be the gaps around the selected vertices and
$\sigma(B_{i,j})$ to be the gaps around selected edges. We match
${\mathcal{X}}^{\prime}$ in exactly the same way with $T$ (exchanging the
roles of $X_{i}$ and $X_{i}^{\prime}$), so that the gaps are identical in both
matchings. Thus this assignment satisfies ${\mathcal{E}}$.

($\Leftarrow$) If ${\mathcal{E}}$ has a satisfying assignment $\sigma$, First,
note that $\sigma(Z)=z$: The first block in ${\mathcal{X}}$ is $Z$, so $Z$
must start with $z$. Moreover, $z$ is followed by different characters in
${\mathcal{X}}$ and ${\mathcal{X}}^{\prime}$ ($x_{0}$ and $y_{0}$,
respectively). Similarly, $\sigma(Z^{\prime})=z$. Thus, the vertex (edge)
sections of ${\mathcal{X}}$ and ${\mathcal{X}}^{\prime}$ are matched only to
the vertex (edge) section of $T$. Hence, $\sigma(X_{i,j})$ is a substring of
both sections of $T$, which may only be single characters corresponding to
some character $w_{i,j}$. In the vertex section, characters $\sigma(X_{i,j})$
for $j\neq i$ appear consecutively in $T$,so all vertices $w_{i,j}$ are equal
(and denoted $w_{i}$, $1\leq i\leq\kappa$). In the edge section, each string
$\sigma(X_{i,j}X_{j,i})=w_{i}w_{j}$ for $1\leq i<j\leq k$ is a substring of
$T$ so it is an edge of $G$, i.e. $\\{w_{1},\ldots,w_{\kappa}\\}$ is a clique
in $G$.

Building on the result above, we prove that String Equations is W[1]-hard even
if blocks are allowed to be assigned empty strings (in this case, we need two
distinct target strings: having a single target would have trivial solutions
by assigning empty strings to all but one blocks).

######  Theorem 4.5.

String Equations allowing empty blocks with $r=2$ duplicate-free equations and
parameter $c$ is W[1]-hard.

######  Proof 4.6.

See Figure 5. We build on the proof of Theorem 4.3, and create a similar
instance of String Equations with more separating gadgets, mainly to enforce
that strings $\sigma(Z)$ and $\sigma(X_{i,j})$ may not be empty. We start from
$T,{\mathcal{X}},{\mathcal{X}}^{\prime}$ as defined in the previous proof. We
introduce characters $\gamma$, $\phi_{1}$, and $\phi_{2}$, as well as blocks
$\Gamma_{0},\Gamma_{0}^{\prime},\Gamma_{h,i},\Gamma^{\prime}_{h,i}$ (with
$h\in\\{0,1\\}$ and $1\leq i\leq\kappa$), $\Phi_{1}$ and $\Phi_{2}$.

We build the new equation system ${\mathcal{E}}$ as follows (differences to
the construction in the proof of Theorem 4.3 are highlighted):

$\displaystyle{\mathcal{E}}$
$\displaystyle:=\\{T\equiv{\mathcal{X}},\bm{T^{\prime}}\equiv{\mathcal{X}}^{\prime}\\},\text{
where: }$ $\displaystyle T$ $\displaystyle:=\bm{\gamma^{2\kappa+1}\
\phi_{1}\phi_{2}}\quad z\ \bm{\gamma}\ x_{0}\ \prod_{i=1}^{n}(\bm{\gamma}\
v_{i}^{k-1}\ \bm{\gamma}\ x_{i})\quad z\quad y_{0}\ \prod_{j=1}^{m}(e_{j}\
y_{j})$ $\displaystyle T^{\prime}$ $\displaystyle:=\bm{\gamma^{2\kappa+1}\
\phi_{2}\phi_{1}}\quad z\ \bm{\gamma}\ x_{0}\ \prod_{i=1}^{n}(\bm{\gamma}\
v_{i}^{k-1}\ \bm{\gamma}\ x_{i})\quad z\quad y_{0}\ \prod_{j=1}^{m}(e_{j}\
y_{j})$ $\displaystyle{\mathcal{X}}$
$\displaystyle:=\bm{\Gamma_{0}\prod_{i=1}^{\kappa}\Gamma_{0,i}\Gamma_{1,i}\Phi_{1}\Phi_{2}}\quad
Z\ \bm{\Gamma_{0}^{\prime}}\ A_{0}\
\prod_{i=1}^{\kappa}\big{(}\bm{\Gamma_{0,i}^{\prime}}\ \prod_{j\neq
i}(X_{i,j}\bm{\Gamma_{1,i}^{\prime}}\ A_{i,j})\big{)}$
$\displaystyle\mathllap{Z^{\prime}\ B_{0}\ \prod_{1\leq
i<\kappa}\prod_{i<j\leq\kappa}(X^{\prime}_{i,j}X^{\prime}_{j,i}\ B_{i,j})}$
$\displaystyle{\mathcal{X}}^{\prime}$
$\displaystyle:=\underbrace{\bm{\Gamma^{\prime}_{0}\prod_{i=1}^{\kappa}\Gamma^{\prime}_{0,i}\Gamma^{\prime}_{1,i}\Phi_{2}\Phi_{1}}}_{\text{prefix
section}}\quad Z^{\prime}\ \bm{\Gamma_{0}}\ A_{0}\
\prod_{i=1}^{\kappa}\big{(}\bm{\Gamma_{0,i}}\prod_{j\neq i}(X^{\prime}_{i,j}\
\bm{\Gamma_{1,i}}\ A_{i,j})\big{)}$ $\displaystyle\mathllap{Z\ B_{0}\
\prod_{1\leq i<\kappa}\prod_{i<j\leq\kappa}(X_{i,j}X_{j,i}\ B_{i,j})}$

$\displaystyle T$
$\displaystyle=\gamma\gamma\gamma\gamma\gamma\gamma\gamma\phi_{1}\phi_{2}z\gamma\
x_{0}\
\gamma{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\gamma\ x_{1}\ \gamma bb\gamma\
x_{2}\
\gamma{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\gamma\ x_{3}\
\gamma{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\gamma\ x_{4}\ldots$ $\displaystyle
T^{\prime}$
$\displaystyle=\gamma\gamma\gamma\gamma\gamma\gamma\gamma\phi_{2}\phi_{1}z\gamma\
x_{0}\
\gamma{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\gamma\ x_{1}\ \gamma bb\gamma\
x_{2}\
\gamma{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\gamma\ x_{3}\
\gamma{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\gamma\ x_{4}\ldots$ $\displaystyle
T$
$\displaystyle\equiv\Gamma_{0}\Gamma_{0,1}\ldots\Gamma_{1,3}\Phi_{1}\Phi_{2}\
Z\ \Gamma^{\prime}_{0}A_{0}\
\Gamma^{\prime}_{0,1}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\Gamma^{\prime}_{1,1}\ A_{1}\
\Gamma^{\prime}_{0,2}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\Gamma^{\prime}_{1,2}\ A_{2}\
\Gamma^{\prime}_{0,3}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\Gamma^{\prime}_{1,3}\
A_{3}\ldots$ $\displaystyle T$
$\displaystyle\equiv\Gamma^{\prime}_{0}\Gamma^{\prime}_{0,1}\ldots\Gamma^{\prime}_{1,3}\Phi_{2}\Phi_{1}\
Z^{\prime}\ \Gamma_{0}A_{0}\
\Gamma_{0,1}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}^{\prime}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\Gamma_{1,1}\ A_{1}\
\Gamma_{0,2}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}^{\prime}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}^{\prime}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\Gamma_{1,2}\ A_{2}\
\Gamma_{0,3}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}^{\prime}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}^{\prime}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}\Gamma_{1,3}\
A_{3}\ldots$ Figure 5:  Prefix and vertex sections in the reduction of Theorem
4.5 (with $r=2$ equations and empty blocks) applied to the graph from Figure 2

This concludes the construction of the instance. We now show the correctness
of the reduction.

($\Rightarrow$) Assume that $G$ has a $\kappa$-clique. We set
$\gamma=\sigma(\Gamma_{0})=\sigma(\Gamma_{0}^{\prime})=\sigma(\Gamma_{h,i})=\sigma(\Gamma_{h,i}^{\prime})$
for $h\in\\{0,1\\}$ and $1\leq i\leq\kappa$. We set
$\phi_{i}=\sigma(\Phi_{i})$, $i\in\\{1,2\\}$, and keep the assignments to
other blocks from Theorem 4.3 (inserting character $\gamma$ within separators
$G_{i,j}$ and $G^{\prime}_{i,j}$ since only those around blocks $X_{i,j}$ are
covered by $\Gamma_{h,i}$ and $\Gamma^{\prime}_{h,i}$). The new prefix section
is correctly covered by these new blocks, as are the occurrences of $\gamma$
in the vertex sections (those around selected vertices are covered by
$\Gamma_{h,i}$ and $\Gamma^{\prime}_{h,i}$, others are inserted in separators
$G_{i,j}$ and $G^{\prime}_{i,j}$).

($\Leftarrow$) If ${\mathcal{E}}$ has an assignment, possibly with empty
blocks, we focus on proving that blocks $Z$ and $X_{i,j}$ are not empty. First
consider characters $\phi_{i}$: they must each be in their own block ($T$ and
$T^{\prime}$ have no other common substring containing these). Write $A$ and
$B$ respectively for the blocks assigned $\phi_{1}$ and $\phi_{2}$, then $AB$
is a substring of ${\mathcal{X}}$ and $BA$ is a substring of
${\mathcal{X}}^{\prime}$. It can be verified that $\Phi_{1}$, $\Phi_{2}$ are
the only blocks satisfying this property, so $\sigma(\Phi_{i})=\phi_{i}$ for
$i=1,2$. Thus, from the prefix section of $T$ and ${\mathcal{X}}$, we have
$\sigma(\Gamma_{0}\prod_{i=1}^{\kappa}(\Gamma_{0,i}\Gamma_{1,i}))=\gamma^{2\kappa+1}$,
so each $\sigma(\Gamma_{0})$, $\sigma(\Gamma_{h,i})$ only contains characters
$\gamma$, and may not contain more than one (since there is no $\gamma\gamma$
outside the vertex section, where the corresponding block is matched in
$T^{\prime}\equiv{\mathcal{X}}^{\prime}$), so it must contain exactly
$\gamma$. Similarly,
$\sigma(\Gamma^{\prime}_{0})=\sigma(\Gamma^{\prime}_{h,i})=\gamma$. It follows
that $\sigma(Z)$ is not empty and starts with $z$, which gives the separation
into vertex and edge sections as in the proof of Theorem 4.3. For each $i$,
string $\sigma(\prod_{j\neq i}X_{i,j})$ only contains characters from vertex
and edge sections (so only of the form $v_{i^{\prime}}$, not $\gamma$ or
separators), and $T$ contains $\gamma\sigma(\prod_{j\neq i}X_{i,j})\gamma$ as
a substring, so again $X_{i,j}=w_{i}$ for some $i$ and every $j\neq i$.
Finally, $w_{i}w_{j}$ must be an edge of $G$ for each $i$ and $j$, so
$\\{w_{1},\ldots,w_{\kappa}\\}$ forms a clique of $G$.

We note that the above reduction requires two distinct target strings
(otherwise, allowing empty blocks leads to trivial solutions where a single
block is non-empty). However, the two strings differ by a single character
inversion, that force each and every other block to be non-empty.

##  5 Constant Equation Sizes

We now consider the special case where the right hand side of each equation in
the system has only a constant number of blocks. In other words, the case when
$c$ is constant. We show that the case where $c=2$ can be solved in polynomial
time. In fact, we show that a more general case is polynomial-time solvable.
To describe this special case, we introduce the following notation.

A block $X_{p}$ is a _border block_ of an equation if it appears as first or
as last block in the right hand side of that equation. A block is a border
block of a system of equations ${\mathcal{E}}$ if it is a border block of at
least one equation of ${\mathcal{E}}$. We say that ${\mathcal{E}}$ has _only
border blocks_ if non-border blocks are all jokers. In particular, in such a
setting, a border block of ${\mathcal{E}}$ is a border block of any equation
in which it occurs (otherwise, it would both appear twice and be a joker: a
contradiction).

######  Proposition 5.1.

String Equations with only border blocks is polynomial-time solvable. In
particular, String Equations with equation size $c=2$ can be solved in
polynomial time.

######  Proof 5.2.

Consider an equation $T_{i}\equiv{\mathcal{X}}_{i}$. We say that the string
$T_{i}$ _starts_ with block $X_{p}$ if ${\mathcal{X}}_{i}[1]=X_{p}$.
Similarly, $T_{i}$ _ends_ with $X_{p}$ if
${\mathcal{X}}_{i}[|{\mathcal{X}}_{i}|]=X_{p}$). Some length
$\ell\in\mathds{N}$ is _valid_ for block $X_{p}$ if the length-$\ell$ prefixes
of all strings starting with $X_{p}$ and the length-$\ell$ suffixes of all
strings ending with $X_{p}$ are equal (then we denote this common substring
$\sigma_{\ell}(X_{p})$).

We let $\\{X_{1},\ldots,X_{k^{\prime}}\\}\subseteq{\mathcal{B}}$ denote the
border blocks of the instance. Recall that, since the instance has only border
blocks, all other blocks are jokers, and border blocks are border blocks in
every equation that contains them. Build a 2SAT formula as follows. For each
border block $X_{p}$ and each integer $0\leq\ell\leq t$, introduce a boolean
variable denoted $X_{p}\preceq\ell$ (which corresponds to assigning a string
with length at most $\ell$ to $X_{p}$, its negation is denoted
$X_{p}\succ\ell$). Create formula $\Phi_{\mathcal{E}}$ using the following 1-
and 2-clauses.

  1. 1.

For each $X_{p}$, add clause $X_{p}\succ 0$.

  2. 2.

For each $X_{p}$ and $0\leq\ell<\ell^{\prime}\leq n$, add clause
$X_{p}\preceq\ell\rightarrow X_{p}\preceq\ell^{\prime}$.

  3. 3.

For each $X_{p}$ and $1\leq\ell\leq n$. If $\ell$ is not a valid length for
$X_{p}$, add clause $X_{p}\preceq\ell\rightarrow X_{p}\preceq\ell-1$.

  4. 4.

For each equation $T_{i}\equiv{\mathcal{X}}_{i}$ where
${\mathcal{X}}_{i}=X_{p}$, add clause $X_{p}\succ|T_{i}|-1$.

  5. 5.

For each equation $T_{i}\equiv{\mathcal{X}}_{i}$ where
${\mathcal{X}}_{i}=X_{p}X_{q}$, and $0\leq\ell\leq|T_{i}|$, add clause
$X_{p}\preceq\ell\rightarrow X_{q}\succ|T_{i}|-1-\ell$.

  6. 6.

For each equation $T_{i}\equiv{\mathcal{X}}_{i}$ where ${\mathcal{X}}_{i}$
starts with $X_{p}$ and ends with $X_{q}$, for each $0\leq\ell\leq|T_{i}|$,
add clause $X_{p}\succ\ell\rightarrow
X_{q}\preceq|T_{i}|-|{\mathcal{X}}_{i}|-\ell+1$.

We then prove the following claim, which completes the proof that
${\mathcal{E}}$ can be solved in polynomial time:

${\mathcal{E}}\text{ admits a satisfying
assignment}\Leftrightarrow\Phi_{\mathcal{E}}\text{ is satisfiable.}$

($\Rightarrow$) Consider a satisfying assignment $\sigma$ of ${\mathcal{E}}$,
let $\ell_{p}$ be the length of $\sigma(X_{p})$, and set all variables
$X_{p}\preceq\ell$ to true iff $\ell\geq\ell_{p}$. We now verify each clause
(each time we use the notations from the clause definition, and for clauses of
the form $A\rightarrow B$, we assume that $A$ is true and directly prove $B$).

  1. 1.

$\ell_{p}>0$ so $X_{p}\succ 0$.

  2. 2.

We have $\ell_{p}\leq\ell$ and $\ell<\ell^{\prime}$ so
$\ell_{p}\leq\ell^{\prime}$.

  3. 3.

$\ell_{p}$ is a valid length, so $\ell\neq\ell_{p}$, if $X_{p}\preceq\ell$,
then $\ell_{p}<\ell$ and $X_{p}\preceq\ell-1$.

  4. 4.

We have $|T_{i}|=|\sigma({\mathcal{X}}_{i})|=\ell_{p}$, so
$\ell_{p}>|T_{i}-1|$ and $X_{p}\succ|T_{i}|-1$.

  5. 5.

We have $|T_{i}|=|\sigma({\mathcal{X}}_{i})|=\ell_{p}+\ell_{q}$, and
$\ell\geq\ell_{p}$ so $\ell_{q}\geq|T_{i}|-\ell$ and
$X_{q}\succ|T_{i}|-1-\ell$.

  6. 6.

We have $T_{i}=\sigma({\mathcal{X}}_{i})$, so
$|T_{i}|\geq\ell_{p}+\ell_{q}+|{\mathcal{X}}_{i}|-2$ (blocks of
${\mathcal{X}}_{i}$ have length at most 1, except the first and last that have
length $\ell_{p}$ and $\ell_{q}$). If $X_{p}\succ\ell$, then $\ell<\ell_{p}$,
and
$\ell_{q}\leq|T_{i}|-\ell_{p}-|{\mathcal{X}}_{i}|+2\leq|T_{i}|-\ell-|{\mathcal{X}}_{i}|+1$.

($\Leftarrow$) For each $p$, let $\ell_{p}$ be the smallest value of $\ell$
such that $X_{p}\leq\ell$ is true. In particular, $\ell_{p}>0$ (since
$X_{p}\preceq 0$ is false, Clause 1), and $\ell_{p}$ is a valid length for
$X_{p}$ (Clause 3: otherwise, we would also have $X_{p}\preceq\ell_{p}-1$ set
to true). Set $\sigma(X_{p})=\sigma_{\ell_{p}}(X_{p})$. Consider an equation
$T_{i}\equiv{\mathcal{X}}_{i}$. By Clause 3, if ${\mathcal{X}}_{i}$ starts
with $X_{p}$ and ends with $X_{q}$, then $\sigma(X_{p})$ is a prefix of
$T_{i}$ and $\sigma(X_{q})$ is a suffix of $T_{i}$. In particular,
$\ell_{p},\ell_{q}\leq|T_{i}|$. If $|{\mathcal{X}}_{i}|=1$
(${\mathcal{X}}_{i}=X_{p}$), then by Clause 4, $\ell_{p}=|T_{i}|$, so
$\sigma(X_{p})=T_{i}$. If ${\mathcal{X}}_{i}=X_{p}X_{q}$, then by Clauses 6
and 5 $\ell_{p}+\ell_{q}=|T_{i}|$, so $\sigma(X_{p}X_{q})=T_{i}$. Otherwise
(${\mathcal{X}}_{i}$ contains $|{\mathcal{X}}_{i}|-2\geq 1$ joker blocks), we
have $\ell_{p}+\ell_{q}+|{\mathcal{X}}_{i}|-2\leq|T_{i}|$ (indeed,
$X_{p}\succ\ell_{p}-1$, so
$X_{q}\preceq|T_{i}|-|{\mathcal{X}}_{i}|-(\ell_{p}-1)+1$ by Clause 6, hence
$\ell_{q}\leq|T_{i}|-|{\mathcal{X}}_{i}|-\ell_{p}+2$, which gives the result).

######  Theorem 5.3.

String Equations with duplicate-free equations of size $c=3$ and parameter $r$
is W[1]-hard.

######  Proof 5.4.

$\displaystyle T_{1,r}$ $\displaystyle:=x\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}b\ x$ $\displaystyle T_{1,g}$
$\displaystyle:=x\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\ x$ $\displaystyle T_{1,b}$
$\displaystyle:=x\
{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ x$ $\displaystyle T_{1,r}$
$\displaystyle\equiv{*}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R$}}\cr\rule[-5.5pt]{11.00348pt}{1.5pt}}}}\ {*}$ $\displaystyle T_{1,g}$
$\displaystyle\equiv{*}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\ {*}$ $\displaystyle T_{1,b}$
$\displaystyle\equiv{*}\
{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\ {*}$ $\displaystyle T_{2}$
$\displaystyle:=\mathrlap{y\ a\,c\ y\ a\,d\ y\ b\,c\ y\ b\,d\ y\ c\,d\ y}$
$\displaystyle T_{2}$ $\displaystyle\equiv{*}\ E_{rg}\ {*}$ $\displaystyle
T_{2}$ $\displaystyle\equiv{*}\ E_{rb}\ {*}$ $\displaystyle T_{2}$
$\displaystyle\equiv{*}\ E_{gb}\ {*}$ $\displaystyle T_{3}$
$\displaystyle:=\mathrlap{z\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\ z\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$a$}}\cr\rule[-5.5pt]{8.61922pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ z\ b\,c\ z\ b\,d\ z\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c$}}\cr\rule[-5.5pt]{7.66089pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ z}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{rg}\ E_{rg}\ B_{rg}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{rb}\ E_{rb}\ B_{rb}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{gb}\ E_{gb}\ B_{gb}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{rg}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R$}}\cr\rule[-5.5pt]{11.00348pt}{1.5pt}}}}\quad{*}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{rb}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R$}}\cr\rule[-5.5pt]{11.00348pt}{1.5pt}}}}\quad{*}$ $\displaystyle T_{3}$
$\displaystyle\equiv A_{gb}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\quad{*}$ $\displaystyle T_{3}$
$\displaystyle\equiv\quad{*}\quad{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G$}}\cr\rule[-5.5pt]{11.19582pt}{1.5pt}}}}\ B_{rg}$ $\displaystyle T_{3}$
$\displaystyle\equiv\quad{*}\quad{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\ B_{rb}$ $\displaystyle T_{3}$
$\displaystyle\equiv\quad{*}\quad{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B$}}\cr\rule[-5.5pt]{11.42014pt}{1.5pt}}}}\ B_{gb}$ Figure 6:  Reduction of
Theorem 5.3 (using equations of size $c=3$) applied to the graph from Figure
2.

See Figure 6. Consider an instance $(G=(V,E),\kappa)$ of Multi-Colored Clique.
Introduce three separators denoted $x,y,z$, let $\Sigma=V\cup\\{x,y,z\\}$.
Introduce $\kappa+3{\kappa\choose 2}$ non-joker blocks $\\{X_{i}\mid 1\leq
i\leq\kappa\\}$ and $\\{E_{i,j},A_{i,j},B_{i,j}\mid 1\leq i<j\leq\kappa\\}$,
and $2\kappa+4{\kappa\choose 2}$ joker blocs (for a total of
$k={\mathcal{O}}(\kappa^{2})$ blocks). The equation system is defined as
follows.

$\displaystyle{\mathcal{E}}$
$\displaystyle:=\\{T_{1,i}\equiv{\mathcal{X}}_{1,i}\mid 1\leq i\leq\kappa\\}$
$\displaystyle\cup\\{T_{2}\equiv{\mathcal{X}}_{2,i,j}\mid 1\leq
i<j\leq\kappa\\}$
$\displaystyle\cup\\{T_{3}\equiv{\mathcal{X}}_{3,i,j},T_{3}\equiv{\mathcal{X}}_{4,i,j},T_{3}\equiv{\mathcal{X}}_{5,i,j}\mid
1\leq i<j\leq\kappa\\}$ $\displaystyle T_{1,i}$
$\displaystyle:=x\prod_{v_{j}\in V_{i}}(v_{i}y)$
$\displaystyle{\mathcal{X}}_{1,i}$ $\displaystyle:={*}\ \ X_{i}\ \ {*}$
$\displaystyle T_{2}$ $\displaystyle:=y\prod_{j=1}^{m}(e_{j}y)$
$\displaystyle{\mathcal{X}}_{2,i,j}$ $\displaystyle:={*}\ \ E_{i,j}\ \ {*}$
$\displaystyle{\mathcal{X}}_{3,i,j}$ $\displaystyle:=A_{i,j}E_{i,j}B_{i,j}$
$\displaystyle T_{3}$ $\displaystyle:=\smash{z\prod_{j=1}^{m}(e_{j}z)}$
$\displaystyle{\mathcal{X}}_{4,i,j}$ $\displaystyle:=A_{i,j}X_{i}\quad{*}$
$\displaystyle{\mathcal{X}}_{5,i,j}$ $\displaystyle:=\quad{*}\quad
X_{j}B_{i,j}$

If $G$ contains a clique, let $\sigma(X_{i})$ and $\sigma(E_{i,j})$ correspond
respectively to the selected vertex in component $i$ and to the selected edge
between components $i$ and $j$. In particular, $\sigma(X_{i})$ appears in
$T_{1,i}$ and $\sigma(E_{i,j})$ appears in $T_{2}$ and $T_{3}$ (using
${\mathcal{X}}_{3,i,j}$, $\sigma(A_{i,j}E_{i,j})$ is a prefix of $T_{3}$ and
$\sigma(E_{i,j}B_{i,j})$ is a suffix of $T_{3}$). Moreover,
$\sigma(E_{i,j)=\sigma(X_{i}X_{j}}$, so $\sigma(A_{i,j}X_{i})$ is a prefix of
$T_{3}$ and $\sigma(X_{j}B_{i,j})$ is a suffix of $T_{3}$, satisfying
equations for ${\mathcal{X}}_{4,i,j}$ an ${\mathcal{X}}_{5,i,j}$, and $\sigma$
is a satisfying assignment of ${\mathcal{E}}$.

Assume now that ${\mathcal{E}}$ admits a satisfying assignment $\sigma$. Note
that $\sigma(X_{i})$ is a common substring of $T_{1}$ and $T_{3}$, so it has
length 1 and does not contain any separator (there are no common separators in
$T_{1}$ and $T_{3}$ and no length-2 substring of $T_{3}i$ uses two vertices
from the same subset $V_{i}$). Let $v_{i}=\sigma(X_{i})$. Similarly
$\sigma(E_{i,j})$ does not contain any separator and has length at most 2
(note that if it has length 2, then it is an edge of $G$). Using
${\mathcal{X}}_{3,i,j}$ and ${\mathcal{X}}_{4,i,j}$, $\sigma(E_{i,j})$ and
$\sigma(X_{i})$ must start with the same character, $v_{i}$. Similarly,
$\sigma(E_{i,j})$ and $\sigma(X_{j})$ must end with the same character
$v_{j}$. Since$v_{i}\in V_{i}$, $v_{j}\in V_{j}$ and $V_{i},V_{j}$ are
disjoint for $i\neq j$, we have $\sigma(E_{i,j})=v_{i}v_{j}$, i.e. there exist
an edge $\\{v_{i},v_{j}\\}$ in $G$, and $\\{v_{1},\ldots,v_{\kappa}\\}$ form a
clique of $G$.

######  Theorem 5.5.

String Equations with $r-1$ size-$2$ equations and one size-$c$ duplicate-free
equation is W[1]-hard for parameter $r+c$.

######  Proof 5.6.

$\displaystyle T_{v}$
$\displaystyle:={\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
${\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$x$}}\cr\rule[-5.5pt]{9.0486pt}{1.5pt}}}}\,\
a\,b$}}\cr\rule[-7.5pt]{30.29272pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$c\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}$}}\cr\rule[-7.5pt]{17.8657pt}{1.5pt}}}}$
$\displaystyle T_{v}$ $\displaystyle\equiv R\,R^{\prime}$ $\displaystyle
T_{v}$ $\displaystyle\equiv{G}\,{G^{\prime}}$ $\displaystyle T_{v}$
$\displaystyle\equiv B\,{B^{\prime}}$ $\displaystyle T_{v}$
$\displaystyle\equiv{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,R^{\prime}$ $\displaystyle
T_{v}$
$\displaystyle\equiv{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\,{G^{\prime}}$ $\displaystyle
T_{v}$ $\displaystyle\equiv
B\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{r}^{\prime}$}}\cr\rule[-5.5pt]{14.10217pt}{1.5pt}}}}$ $\displaystyle
T_{v}$
$\displaystyle\equiv{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\,R^{\prime}$ $\displaystyle
T_{v}$
$\displaystyle\equiv{G}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{r}^{\prime}$}}\cr\rule[-5.5pt]{13.87785pt}{1.5pt}}}}$ $\displaystyle
T_{v}$ $\displaystyle\equiv
B\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B_{g}^{\prime}$}}\cr\rule[-5.5pt]{14.29207pt}{1.5pt}}}}$ $\displaystyle
T_{l}$ $\displaystyle:=\mathrlap{y\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$x$}}\cr\rule[-5.5pt]{9.0486pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$cd$}}\cr\rule[-5.5pt]{12.86575pt}{1.5pt}}}}\ y\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$x$}}\cr\rule[-5.5pt]{9.0486pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y\ xacd\ y\ xad\ y\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$xab$}}\cr\rule[-5.5pt]{18.62614pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$d$}}\cr\rule[-5.5pt]{8.5382pt}{1.5pt}}}}\ y}$ $\displaystyle T_{l}$
$\displaystyle\equiv\mathrlap{{*}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{g}$}}\cr\rule[-5.5pt]{13.87541pt}{1.5pt}}}}\,{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G^{\prime}_{r}$}}\cr\rule[-5.5pt]{12.73581pt}{1.5pt}}}}\ {*}\
{\color[rgb]{1,0.2,0.2}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.2,0.2}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$R_{b}$}}\cr\rule[-5.5pt]{13.40681pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B^{\prime}_{r}$}}\cr\rule[-5.5pt]{12.96013pt}{1.5pt}}}}\ {*}\
{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$G_{b}$}}\cr\rule[-5.5pt]{13.59915pt}{1.5pt}}}}\,{\color[rgb]{0,0,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.3}{\ooalign{\hbox{\set@color{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
$B^{\prime}_{g}$}}\cr\rule[-5.5pt]{12.96013pt}{1.5pt}}}}\ {*}}$ Figure 7:
Reduction of Theorem 5.5 (using $r-1$ size-2 equations and one size-$c$
duplicate-free equation) applied to the graph from Figure 2.

See Figure 7. Consider an instance $(G=(V,E),\kappa)$ of Clique. Introduce
additional characters $x$ and $y$, and let $\Sigma=V\cup\\{x,y\\}$. Given a
vertex $v_{i}\in V$, define the (non-empty) strings $\text{\sf
pre}(v_{i}):=x\prod_{i^{\prime}=1}^{i-1}v_{i^{\prime}}$ and $\text{\sf
suf}(v_{i}):=\prod_{i^{\prime}=i}^{n}v_{i^{\prime}}$. We first prove the
following property on these functions:

######  Claim 1.

If $v_{i},v_{j},v_{i^{\prime}},v_{j^{\prime}}$ are vertices with $i<j$ and
$\text{\sf pre}(v_{i})\text{\sf suf}(v_{j})=\text{\sf
pre}(v_{i^{\prime}})\text{\sf suf}(v_{j^{\prime}})$, then $i=i^{\prime}$ and
$j=j^{\prime}$.

######  Proof 5.7.

Character $v_{i}$ does not appear in $\text{\sf pre}(v_{i})\text{\sf
suf}(v_{j})$, so $i^{\prime}\leq i<j^{\prime}$. Furthermore, $v_{i-1}$ (or $x$
if $i=0$) appears in $\text{\sf pre}(v_{i})\text{\sf suf}(v_{j})$ but may not
appear in $\text{\sf suf}(v_{j^{\prime}})$, so it appears in $\text{\sf
pre}(v_{i^{\prime}})$ and $i=i^{\prime}$. Removing the common prefix yields
$\text{\sf suf}(v_{j})=\text{\sf suf}(v_{j^{\prime}})$, and $j=j^{\prime}$.

Introduce $2\kappa+2{\kappa\choose 2}$ non-joker blocks $\\{X_{i}\mid 1\leq
i\leq\kappa\\}$ and $\\{X_{i,j},X^{\prime}_{j,i}\mid 1\leq i<j\leq\kappa\\}$,
and ${\kappa\choose 2}+1$ joker blocs (for a total of
$k={\mathcal{O}}(\kappa^{2})$ blocks). The equation system is defined as
follows.

$\displaystyle{\mathcal{E}}$
$\displaystyle\mathrlap{:=\\{T_{v}\equiv{\mathcal{X}}_{i}\mid 1\leq
i\leq\kappa\\}}$ $\displaystyle\mathrlap{\cup\
\\{T_{v}\equiv{\mathcal{X}}_{1,i,j},T_{v}\equiv{\mathcal{X}}_{2,i,j}\mid 1\leq
i<j\leq\kappa\\}}$ $\displaystyle\mathrlap{\cup\
\\{T_{e}\equiv{\mathcal{X}}_{e}\\},\text{ where: }}$ $\displaystyle T_{v}$
$\displaystyle:=x\ \prod_{i=1}^{n}v_{i}$ $\displaystyle T_{e}$
$\displaystyle:=y\ \prod_{uv\in E}(\text{\sf pre}(u)\text{\sf suf}(v)\ y)$
$\displaystyle{\mathcal{X}}_{i}$ $\displaystyle:=X_{i}\ \ \ X_{i}^{\prime}$
$\displaystyle{\mathcal{X}}_{e}$ $\displaystyle:=\smash{{*}\ \prod_{1\leq
i<j\leq\kappa}(X_{i,j}X^{\prime}_{j,i}}\ {*})$
$\displaystyle{\mathcal{X}}_{1,i,j}$ $\displaystyle:=X_{i,j}\ X_{i}^{\prime}$
$\displaystyle{\mathcal{X}}_{2,i,j}$ $\displaystyle:=X_{j}\ X^{\prime}_{j,i}$

If $G$ contains a clique $K=\\{w_{1},\ldots,w_{\kappa}\\}$, let
$\sigma(X_{i}):=\text{\sf pre}(w_{i})$ and $\sigma(X_{i}^{\prime}):=\text{\sf
suf}(w_{i})$. For each $i<j$, let $\sigma(X_{i,j})=X_{i}$ and
$\sigma(X^{\prime}_{i,j})=X_{j}^{\prime}$. Since, for each $w_{i}$, we have
$T_{v}=\text{\sf pre}(w_{i})\text{\sf suf}(w_{i})$, the equations
$T_{v}\equiv{\mathcal{X}}_{i}$, $T_{v}\equiv{\mathcal{X}}_{1,i,j}$ and
$T_{v}\equiv{\mathcal{X}}_{2,i,j}$ are satisfied. Furthermore, since $K$ is a
clique, for any $i<j$ we have $\sigma(X_{i,j}X^{\prime}_{j,i})=\text{\sf
pre}(u)\text{\sf suf}(v)$ for some edge $uv$ of $G$, so strings
$\sigma(X_{i,j}X^{\prime}_{j,i})$ are indeed substrings of $T_{e}$, in the
same order as in ${\mathcal{X}}_{e}$, so $T_{e}\equiv{\mathcal{X}}_{e}$ is
satisfied as well.

Assume now that ${\mathcal{E}}$ admits a satisfying assignment $\sigma$. Note
that by $T_{s}\equiv{\mathcal{X}}_{i}$, $\sigma(X_{i})=\text{\sf pre}(w_{i})$
and $\sigma(X^{\prime}_{i})=\text{\sf suf}(w_{i})$ for some vertex $w_{i}\in
V$. Using other equations with $T_{s}$, we get $\sigma(X_{i,j})=\sigma(X_{i})$
and $\sigma(X^{\prime}_{j,i})=\sigma(X^{\prime}_{j})$ for each $i<j$. For each
$i<j$, write $E_{i,j}=\sigma(X_{i,j}X^{\prime}_{j,i})$. Then $E_{i,j}$ is a
substring of $T_{e}$ starting with $x$, ending with $v_{n}$, and not
containing any occurrence of $y$, so $E_{i,j}=\text{\sf pre}(u)\text{\sf
suf}(v)$ for some edge $uv$ of $G$. By Claim 1, since $E_{i,j}=\text{\sf
pre}(w_{i})\text{\sf suf}(w_{j})$, we have $u=w_{i}$ and $v=w_{j}$, so
$w_{i}w_{j}$ is an edge for each $i<j$: $\\{w_{1},\ldots,w_{\kappa}\\}$ is a
clique of $G$.

##  6 Open Questions

We identified and focused on parameters $k$, $r$, $c$ and $d$ for our
multivariate study of the String Equations and String Equations with Deletions
problems. Two questions remain open, both in the deletions setting. Can the
XP-algorithm for String Equations with Deletions parameterized by $k+d$
(Proposition 3.3) be improved to an algorithm with running time $f(d)\cdot
t^{f(k)}$, that is, to an FPT-algorithm for $d$ when $k$ is constant?
Similarly, is there an $f(d)t^{{\mathcal{O}}(1)}$-time algorithm for String
Equations with Deletions with size-2 equations (or, even better, equations
with only border blocks of arbitrary size)?

We reserve the study of other parameters for future works: possible candidates
could be the alphabet size $|\Sigma|$, the size of the target string $t$, or
the maximum length of a string assigned to a block $|\sigma(X_{i})|$. However,
most combinations bring hardness for the related String Morphism problem [8].

Finally, another variant would allow undefined characters (question marks) in
the target strings. Does this introduce an additional difficulty, and can our
algorithms be extended to this setting?

## References

  * [1] Dana Angluin.  Finding patterns common to a set of strings.  In Proceedings of the eleventh annual ACM Symposium on Theory of Computing, pages 130–141, 1979.
  * [2] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Harold T. Wareham.  The parameterized complexity of sequence alignment and consensus.  Theor. Comput. Sci., 147(1&2):31–54, 1995.
  * [3] Laurent Bulteau and Christian Komusiewicz.  Minimum common string partition parameterized by partition size is fixed-parameter tractable.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 102–121. SIAM, 2014.
  * [4] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [5] Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette.  On the parameterized complexity of multiple-interval graph problems.  Theor. Comput. Sci., 410(1):53–61, 2009.
  * [6] Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid.  Pattern matching with variables: Efficient algorithms and complexity results.  ACM Trans. Comput. Theory, 12(1):6:1–6:37, 2020.
  * [7] Henning Fernau and Markus L. Schmid.  Pattern matching with variables: A multivariate complexity analysis.  Inf. Comput., 242:287–305, 2015.
  * [8] Henning Fernau, Markus L. Schmid, and Yngve Villanger.  On the parameterised complexity of string morphism problems.  Theory Comput. Syst., 59(1):24–51, 2016.
  * [9] Oscar H. Ibarra, Ting-Chuen Pong, and Stephen M. Sohn.  A note on parsing pattern languages.  Pattern Recognition Letters, 16(2):179–182, 1995.  URL: https://www.sciencedirect.com/science/article/pii/016786559400091G, doi:https://doi.org/10.1016/0167-8655(94)00091-G.
  * [10] Krzysztof Pietrzak.  On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems.  J. Comput. Syst. Sci., 67(4):757–771, 2003.