Laurent Bulteau
email: laurent.bulteau@u-pem.fr

Vincent Froese
email: vincent.froese@tu-berlin.de

AND Rolf Niedermeier
email: rolf.niedermeier@tu-berlin.de

Tight Hardness Results for Consensus Problems on

Keywords: Circular String Alignment, Time Series Averaging, Dynamic Time Warping, Fine-Grained Complexity and Reductions, Lower Bounds, Parameterized Complexity, Exponential Time Hypothesis AMS subject classifications. 68Q17, 68T10, 92D20

published or not. The documents may come   L'archive ouverte pluridisciplinaire

1. Introduction. Consensus problems appear in many contexts of stringology and time series analysis, including applications in bioinformatics, data mining, machine learning, and speech recognition. Roughly speaking, given a set of input sequences, the goal is to find a consensus sequence that minimizes the "distance" (according to some specified distance measure) to the input sequences. Classic problems in this context are the NP-hard Closest String [START_REF] Frances | On covering problems of codes[END_REF][START_REF] Li | On the closest string and substring problems[END_REF][START_REF] Li | Finding similar regions in many sequences[END_REF][START_REF] Gramm | Fixed-parameter algorithms for Closest String and related problems[END_REF] (where the goal is to find a "closest string" that minimizes the maximum Hamming distance to a set of equal-length strings) or the more general Closest Substring [START_REF] Fellows | On the parameterized intractability of motif search problems[END_REF][START_REF] Marx | Closest substring problems with small distances[END_REF]. Notably, the variant of Closest String where one minimizes the sum of Hamming distances instead of the maximum distance is easily solvable in linear time.

In this work, we settle the computational complexity of prominent consensus problems on circular strings and time series. Despite their great importance in many applications, and a correspondingly rich set of heuristic solution strategies used in practice, to date, it has been unknown whether these problems are polynomial-time solvable or NP-hard. We prove their hardness, including also "tight" parameterized and fine-grained complexity results, thus justifying the massive use of heuristic solution strategies in real-world applications.

On the route to determining the complexity of exact mean computation in dynamic time warping spaces, a fundamental consensus problem in the context of time series analysis [START_REF] Petitjean | A global averaging method for dynamic time warping, with applications to clustering[END_REF] 1 , we first study a fairly general alignment problem 2 for circular

1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 Fig. 1.
An instance of σ-MSCS with three binary input strings, and an optimal multiple circular shift ∆ = (0, 2, 1), using the sum of squared distances from the mean (σ) as a cost function. Columns of ∆ are indicated with dark (red) or light (green) lines, depending on their cost. For example, column 1 with values (1, 0, 1) has mean 2 3 and cost

1 3 2 + 2 3 2 + 1 3 2 = 2 3 .
The overall cost is 4 3 .

strings called Multiple String Circular Shift (with Cost f ). Based on its analysis, we will also derive our results for two further, more specific problems. Given a set of input strings over a fixed alphabet Σ and a local cost function f : Σ * → Q, the goal in Multiple String Circular Shift (with Cost f ) (abbreviated by f -MSCS) is to find a cyclic shift of each input string such that the shifted strings "align well" in terms of the sum of local costs. String). As we will show, allowing circular shifts makes consensus string problems much harder to solve.

Multiple circular string (sequence) alignment problems have been considered in different variations in bioinformatics, where circular strings naturally arise in several applications (for example, in multiple alignment of genomes, which often have a circular molecular structure) [START_REF] Ayad | MARS: improving multiple circular sequence alignment using refined sequences[END_REF][START_REF] Barton | Accurate and efficient methods to improve multiple circular sequence alignment[END_REF][START_REF] Fernandes | CSA: An efficient algorithm to improve circular DNA multiple alignment[END_REF][START_REF] Grossi | Circular sequence comparison: algorithms and applications[END_REF][START_REF] Mollineda | Cyclic sequence alignments: Approximate versus optimal techniques[END_REF]37]. Depending on the application at hand, different cost functions are used. For example, non-trivial algorithms for computing a consensus string of three and four circular strings with respect to the Hamming distance have been developed [START_REF] Lee | Finding consensus and optimal alignment of circular strings[END_REF]. However, most of the algorithmic work so far is heuristic in nature or only considers specific special cases. A thorough analysis of the computational complexity for these problems in general so far has been missing.

After having dealt with circular string alignment problems in a quite general fashion, we then study a fundamental (consensus) problem in time series analysis.

Dynamic time warping (see Section 2 for details) defines a distance between two time series which is used in many applications in time series analysis [START_REF] Keogh | Exact indexing of dynamic time warping[END_REF][START_REF] Morel | Time-series averaging using constrained dynamic time warping with tolerance[END_REF][START_REF] Petitjean | A global averaging method for dynamic time warping, with applications to clustering[END_REF][START_REF] Soheily-Khah | Generalized This manuscript is for review purposes only[END_REF] (notably, dynamic time warping has also been considered in the context of circular

x 1 x 1 x 2 x 2 x 3 x 3 z cost: 3 4 2 0 0 32 3
Fig. 2. A DTW-Mean instance with three input sequences and an optimal length-5 mean (z). Alignments between the mean and input sequences can progress at different speeds. This is formalized using warping paths (see Section 2) represented by polygons (or lines in degenerate cases) with alternating shades. Every pair of aligned elements belongs to the same polygon. The cost of each mean element is the sum of squared differences over all aligned input elements, e.g. the cost of the first element is (1

-1 4 ) 2 + 3 • (0 -1 4 ) 2 = 3 4 .
sequences [START_REF] Arica | Cyclic sequence comparison using dynamic warping[END_REF][START_REF] Palazón-González | On the dynamic time warping of cyclic sequences for shape retrieval[END_REF]). An important problem here is to compute an average of a given sample of time series under the dynamic time warping distance.

DTW-Mean

Input:

A list of k univariate rational time series x 1 , . . . , x k and c ∈ Q. Question: Is there a univariate rational time series z such that F(z) = k i=1 (dtw(z, x i ))

2 ≤ c?

Here, dtw denotes the dynamic time warping distance (see Section 2 for details).

Intuitively, dynamic time warping allows for non-linear alignments between two series. Figure 2 depicts an example. The dtw-distance of two length-n time series can be computed via standard dynamic programming in O(n 2 ) time. Some subquadratic algorithms are known [START_REF] Gold | Dynamic time warping and geometric edit distance: Breaking the quadratic barrier[END_REF][START_REF] Kuszmaul | Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation[END_REF][START_REF] Froese | Fast exact dynamic time warping on run-length encoded time series[END_REF]. For two binary time series, there exists an O(n 1.87 )time algorithm [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]. In general, however, a strongly subquadratic-time algorithm (that is, O(n 2-ε ) time for some ε > 0) does not exist unless the Strong Exponential Time

Hypothesis fails [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF][START_REF] Bringmann | Quadratic conditional lower bounds for string problems and dynamic time warping[END_REF][START_REF] Kuszmaul | Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation[END_REF].

Regarding the computational complexity of DTW-Mean, although more or less implicitly assumed in many publications presenting heuristic solution strategies 4 , NPhardness still has been open (see Brill et al. [6,Section 3] for a discussion on some misconceptions and wrong statements in the literature). It is known to be solvable in O(n 2k+1 2 k k) time, where n is the maximum length of any input series [START_REF] Brill | Exact mean computation in dynamic time warping spaces[END_REF]. Moreover, Brill et al. [START_REF] Brill | Exact mean computation in dynamic time warping spaces[END_REF] presented a polynomial-time algorithm for the special case of binary time series which has been improved recently [START_REF] Schaar | Faster binary mean computation under dynamic time warping[END_REF]. In practice, numerous heuristics are used [START_REF] Cuturi | Soft-DTW: a differentiable loss function for timeseries[END_REF][START_REF] Petitjean | Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm[END_REF][START_REF] Petitjean | A global averaging method for dynamic time warping, with applications to clustering[END_REF][START_REF] Schultz | Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces[END_REF]. Note that DTW-Mean is often described as closely related to multiple sequence alignment problems [START_REF] Aghabozorgi | Time-series clustering -A decade review[END_REF][START_REF] Paparrizos | Fast and accurate time-series clustering[END_REF][START_REF] Petitjean | Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment[END_REF]. However, we are not aware of any formal proof regarding this connection. By giving a polynomial-time manyone reduction from Multiple String Circular Shift (with Cost f ) to DTW-Mean, we show that DTW-Mean is actually connected to multiple circular sequence alignment problems. To the best of our knowledge, this is the first formally proven result regarding this connection.

Our Results. Using plausible complexity-theoretic assumptions, we provide a finegrained picture of the exact computational complexity (including parameterized complexity) of the problems introduced above. We present two main results.

First, we show that, for a large class of natural cost functions f , f -MSCS on binary sequences is NP-hard, W [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]-hard with respect to the number k of inputs, and not solvable in ρ(k) • n o(k) time for any computable function ρ (unless the Exponential Time Hypothesis fails). Note that f -MSCS is easily solvable in ρ(k) • n O(k) time (for computable functions f ) since there are at most n k-1 cyclic shifts to try out (without loss of generality, the first string is not shifted). Our running time lower bound thus implies that the brute-force approach can only be improved up to a constant factor in the exponent. Based on this, we can also prove the same hardness for the Circular Consensus String problem. In fact, the general ideas of our reduction might also be used to develop hardness reductions for other circular string alignment problems.

As our second main contribution, we obtain the same list of hardness results as above for DTW-Mean on binary time series. We achieve this by a polynomial-time reduction from a special case of f -MSCS. Our reduction implies that, unless the Exponential Time Hypothesis fails, the known O(n 2k+1 2 k k)-time algorithm [START_REF] Brill | Exact mean computation in dynamic time warping spaces[END_REF] essentially can be improved only up to constants in the first exponent. Note that recently Buchin et al. [START_REF] Buchin | On the hardness of computing an average curve[END_REF] achieved the same hardness result for the problem of averaging time series under generalized (p, q)-DTW. Their reduction, however, does not yield binary input time series.

Organization. In Section 2 we fix notation and introduce basic concepts, also including the formal definition of dynamic time warping and the corresponding concept of warping paths. In Section For 0 ≤ δ < n, we define the circular (left) shift by δ as the string

s ←δ :=s[δ + 1] . . . s[n]s[1] . . . s[δ] (note that s ←δ [i] = s[(i + δ -1 mod n) + 1]),
that is, we circularly shift the string δ times to the left. . We define column i ∈ {1, . . . , n} of a multiple circular shift ∆ as the k-tuple (s ←δ1

1 [i], . . . , s ←δ k k [i]).
By row j ∈ {1, . . . , k} of column i we denote the element s

←δj j [i].
This manuscript is for review purposes only.

Cost Functions. A local cost function is a function f : Σ * → Q assigning a cost to any tuple of values. Given such a function, the overall cost of a circular shift ∆ for k length-n strings is defined as

cost f (∆) := n i=1 f (s ←δ1 1 [i], . . . , s ←δ k k [i]) ,
that is, we sum up the local costs of all columns of ∆.

An example for a local cost is the sum of squared distances from the arithmetic mean (i.e., k times the variance, here called σ), that is,

σ((x 1 , . . . , x k )) = k i=1   x i - 1 k k j=1 x j   2 .
Using a well-known formula for the variance, we get the following useful formula for σ:

σ((x 1 , . . . , x k )) = k j=1 x 2 j - 1 k k j=1 x j 2 .
For binary strings (that is, x j ∈ {0, 1} for all 1 ≤ j ≤ k), σ does only depend on the number w := k j=1 x j of 1's and the number k -w of 0's and can be written (according to the formula above) as

(2.1) σ((x 1 , . . . , x k )) = w - w 2 k = w(k -w) k .
We will repeatedly use this formula later on for cost calculations in the proof for DTW-Mean (Theorem 5.1).

Dynamic Time Warping.

A time series is a sequence x = (x 1 , . . . , x n ) ∈ Q n . The dynamic time warping distance between two time series is based on the concept of a warping path.

Definition 2.1. A warping path of order m × n is a sequence p = (p 1 , . . . , p L ),

L ∈ N, of index pairs p = (i , j ) ∈ {1, . . . , m} × {1, . . . , n}, 1 ≤ ≤ L, such that (i) p 1 = (1, 1), (ii) p L = (m, n), and (iii) (i +1 -i , j +1 -j ) ∈ {(1, 0), (0, 1), (1, 1)} for each 1 ≤ ≤ L -1.
See Figure 2 in Section 1 for an example.

(x[i] -y[j]) 2 1/2 .
Note that also other cost functions can be considered. In this work, we only consider the most common case of squared costs.

A mean of time series x 1 , . . . , x k is a time series that minimizes the Fréchet function

F(z) := k j=1 (dtw(z, x j )) 2 = k j=1 min pj ∈P |x j |,|z| (u,v)∈pj (x j [u] -z[v]) 2 .
Note that given, for each j ∈ [k], a warping path p j between z and x j , the value of

z[i] that minimizes (2.2) k j=1 (u,v)∈pj (x j [u] -z[v]) 2
is the arithmetic mean of all values aligned to z[i],

z[i] = k j=1 (i,u)∈pj x j [u] k j=1 |{(i, u) ∈ p j }| .
That is, the length of a mean together with the optimal alignments to the input time series determine the mean. The contribution of z[i] to the sum (2.2) is the sum of squared distances between z[i] and all values aligned to z

[i], k j=1 (u,i)∈pj (x j [u] -z[i]) 2 .
Note that this corresponds to the cost function σ above.

We remark that for DTW-Mean, often a normalized cost F (z) := 1 k F(z) is considered. Clearly, this does not affect the computational complexity of the problem, so for simplification purposes we only consider the non-normalized cost F(z).

Parameterized Complexity. We assume familiarity with the basic concepts from classic and parameterized complexity theory. 1) to an equivalent instance (I , k ) of P such that k ≤ g(k) (for some computable functions f and g). It holds that

mapping an instance (I, k) of Q in time f (k) • |I| O(
FPT ⊆ W[1] ⊆ XP.
A parameterized problem that is W [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]-hard with respect to a parameter (such as

Clique with parameter clique size) is widely believed not to be in FPT.

Exponential Time Hypothesis. Impagliazzo and Paturi [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF] formulated the Exponential Time Hypothesis (ETH) which asserts that there exists a constant c > 0 such that 3-SAT cannot be solved in O(2 cn ) time, where n is the number n of variables in the input formula. It is a stronger assumption than common complexity assumptions such as P =NP or FPT =W [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF].

Several conditional running time lower bounds have since been shown based on the ETH, for example, Clique cannot be solved in ρ(k)•n o(k) time for any computable function ρ unless the ETH fails [START_REF] Chen | Tight lower bounds for certain parameterized NP-hard problems[END_REF].

This manuscript is for review purposes only.

3. Hardness of f -MSCS on Binary Strings. In this section, we focus on binary strings from {0, 1} * . We prove hardness for a family of local cost functions that satisfy certain properties. The functions we consider have the common property that they only depend on the number of 0's and 1's in a column, and that they aim at grouping similar values together.

Definition 3.1. A function f : {0, 1} * → Q is called order-independent (or sym- metric) if, for each k ∈ N, there exists a function f k : {0, . . . , k} → Q such that f ((x 1 , . . . , x k )) = f k k j=1 x j holds for all (x 1 , . . . , x k ) ∈ {0, 1} k .
For an order-independent function f , we define the function

f k : {1, . . . , k} → Q as f k (x) := f k (x) -f k (0)
x .

An order-independent function

f is grouping if f k (k) < min 1≤x<k f k (x) and f k (2) < f k (1) holds for every k ∈ N.
For an order-independent function f , f k can be seen as the cost per 1-value (a column with x 1's and k -x 0's has cost

f k (x) = f k (0) + xf k (x))
. It can also be seen as a discrete version of the derivative for f k , so that if f k is concave then f k is decreasing. The intuition behind a grouping function is that the cost per 1-value is minimal in columns containing only 1's, and that having two 1's in a column has less cost than having two columns with a single 1. In particular, any function f where all f k are strictly concave is grouping. Finally, if f is grouping, then the function

(x 1 , . . . , x k ) → f k   k j=1 x j   + a k j=1
x j + b is also grouping for any a, b ∈ Q.

The following definitions are required to ensure that our subsequent reduction (Lemma 3.3) is computable in polynomial time.

Definition 3.2. Let f be an order-independent function. The gap of f k is

ε k := min{f k (x) -f k (y) | 1 ≤ x, y ≤ k, f k (x) > f k (y)}. The range of f k is µ k := max 1≤x≤k |f k (x)|.
An order-independent function f is polynomially bounded if it is polynomial-time computable and if, for every k ∈ N, µ k and ε -1 k are upper-bounded by a polynomial in k.

For binary strings, the function σ (see Section 2) is a polynomially bounded grouping function. Indeed, it is order-independent since σ((x 1 , . . . , x k )) = w(k-w) k , where w = k j=1 x j . Thus, σ k (w) = w(k-w) k and we have σ k (0) = 0, and σ k (w) = k-w k , so σ k is strictly decreasing, which is sufficient for σ to be grouping. Finally, it is polynomially bounded, with gap

ε k = 1 k and range µ k = k-1 k ≤ 1.
We prove our hardness results with a polynomial-time reduction from a special version of the Clique problem.

This manuscript is for review purposes only.

Regular Multicolored Clique (RMCC)

Input:

A d-regular undirected graph G = (V, E) where the vertices are colored with k colors such that each color class contains the same number of vertices. Question: Does G have a size-k complete subgraph (containing k 2 edges, called a k-clique) with exactly one vertex from each color?

RMCC is known to be NP-hard, W [START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]-hard with respect to k, and not solvable in k) time for any computable function ρ unless the ETH fails [START_REF] Cygan | Parameterized Algorithms[END_REF].

ρ(k) • |V | o(
The following lemma states the existence of a polynomial-time reduction from RMCC to f -MSCS which implies hardness of f -MSCS for polynomially bounded grouping functions.

Lemma 3.3. Let f be a polynomially bounded grouping function. Then there is a polynomial-time reduction that, given an RMCC instance G = (V, E) with k colors, outputs binary strings s 0 , . . . , s k of equal length and c ∈ Q such that the following holds:

• If G contains a properly colored k-clique, then there exists a multiple circular shift ∆ of s 0 , . . . , s k with cost f (∆) = c.

• If G does not contain a properly colored k-clique, then every multiple circular shift ∆ of s 0 , . . . , s k has cost f (∆) ≥ c + ε k+1 .
To prove Lemma 3.3, we first describe the reduction and then prove several claims about the structure and the costs of multiple circular shifts in the resulting f -MSCS instance.

Reduction. Consider an instance of

RMCC, that is, a graph G = (V, E) with a partition of V into k subsets V 1 , . . . , V k of size n := |V |
k each, such that each vertex has degree d. Let V j = {v j,1 , . . . , v j,n }, m = |E|, and E = {e 1 , . . . , e m }. We assume that k ≥ 3 since the instance is trivially solvable otherwise.

We build an f -MSCS instance with k + 1 binary strings. Hence, the local cost of a column of a multiple circular shift is given by the function f k+1 . For simplicity, we write f , gap ε, and range µ for f k+1 , ε k+1 , and µ k+1 .

For each j ∈ {1, . . . , k}, let p j be the length-k string such that p j [h] = 1 if h = j, and p j [h] = 0 otherwise. For each vertex v j,i , let q j,i ∈ {0, 1} m be the string such that

q j,i [h] := 1, if 1 ≤ h ≤ m and v j,i ∈ e h 0, otherwise
and let u j,i := p j q j,i be the concatenation of p j and q j,i . Note that u j,i has length m := m + k, contains 1 + d ones, and m -1 -d zeros. Let 0 := 0 m be the string containing m zeros and define the numbers

κ := knd + kn + k, γ := nk, λ := max κ 2µ ε + 1 , 2n(γ + k + 1) + 1.
For 1 ≤ j ≤ k, we define the string s j := 1u j,1 (10 ) γ+j 1u j,2 (10 ) γ+j . . . 1u j,n (10 ) γ+j (10 ) λ-n(γ+j+1) .

Note that |1u j,i | = |10 | = m + 1. Thus, each string s j has length

n(m + 1)(1 + γ + j) + (m + 1)(λ -n(γ + j + 1)) = λ(m + 1) =: ,
This manuscript is for review purposes only.

where ≤ poly(nk). We further define the following length-dummy string

s 0 = 11 k 0 m (10 ) λ-1 .
Finally, we define the target cost

c := f k+1 (0) + λ(k + 1)f (k + 1) + 2 k + k 2 (f (2) -f (1)) + κf (1).
Clearly, the strings s 0 , . . . , s k and the value c can be computed in polynomial time.

Our construction is illustrated in Figure 3.

In the strings s 0 , . . . , s k , any 1-value at a position i with i mod (m + 1) = 1 is called a separator, other 1-values are coding values. A coding value is either vertexcoding if it belongs to some p j (or to the k coding values of s 0 ), or edge-coding otherwise (then it belongs to some q i,j ). There are λ(k + 1) separator values in total and κ coding values.

Given a multiple circular shift ∆, we define the weight w of a column as the number of 1-values it contains, that is, 0 ≤ w ≤ k + 1. The cost for such column is

f k+1 (w) = f k+1 (0) + wf (w). Each 1-value of this column is attributed a local cost
of f (w), so that the cost of any solution is composed of a base cost of f k+1 (0) and of the sum of all local costs of all 1-values. In the following we mainly focus on local costs.

It remains to be shown that there exists a multiple circular shift of s 0 , . . . , s k with cost c if G contains a properly colored k-clique, and that otherwise every multiple circular shift has cost at least c + ε. We proceed by analyzing the structure and costs of optimal multiple circular shifts.

Aligning Separators. Let ∆ = (δ 0 , . . . , δ k ) be a multiple circular shift of s 0 , . . . , s k .

Without loss of generality, we can assume that δ 0 = 0 since setting each δ j to (δ jδ 0 ) mod yields a shift with the same cost. First, we show that if δ j mod (m + 1) = 0 holds for some 0 < j ≤ k, then ∆ has large cost.

Claim 3.4. For any multiple circular shift ∆ = (δ 0 = 0, δ 1 , . . . , δ k ) with δ j mod

(m + 1) = 0 for some 1 < j ≤ k, it holds that cost f (∆) ≥ c + ε. Proof. Assume that δ j mod (m + 1) = a ∈ {1, . . . , m } for some 0 < j ≤ k.
We count the number of weight-(k + 1) columns: such a column cannot only contain separator values since it cannot contain a separator value in both row 0 and row j.

Hence, it contains at least one coding value. Since there are κ coding values, there are at most κ weight-(k + 1) columns, so at most kκ separator values have local cost f (k + 1). All other separator values have local cost f (w) for some w < k + 1, which is at least f (k + 1) + ε. There are at least λ(k + 1) -kκ such separator values. Adding the base cost of f k+1 (0), the cost of ∆ is thus at least:

cost f (∆) ≥ f k+1 (0) + (λ(k + 1) -kκ)(f (k + 1) + ε) ≥ f k+1 (0) + λ(k + 1)f (k + 1) + λkε -kκ(µ + ε).
This manuscript is for review purposes only.

v 1,1 v 1,2 v 1,3 v 2,1 v 2,2 v 2,3 v 3,1 v 3,2 v 3,3 V 1 V 2 V 3 s 0 s 1 s 2 s 3 u 1,1 u 1,2 u 1,3 u 2,1 u 2,2 u 2,3 u 3,1 u 3,2 u 3,3 s 0 s 1 s 2 s 3 u 1,1 u 1,2 u 1,3 u 2,3 u 2,1 u 2,2 u 3,1 u 3,2 u 3,3 s 0 1 1 s 1 1 1 s 2 1 1 s 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 • • • 1 1 • • • 1 1 • • • 1 1 • • • 1 1 1 1 1 1 1
Fig. 3. Illustration of the reduction from an instance of RMCC (top) with k = 3. Middle: Sequences s 0 to s 3 , and their optimal circular shifts s 0 to s 3 . Blue stripes represent the regularlyspaced separator 1-values. The (light) gray intervals contain both 0's and 1's according to strings u i,j , and white intervals contain only 0's. The spacing between consecutive u i,j 's is defined using γ and the overall string length depends on λ, both values are chosen so as to restrict the possible alignments between different u i,j 's; in this example we use γ = 1 and λ = 19. Bottom: a zoom-in on blocks 1 and 12 in the shifted strings (only non-0 values are indicated, weight-2 columns are highlighted). Through vertex columns, the dummy string s 0 ensures that one vertex occupies block 1 in each row, and weight-2 edge-columns ensure that k 2 edges (as highlighted in the graph) are induced by these vertices.

Recall that

c = f k+1 (0) + λ(k + 1)f (k + 1) + 2 k + k 2 (f (2) -f (1)) + κf (1) ≤ f k+1 (0) + λ(k + 1)f (k + 1) + κµ
This manuscript is for review purposes only.

since f (2) -f (1) < 0. Combining the above bounds for c and cost f (∆) using

λ ≥ κ 2µ ε + 1 + 1 (by definition) yields cost f (∆) -c ≥ λkε -kκ(µ + ε) -κµ ≥ 2κkµ + κkε + kε -kκ(µ + ε) -κµ ≥ ε.
Cost of Circular Shifts. We assume from now on that δ j mod (m + 1) = 0 for all j ∈ {0, . . . , k}. We now provide a precise characterization of the cost of ∆.

For l ∈ {1, . . . , λ}, we define the l-th block consisting of the m consecutive columns (l-1)(m +1)+2, . . . , l(m +1). The block index of column i is i-1 mod (m + 1). For j ∈ {1, . . . , k}, the substring s

←δj j [(l -1)(m + 1) + 2] . . . s ←δj j
[l(m + 1)] corresponding to the l-th block of s ←δj j either equals some u j,i or 0 . We say that block l (since they all are in block 1). We now focus on weight-2 edge-columns. The following claim will help us to show an upper bound on their number.

is occupied by vertex v j,i ∈ V j , if
Claim 3.7. For any two rows j, j , there exists at most one block l that is occupied by vertices from both V j and V j .

Proof. First, note that if two distinct blocks l and l are both occupied by a vertex from the same row j, then, by construction, there are two possible cases:

either |l -l | = a(γ + j + 1) or |l -l | = λ -a(γ + j + 1)
, where 1 ≤ a < n in both cases.

This manuscript is for review purposes only.

Indeed, there are n regularly-spaced substrings u j,i (having γ + j blocks in between them) in s j (consisting of λ blocks in total).

Assume towards a contradiction that two distinct blocks l and l are each occupied by a vertex from V j and V j . Then, there exists an a ∈ {1, . . . , n -1} such that

|l -l | = a(γ + j + 1) or |l -l | = λ -a(γ + j + 1)
, and there exists an a ∈ {1, . . . , n -1} such that |l -l | = a (γ + j + 1) or |l -l | = λ -a (γ + j + 1). This gives four cases to consider (in fact just three by symmetry of j and j ).

If |l -l | = a(γ + j + 1) = a (γ + j + 1), then (a -a )(γ + 1) = a j -aj. We have a = a , as otherwise this would imply j = j . So |a j -aj| ≥ γ + 1, but this is impossible since a < n, a < n, j ≤ k, j ≤ k, that is, |a j -aj| ≤ kn, whereas

γ + 1 = kn + 1 (by construction). If |l -l | = a(γ + j + 1) = λ -a (γ + j + 1), then λ = a(γ + j + 1) + a (γ + j + 1).
However, λ > 2n(γ + k + 1) by construction, so this case also leads to a contradiction.

Finally, if |l -l | = λ -a(γ + j + 1) = λ -a (γ + j + 1
), then we have a(γ + j + 1) = a (γ + j + 1). This case yields, as the first case, a contradiction.

Claim 3.8. There are at most k 2 weight-2 edge-columns.

Proof. Consider any pair j, j such that 1 ≤ j < j ≤ k. It suffices to show that there exists at most one weight-2 edge-column with a 1 in rows j and j . Aiming at a contradiction, assume that two such columns exist. By Observation 3.6, they must each belong to a block which is occupied by vertices both in V j and V j . From Claim 3.7 it follows that both columns belong to the same block. Let v and v be the vertices of V j and V j , respectively, occupying this block. By Observation 3.6 again, both edges are equal to {v, v }, which contradicts the fact that they are distinct.

Having established an upper bound of k + k 2 for the number of weight-2 columns, the following result describes the corresponding cost.

Claim 3.9. Let W 2 be the number of weight-2 columns. If

W 2 = k + k 2 , then cost f (∆) = c. If W 2 < k + k 2 , then cost f (∆) ≥ c + ε.
cost f (∆) = f k+1 (0) + λ(k + 1)f (k + 1) + 2W 2 (f (2) -f (1)) + κf (1).
Thus, by definition of c, we have cost

f (∆) = c if W 2 = k + k 2 . If W 2 < k + k 2 , then
using the fact that, by assumption,

f (2) -f (1) ≤ -ε, we obtain cost f (∆) = c + 2 W 2 -k - k 2 (f (2) -f (1)) ≥ c + ε.
This manuscript is for review purposes only. This manuscript is for review purposes only.

Corollary 3.12. Let f be a computable grouping function. For binary strings, it can easily be seen that the cost induced by column i is the minimum of the number of 0's and the number of 1's. Let f CS be the polynomially bounded order-independent function with f CS k (w) = min{w, k -w}. It follows from the discussion above that Circular Consensus String is exactly f CS -MSCS. Note, however, that f CS is not a grouping function since

f CS k (2) = f CS k (1) = 1.
That is, we do not immediately obtain hardness of CCS from Theorem 3.11. We can still prove hardness via a reduction using a properly chosen polynomially bounded grouping function. Proof. As discussed above, CCS is equivalent to f CS -MSCS. To prove hardness, we define a local cost function g (similar to f CS ) and reduce from g-MSCS to f CS -MSCS.

Let g be the order-independent local cost function such that

g k (w) := f CS 2k-2 (w + (k -2)) = min{w + k -2, k -w}.
Note that the function g k is linearly decreasing on {1, . . . , k} and that

g k (w) = 2-w w = 2 w -1. The range of g k is µ k = 1 and its gap is ε k = 2 k-1 -2 k > 2 k 2 .
That is, g satisfies all conditions of Theorem 3.11 and the corresponding hardness results hold for g-MSCS.

See Figure 4 for an illustration.

Given an instance I = (s 1 , . . . , s k , c) of g-MSCS, we define the strings s j := 1 |s1|

for j = k + 1, . . . , 2k -2. We show that I is a yes-instance if and only if I := (s 1 , . . . , s 2k-2 , c) is a yes-instance for f CS -MSCS.

For the forward direction, consider a multiple circular shift ∆ = (δ 1 , . . . , δ k ) of s 1 , . . . , s k such that cost g (∆) ≤ c. We define the multiple circular shift ∆ := (δ 1 , . . . , δ k , δ k+1 = 0, . . . , δ 2k-2 = 0) of s 1 , . The converse direction is similar. Any multiple circular shift ∆ of s 1 , . . . , s 2k-2 can be restricted to a multiple circular shift ∆ of s 1 , . . . , s k with the same cost.

5. Consensus for Time Series: DTW-Mean. In this section we consider the DTW-Mean problem.

DTW-Mean Input:

A list of k univariate rational time series x 1 , . . . , x k and c ∈ Q. Question: Is there a univariate rational time series z such that

F(z) = k i=1 (dtw(z, x i )) 2 ≤ c?
We prove the following theorem, settling the complexity status of this prominent consensus problem in time series analysis. The proof is based on a polynomial-time reduction from a special variant of f -MSCS for which hardness holds via Theorem 3.11 in Section 3. At this point we make crucial use of the fact that the reduction described in the proof of Lemma 3.3 actually shows that it is hard to decide whether there is a multiple circular shift of cost at most c or whether all multiple circular shifts have cost at least c + ε for some ε polynomially bounded in the number of strings. This gap of ε guarantees that a noinstance of f -MSCS is reduced to a no-instance of DTW-Mean. Being polynomially bounded is required for ε in order to obtain a polynomial-time reduction (otherwise our constructed time series are too long).

Before proving Theorem 5.1, we introduce some definitions. A position i in a time series x is an integer 1 ≤ i ≤ |x|, its value is x[i]. The distance between two positions i and i is |i -i|. A block in a binary time series is a maximal subseries of consecutive 0's (a 0-block ) or 1's (a 1-block ). Blocks are also represented by integers, indicating their rank in the series (a series with n blocks has blocks 1, 2, . . . , n). The distance between two blocks of rank y and y is |y -y|. Note that the notion of distance is different in the context of positions and blocks (even between size-1 blocks, as larger blocks in between increase the position distance).

Recall from Section 2 that once the length of a mean z and the alignments to

This manuscript is for review purposes only.

the input time series are known, then its values are determined. In the binary case, a position i that is aligned to a 0's and b 1's contributes a cost of az

[i] 2 + b(1 -z[i]) 2
to F(z). This cost is minimal for z[i] being the arithmetic mean b/(a + b) of all values aligned to position i. Thus, the cost of position i is

C(i) = min x∈Q (ax 2 + b(1 -x) 2 ) = ab a + b ,
where the second equality follows from Equation (2.1). The reduction in the following proof of Theorem 5.1 is from φ-MSCS for a polynomially bounded grouping function φ specifically chosen in relation to the above cost of a mean position.

Proof. We will reduce from φ-MSCS for a specially chosen cost function φ which we explain first. To this end, we briefly sketch the idea of the reduction. Given k binary strings for φ-MSCS, we construct k+1 binary time series: k time series encoding the original strings and a dummy time series containing a single 1. The construction is such that a column of a multiple circular shift with x 1's and k -x 0's will correspond to a position in a time series that is aligned to k + x 0's and one 1. Now, the cost of that column should be equal to the cost (k + x)/(k + x + 1) of that position minus k/(k +1) (for technical reasons the cost should be 0 if x = 0). That is, we define

φ : {0, 1} * → [0, 1] with φ((x 1 , . . . , x k )) = φ k ( k j=1 x j ), where φ k : {0, . . . , k} → [0, 1] with φ k (x) = k + x k + x + 1 - k k + 1 = x (k + x + 1)(k + 1)
.

Note that φ is a polynomially bounded grouping function since

φ k (x) = φ k (x) -φ k (0) x = 1 (k + x + 1)(k + 1)
is strictly decreasing (φ k is strictly concave) with gap

ε k = φ k (k -1) -φ k (k) = 1 (k + 1)(2k)(2k + 1)
and range

µ k = φ k (1) = 1 (k + 2)(k + 1)
.

See Figure 5 for an example of the functions φ k and φ k . Hence, by Theorem 3.11 hardness holds for φ-MSCS. We now give the polynomial-time reduction from φ-MSCS, see Figure 6 for an illustration of the reduction.

Reduction. In the following, we assume to have an instance of φ-MSCS with k ≥ 15 length-n binary strings s 1 , . . . , s k ∈ {A, B} n (where A := 0 and B := 1) and a target cost 0 ≤ c ≤ n. We write ε for the gap

ε k of φ k (note that ε -1 ∈ O(k 3 )).
The task is to decide whether there exists a multiple circular shift of cost at most c or whether all multiple circular shifts have cost at least c+ε (the reduction in Lemma 3.3 implies the hardness of this decision problem).

First, we encode characters A and B via certain binary strings. To this end, we define the number m := 1600k c + ε and the binary strings t A := (10) m and t B := 100(10) m-1 , each string having m 0-blocks (all of length one, except for the first 0-block of t B which has length two). The first 0-block of t A and t B is called a coding block (respectively, an A-coding or a B-coding block).

This manuscript is for review purposes only. Now, for each 1 ≤ j ≤ k, let s j be the string obtained by concatenating the strings

t sj [i] for 1 ≤ i ≤ |s j |.
The final time series x j is obtained by concatenating r copies of s j , where

r := 1 ε (3mnk + 2(c + ε)) + 1.
Note that each x j contains 2mnr blocks and |x j | ≤ poly(nk). We also define the extra series x k+1 = (1) and set the target cost to

c := r c + mnk k + 1 + 3mnk.
For the correctness of this reduction we need to prove the following:

(i) If (s 1 , . . . , s k , c
) is a yes-instance, that is, there exists a multiple circular shift ∆ with cost φ (∆) ≤ c, then there exists a time series z with F(z) ≤ c .

(ii) If (s 1 , . . . , s k , c) is a no-instance, that is, cost φ (∆) ≥ c+ε holds for every multiple circular shift ∆, then F(z) > c holds for every time series z.

(i) Yes-instance of φ-MSCS. Consider a multiple circular shift ∆ = (δ 1 , . . . , δ k ) of s 1 , . . . , s k with cost φ (∆) ≤ c. Without loss of generality, we assume that 0 ≤ δ j < n holds for every 1 ≤ j ≤ k.

We construct a time series z of length 2mn(r -1) + 2 (also see Figure 6) such that F(z) ≤ c . To this end, we describe the alignments between z and x 1 , . . . , x k+1

(recall that this determines the values and costs of positions in z). For each j = 1, . . . , k, the first position is aligned with the leftmost 2δ j m blocks of each x j (or with the first block if δ j = 0) and the last position is aligned with the rightmost 2(n -δ j )m blocks of x j . For each 1 < i < 2mn(r -1) + 2, position i is aligned with the (i -1 + 2δ j m)-th block of x j . These positions are called regular positions, whereas the first and last position are called extreme. Clearly, all positions of z are also aligned with the single 1 in x k+1 .

Given the above alignments, the sum of costs of all positions in z is clearly an upper bound for F(z). The following two claims give an upper bound for this sum.

Claim 5.2. The total cost of regular positions is at most (r -1)(c + mnk k+1 ).

Proof. Due to the alternation of 1-and 0-blocks in each x j and the fact that i + (2δ j m) ≡ i (mod 2), it follows that the i-th regular position (which is z[i + 1]) is mapped only to 1's if i is odd (odd position) or only to 0's (and the single 1 in x k+1 ) if i is even (even positions). Thus, odd positions have cost (k+1)•0 k+1 = 0, and even positions have a cost depending on the size of the 0-blocks to which they are mapped.

This manuscript is for review purposes only.

s 1 : s 1 :
x 1 :

s 2 : s 2 :
x 2 : s 3 : s 3 :

x 3 :

x 4 :

z :

cost:

(1) (1) (3) (3) (0) A t A 10(10) m-1 0 ••• 0 ••• 0 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• B t B 100(10) m-1 00 ••• 00 ••• 00 ••• A t A 10(10) m-1 0 ••• 0 ••• 0 ••• 1 1 4 ••• 1 5 ••• 1 5 ••• 1 7 ••• 1 7 ••• 3 4 ••• 4 5 ••• 4 5 ••• 6 7 ••• 6 7 ••• 1 4 ••• 1 5 ••• 1 5 ••• 1 7 ••• 1 7 ••• 3 4 ••• 4 5 ••• 4 5 ••• 6 7 ••• 6 7 ••• ••• ••• 1 2 O(kmn) 1 2
O(kmn) translate using t A , t B repeat r times ). Note that the cost function φ is chosen so that the cost of a position aligned to k coding blocks equals the cost of the corresponding column of the original circular shift (plus the background cost 3 4 ). For example, a position aligned to two A-coding blocks and one B-coding block has cost 4 5 = 3 4 + φ 3 (1), where φ 3 (1) is the cost of a column with two A's and one B in φ-MSCS. The value of m is chosen large enough to yield a large cost for misalignments, such as two consecutive coding blocks of the same series aligned together. The value of r is chosen such that only a periodic pattern ensures low cost of z, even though it requires to pay a high (but bounded) misalignment cost for the first and last positions.

Consider an even position i such that i mod 2m = 2. The i-th regular position is not aligned with any coding block in any x j . Thus, it is aligned to k 0's and a single 1, and has cost C(i + 1) = k k+1 . There are (m -1)n(r -1) such positions, which thus contribute a total cost of (r -1) (m -1)nk k + 1 .

For an even position i with i mod 2m = 2, the i-th regular position is aligned with a coding block in each x j (except for the single 1 in x k+1 ). Let i = 2mi + 2.

Then, z[i + 1] is aligned to coding blocks corresponding to column i mod n of ∆. If this column contains a A's and k -a B's, then z

[i + 1] is aligned to a + 2(k -a) 0's
This manuscript is for review purposes only.

and a single 1 and has cost

C(i + 1) = a + 2(k -a) a + 2(k -a) + 1 = 2k -a 2k -a + 1 = φ k (k -a) + k k + 1 .
Note that φ k (k -a) is the cost of column i mod n of ∆. Hence, the overall cost of the (r -1)n regular positions i with i mod 2m = 2 is

(r -1) cost φ (∆) + (r -1) nk k + 1 ≤ (r -1) c + nk k + 1 .
Overall, the regular positions have a total cost of at most

(r -1) (m -1)nk k + 1 + (r -1) c + nk k + 1 = (r -1) c + mnk k + 1 .
Claim 5.3. The total cost of extreme positions is at most 2knm + 2.

Proof. Since 0 ≤ δ j < n for j ∈ {1, . . . , k}, an extreme position i ∈ {1, |z|} is aligned to at most 2nm consecutive blocks in each x j , thus accounting for at most nm 1's in x j . Moreover, position i is aligned with the additional 1 in x k+1 . Thus, position i is aligned with at most nmk + 1 1's, which implies

C(i) ≤ nmk + 1 (this bound is achieved if z[i] = 0).
Combining Claims 5.2 and 5.3, we obtain

F(z) ≤ |z| i=1 C(i) ≤ (r -1) c + mnk k + 1 + 2knm + 2 ≤ c .
Hence, (x 1 , . . . , x k+1 , c ) is a yes-instance of DTW-Mean.

(ii) No-instance of φ-MSCS. We assume that every multiple circular shift ∆ has cost φ (∆) ≥ c + ε. Consider a fixed mean time series z (minimizing F) together with optimal warping paths between z and x 1 , . . . , x k+1 . We show that F(z) > c .

We will do this hierarchically, starting with a lower bound on the cost of an individual position of z. We then proceed to derive lower bounds for the cost of certain intervals of positions until finally obtaining the desired lower bound on F(z). Before doing so, we start with some preliminary observations about the structure of a mean.

Structural Observations. We say that position i of x j is matched to position i of z if (i, i ) is in the warping path between x j and z. Clearly, the single position in x k+1 is matched to every position of z. We write # 1 (i) and # 0 (i) respectively for the number of positions with value 1 (resp. 0) among x 1 , . . . , x k (ignoring the extra sequence x k+1 ) which are matched to position i of z. Clearly, the cost of i is

C(i) = # 0 (i)(# 1 (i) + 1) # 0 (i) + # 1 (i) + 1 .
We will use the following monotonicity property of the cost. This manuscript is for review purposes only.

L. BULTEAU, V. FROESE, AND R. NIEDERMEIER

We define some further notation for the remaining part of the proof. The range of a position i of z in x j is the set of positions of x j that are matched to i. The range is a subinterval of {1, 2, ..., |x j |} and by construction of x j , the corresponding subseries cannot have three consecutive 0's or two consecutive 1's. More precisely, its values alternate between 0 and 1, except for the (rare) occasions where it includes a B-coding block. The number of blocks of x j intersecting the range of i in x j is denoted r j (i). The number of B-coding blocks contained in the range of i in x j is denoted r B j (i) and we define r B (i

) := k j=1 r B j (i). A position i of z is called 0-simple (resp. 1-simple) if # 1 (i) = 0 (resp. # 0 (i) = 0).
It is simple if it is 0-or 1-simple, and it is bad otherwise. Clearly, the cost of a 1-simple position is 0. For a 0-simple position i, we have #

1 (i) = 0 and k ≤ # 0 (i) ≤ 2k (more precisely, # 0 (i) = k + r B (i) and r B (i) ≤ k). Thus, k k+1 ≤ C(i) ≤ 2k 2k+1 .
Since we assumed k ≥ 15, the cost of a 0-simple position is always contained in [0.9, 1].

We continue with several structural observations regarding a mean.

Observation 5.5. There exists a mean without consecutive 1-simple positions or consecutive 0-simple positions. Such a mean is called non-redundant.

Proof. Any two consecutive 1-simple (or 0-simple) positions of a non-redundant mean z have consecutive or intersecting ranges in each x j with the same value (1 or 0). Hence, they can be merged into one single 1-simple (or 0-simple) position.

Since the warping of the other positions in z remains unchanged, we focus on the cost of the merged position. For 1-simple positions, the cost remains unchanged (both solutions yield a cost of 0 for the 1-simple positions). For 0-simple positions, the cost of the two 0-simple positions in the original solution is at least 0.9 each. However, the cost of the merged 0-simple position is at most 1, which is a contradiction to z being a mean.

In the following, we assume z to be a non-redundant mean.

We say a block b of some input x j is matched (fully matched ) to a position i in z if some position (all positions) in b is (are) matched to i. That is, a matched block intersects the range of i and a fully matched block is included in the range of i.

Note that the distinction is only relevant for B-coding blocks, as all other blocks have size 1. Moreover, the number of B-coding blocks that are fully matched to a position i equals r B (i).

Observation 5.6. For a non-redundant mean z, any B-coding block of some x j that is not fully matched to a position in z is matched to at least one bad position in z.

If any block is matched to two consecutive positions in z, then at least one of them is bad.

Proof. Consider a B-coding block b and all positions of z to which it is matched.

There are at least two of them, which cannot all be 0-simple (since z is non-redundant).

Also, none of them can be 1-simple (since b is a 0-block). Thus, at least one of them is bad.

We prove the contrapositive of the second statement: If two simple positions have a common block matched to them, then they are both a-simple, a ∈ {0, 1}, and cannot be consecutive in a non-redundant mean.

We now introduce an assignment relation between a block b of some input series and a position i of z. We say that b is assigned to the position i if i is the leftmost simple position to which b is fully matched (if any), or (if no such simple position This manuscript is for review purposes only.

exists) if i is the leftmost bad position to which b is matched. Note that any size-1 block is fully matched to at least one position (simple or bad), and every size-2 block is either fully matched to a simple position or matched to a bad position (by Observation 5.6). Thus, every block is assigned to exactly one position.

For a position i of z, we introduce the following quantities:

♦ 0 (i) := number of 0-blocks in x 1 , . . . , x k matched to i, ♦ 1 (i) := number of 1-blocks in x 1 , . . . , x k matched to i, q(i) := number of B-coding blocks assigned to i,

g(i) := 0, if i is simple max{1, r 1 (i) -1, . . . , r k (i) -1}, if i is bad .
We quickly observe the following:

(I) If i is simple, then q(i) = r B (i).

Proof. By definition, every B-coding block assigned to i is fully matched to i, that is, q(i) ≤ r B (i). Furthermore, a B-coding block can be fully matched to only one position. Thus, if i is simple, then all B-coding blocks fully matched to it are also assigned to it, that is, q(i) ≥ r B (i).

(II) If i is 0-simple, then ♦ 0 (i) = k, ♦ 1 (i) = 0, and C(i) = k+q(i) k+q(i)+1 .

Proof. A 0-simple position has exactly one 0-block in each x 1 , . . . , x k matched to it. The cost follows from (I).

(III) If i is 1-simple, then ♦ 0 (i) = 0, ♦ 1 (i) = k, and C(i) = 0.

Proof. A 1-simple position has exactly one 1-block in each x 1 , . . . , x k matched to it.

(IV) If i is bad, then g(i) ≤ 2 min{♦ 1 (i), ♦ 0 (i)}.

Proof. For a bad position i, we have min{♦ 1 (i), ♦ 0 (i)} ≥ max 1, 1 2 max j=1,...,k (r j (i) -1) .

(V) If i is bad, then C(i) ≥ 1 2 min{♦ 1 (i) + 1, ♦ 0 (i)}.
Proof. Let η := min{♦ 1 (i) + 1, ♦ 0 (i)} ≥ 1. Then i is aligned to at least η 0's and at least η 1's. Thus, by Lemma 5.4,

C(i) ≥ η 2 2η = η 2 .
(VI) For every position i, it holds that

|♦ 0 (i) -♦ 1 (i)| ≤ k and ♦ 0 (i) + ♦ 1 (i) ≥ k.
Proof. For each x j , 1 ≤ j ≤ k, the difference between the number of 0-blocks matched to i and the number of 1-blocks matched to i is at most one. Clearly, there is at least one 0-or 1-block matched to i in each x j .

Cost of a Single Position. We consider a fixed position i of z. For simplification, we write ♦ 0 := ♦ 0 (i), ♦ 1 := ♦ 1 (i), q := q(i), g := g(i), and C := C(i). The goal is to provide a lower bound for C that can be decomposed into the following elements:

• a background cost C back (i) := ♦0 k+1 ,
• a coding cost C code (i) := φ k (q) reflecting the extra cost induced by a matched coding block,

• a gap cost of C gap (i) := 0.01g, which is 0 if i is simple, and which increases with the number of blocks matched to i if i is bad.

Claim 5.7. The cost C of position i is at least LB(♦ 0 , q, g, k), defined as follows:

LB(♦ 0 , q, g, k) := C back (i) + C code (i) + C gap (i) = ♦ 0 k + 1 + φ k (q) + 0.01g.
Proof. In the following, we write LB for LB(♦ 0 , q, g, k). We prove C ≥ LB by case distinction.

For a 0-simple position, by (II), we have ♦ 0 = k and g = 0. Thus,

LB = k k + 1 + φ k (q) + 0 = k + q k + q + 1 = C.
For a 1-simple position, by (III), we have ♦ 0 = 0, q = 0, and g = 0. Thus,

LB = 0 + φ k (0) + 0 = 0 = C.
For a bad position, we have ♦ 0 ≥ 1 and ♦ 1 ≥ 1. First, note that

LB -0.01g = ♦ 0 k + 1 + q (k + q + 1) • 1 (k + 1) ≤ ♦ 0 k + 1 k + 1 ≤ 2 ♦ 0 k , that is, LB ≤ 2 ♦0 k + 0.01g.
We now use this upper bound for the following three sub-cases. First, if ♦ 0 ≤ ♦ 1 , then we have

C ≥ 1 2 ♦ 0 (by (V)) ≥ 2 k ♦ 0 + 0.02♦ 0 (since k ≥ 15)
≥ LB (by (IV)).

Second, if 6 ≤ ♦ 1 < ♦ 0 , we have

C ≥ 1 2 ♦ 1 (by (V)) ≥ 2 + 2 k + 0.02 ♦ 1 (since k ≥ 15 and ♦ 1 ≥ 6) = 2 + 2♦ 1 k + 0.02♦ 1 ≥ 2♦ 0 k + 0.02♦ 1 (since ♦ 0 ≤ ♦ 1 + k by (VI))
≥ LB (by (IV)).

Finally, if ♦ 1 ≤ 5 < ♦ 0 (note that ♦ 1 < ♦ 0 ≤ 5 is not possible since, by (VI), we have ♦ 1 + ♦ 0 ≥ k and we assumed k ≥ 15), then k -5 ≤ ♦ 0 ≤ k + 5 (by (VI)), and g ≤ 10 (by (IV)). We have

C = (♦ 1 + 1)# 0 (i) ♦ 1 + 1 + # 0 (i) ≥ 2(k -5) k -3 ≥ 1.66 using Lemma 5.4, with ♦ 1 ≥ 1, # 0 (i) ≥ ♦ 0 ≥ k -5
, and k ≥ 15. On the other side, we have

LB = ♦ 0 k + 1 + φ k (q) + 0.01g ≤ 5 k + 1 + k k + 1
+ φ k (q) + 0.1 (since ♦ 0 ≤ k + 5 and g ≤ 10)

≤ 5 k + 1.1 (since k k + 1 + φ k (q) ≤ 1) ≤ 1.44 (since k ≥ 15) ≤ C.
This manuscript is for review purposes only. We first introduce some notation: a position i of z is j-coding if there is a coding block b in x j such that b is assigned to i; it is coding if it is j-coding for some j, otherwise it is non-coding. A non-coding position i is free if all positions at distance at most m 2k + 2 from i are non-coding (see Figure 7). We first make the following technical claim before proving the main bound on the coding cost of regular intervals (Claim 5.9).

Claim 5.8. In a regular interval, if two positions i < i are at distance at most 2αm -m 2k for some α, then, for any j, there are at most α j-coding positions in [i, i ].

Conversely, if i and i are at distance at least 2αm + m 2k + 1, then, for any j, there are at least α j-coding positions in [i, i ].

Proof. Claim 5.9. The coding cost of a length-regular interval I is at least

C code (I) ≥ + 1 2mn -2 (c + ε).
Proof. Let I be a regular length-interval. Assume that ≥ 3mn (otherwise the stated lower bound is negative which is trivial).

The first part of the proof consists of splitting interval I into consecutive length-2m segments, each one containing exactly one j-coding position for each j. To this end, a few positions need to be cropped from both ends of I. In other words, we need to find a good starting point (a free position) close to the left end of I.

This manuscript is for review purposes only.

x 1

x 2

x 3 I z i 0 i 1 i 2 i 3 i 4
Fig. 7. Decomposition of a regular interval (I) into segments delimited at positions i l . Coding blocks in x j are indicated with colored bullets, as well as their assigned positions in z (dotted arcs). Position i 0 is free (no coding position within the striped area), and each segment [i l , i l+1 ] contains exactly one j-coding position from each x j . These coding positions correspond to columns of a multiple circular shift of the φ-MSCS input strings. The coding cost of n consecutive segments can be bounded from below by the minimum cost of the φ-MSCS instance.

Consider the first position i of I and position i := i + 2m -m 2k (in I). By Claim 5.8, for any j, there is at most one j-coding position in [i, i ] (and so at most k such coding positions in total). Accordingly, the coding positions split the interval [i, i ] into at most (k + 1) disjoint intervals of non-coding positions, with total size at

least (i -i + 1) -k = 2m -m 2k -k + 1. Hence, there is one interval of non-coding positions in [i, i ] with size at least 2m -m 2k -k + 1 k + 1 ≥ 2m -m 2k k + 1 -1 ≥ m k + 5.
Note that the second inequality above is equivalent to

m(2 -1 2k ) k + 1 ≥ m k + 6 ⇔ m ≥ 6k(k + 1) k -3 2 ,
which is true since m ≥ 1600k and k ≥ 15. Hence, this interval contains a free position, denoted i 0 , with i

+ m 2k + 2 ≤ i 0 ≤ i + 2m -m 2k -2.
Let λ := 2m -2 and i l := i 0 + 2lm for 0 < l ≤ λ. Note that λ ≥ n and that every i l is in I (following the assumption on ).

We fix some input series x j , 1 ≤ j ≤ k. Intuitively, positions i l are the cutting points of our segments within interval I (see Figure 7). We now aim at showing that there is exactly one j-coding position in each segment

[i l-1 , i l -1]. First, consider positions h = i 0 -m 2k -2 and i l -1. By Claim 5.8, since (i l -1) -h = 2lm + m 2k + 1, interval [h, i l - 1
] contains at least l j-coding positions. Since i 0 is free, these coding positions cannot be before i 0 (as

i 0 -h = m 2k + 2), so they are in [i 0 , i l -1]. Consider now positions h = i 0 + m 2k + 1 and i l -1. By Claim 5.8, since (i l -1) -h = 2lm -m 2k ,
there are at most l j-coding positions in [h , i l -1], and therefore at most l j-coding positions in [i 0 , i l -1]. That is, there are exactly l j-coding positions in [i 0 , i l -1].

Overall, there is exactly one j-coding position in [i l-1 , i l -1] for every 0 < l ≤ λ and every j. We write C l,j for the corresponding coding block in x j .

Let q l be the number of B-coding blocks among C l,1 , . . . , C l,k . Then,

i l -1 h=i l-1 q(h) = q l ,
This manuscript is for review purposes only.

and thus

i l -1 h=i l-1 φ k (q(h)) = i l -1 h=i l-1 q(h) (k + q(h) + 1)(k + 1) ≥ i l -1 h=i l-1 q(h) (k + q l + 1)(k + 1) = φ k (q l ).
Let δ j be such that C 1,j is the δ j -th coding block of x j . Then, C l,j is the (δ j +l-1)th coding block of x j , for every 0 < l ≤ λ. Note that the coding blocks C l,1 , . . . , C l,k correspond to the ((l -2) mod n + 1)-th column in the multiple circular shift ∆ = (δ 1 mod n, . . . , δ k mod n) of s 1 , . . . , s k . Thus, q l is the number of B's in this column and φ k (q l ) is the corresponding cost of this column.

That is, for any integer a with 0 < a ≤ λ-n, the sum a+n-1 l=a φ k (q l ) corresponds to the cost of some multiple circular shift of s 1 , . . . , s k . Since, by assumption, every multiple circular shift of s 1 , . . . , s k has cost at least c + ε, we have

a+n-1 l=a φ k (q l ) ≥ c + ε.
We can now compute the lower bound on the coding cost of interval I. To this end, we first extract λ n ≥ 1 length-2mn subintervals of I, each consisting of n segments

of the form [i l-1 , i l -1]. It follows C code (I) = h∈I φ k (q(h)) ≥ i λ -1 h=i0 φ k (q(h)) ≥ λ n -1 a=0 an+n-1 l=an i l -1 h=i l-1 φ k (q(h)) ≥ λ n -1 a=0 an+n-1 l=an φ k (q l ) ≥ λ n -1 a=0 c + ε = λ n (c + ε) ≥ λ n -1 (c + ε) = 2m -2 n -1 (c + ε) ≥ 2m -3 n -1 (c + ε) ≥ + 1 2mn -2 (c + ε),
This manuscript is for review purposes only.

where we assume n ≥ 4 for the last inequality.

Next, we prove a lower bound on the gap cost of an interval I. In the following, the total number of matches between blocks of x 1 , . . . , x k and positions in I is denoted W (I) = i∈I (♦ 0 (i) + ♦ 1 (i)).

Claim 5.10. For any interval I of length , the gap cost C gap (I) fulfills

C gap (I) ≥ 1 100
W (I) k - .
Moreover, if I is irregular, then

C gap (I) ≥ m 400k .
Proof. For the first lower bound, it suffices to note that for any position i (simple or bad), it holds

g(i) ≥ max 1≤j≤k r j (i) -1 ≥ W (i) k -1,
where

W (i) := ♦ 0 (i) + ♦ 1 (i).
For the second lower bound, consider an irregular pair i < i in I and an integer j such that a block b in x j is matched to i and a block b > b in x j is matched to i

where This manuscript is for review purposes only.

|(b -b) -(i -i)| > m 2k . If b -b > i -i + m 2k , then i h=i g(h) ≥ i h=i (r j (h) -1) = i h=i r j (h) -(i -i + 1) ≥ b -b -(i -i) > m 2k > m 4k . If b -b < i -i -m 2k ,
Proof. Consider an interval [α l , β l ], 1 ≤ l ≤ L, and let be its length. Let W := W ([α l , β l ]). Since [α l , β l -1] is a regular interval of length -1, by Claim 5.9, we have the following lower bound on the coding cost:

(5. Since εr > 3mnk + 2(c + ε), we get

F(z) > nmrk k + 1 + rc + 3mnk = c .
This manuscript is for review purposes only.

Since the above reduction is a polynomial-time reduction from φ-MSCS where the resulting number of time series is linear in the number of strings in the φ-MSCS instance, Theorem 5.1 now follows from Theorem 3.11.

Closing this section, we remark that Buchin et al. for all integers p, q ≥ 1. Their reduction, however, builds time series containing three different values. Hence, Theorem 5.1 yields a stronger hardness on binary inputs for p = q = 2. Note that if also the mean is restricted to be a binary time series, then the problem is solvable in polynomial time [START_REF] Brill | Exact mean computation in dynamic time warping spaces[END_REF][START_REF] Schaar | Faster binary mean computation under dynamic time warping[END_REF].

Conclusion.

Shedding light on the computational complexity of prominent consensus problems in stringology and time series analysis, we proved several tight computational hardness results for circular string alignment problems and time series averaging in dynamic time warping spaces. Notably, we have shown that the computational complexity of consensus string problems can drastically change (that is, they become hard) when considering circular strings instead of classic strings. Our results

imply that these problems with a rich set of applications are intractable in the worst case (even on binary data). Hence, it is unlikely to find algorithms which significantly improve the worst-case running times of the best known algorithms. This now partly justifies the use of heuristics as has been done for a long time in many real-world applications.

We conclude with some open questions and directions for future work.

• We conjecture that the idea of the reduction for f -MSCS can be used to prove the same hardness result for most non-linear (polynomially bounded) order-independent cost functions (note that f -MSCS is trivially solvable if f k is linear since every shift has the same cost). Proving a complexity dichotomy with respect to the cost function is a worthwhile goal.

• From an algorithmic point of view, it would be nice to improve the constant in the exponent of the running time for DTW-Mean, that is, to find algorithms running in O(n αk ) time for small α. In particular, we ask to find an O(n k )time algorithm for DTW-Mean.

• What about the parameter maximum sequence length n? Are the considered problems polynomial-time solvable if n is a constant? Are they even fixedparameter tractable with respect to n?

• Finally, can the hardness result for averaging time series with respect to (p, q)-DTW by Buchin et This manuscript is for review purposes only.

3 fi=1 f (s ←δ1 1 [

 31 -MSCS Input:A list of k strings s 1 , . . . , s k ∈ Σ n of length n and c ∈ Q. Question: Is there a multiple circular shift ∆= (δ 1 , . . . , δ k ) ∈ N k with cost f (∆) := n i], . . . , s ←δ k k [i]) ≤ c?Here, s ←δ denotes a circular shift of s by δ (see Section 2 for details). See Figure 1 for an example. We separately study the special case Circular Consensus String for a binary alphabet, where the cost function f : {0, 1} * → N is defined as f ((x 1 , . . . , x k )) := min{ k i=1 x i , k -k i=1 x i }. This corresponds to minimizing the sum of Hamming distances (not the maximum Hamming distance as in Closest

Proof.

  The base cost f k+1 (0) of the solution only depends on the number of columns. Separator values are in weight-(k + 1) columns. Since there are λ of them, it follows that the total local cost of all separator values is λ(k + 1)f (k + 1).The total number of coding values is κ, each coding value has a local weight of f (1) if it belongs to a weight-1 column, and f (2) otherwise (since there is no vertex-or edge-column with weight 3 or more). There are W 2 weight-2 columns, so exactly 2W 2 coding values within weight-2 columns. Summing the base cost with the local costs of all separator and coding values, we get:

Claim 3 . 10 .Theorem 3 . 11 .

 310311 If G does not contain a properly colored k-clique, then there are at most k + k 2 -1 weight-2 columns.Proof. We prove the contrapositive. Assume that there are at least k+ k 2 weight-2 columns. By Claim 3.8, there are at least k weight-2 vertex-columns. By Observation 3.5, only the k vertex-columns of block 1 may have weight 2, hence for each 1 ≤ j ≤ k the column of block 1 with block-index j has weight 2. Thus, for every j,P ∩ V j = ∅.By Claim 3.7, no other block than block 1 may be occupied by two vertices, hence any edge-column with weight 2 must be in block 1, and both endpoints are in P . There cannot be more than k weight-2 vertex-columns, hence there are k 2 weight-2 edge-columns, and for each of these there exists a distinct edge with both endpoints in P . Thus, P is a properly colored k-clique.Cliques and CircularShifts with Low Cost. We are now ready to complete the proof of Lemma 3.3. First, assume that G contains a properly colored k-clique P = {v 1,i1 , . . . , v k,i k }. Consider the multiple circular shift ∆ = (δ 0 , . . . , δ k ), where δ 0 = 0 and δ j := (i j -1)(m + 1)(γ + j + 1) for j ∈ {1, . . . , k}. Note that |P | = k, and all edge-columns in block 1 corresponding to edges induced in P have weight 2. Hence there are k 2 weight-2 edge-columns and k weight-2 vertex-columns. By Claim 3.9, cost f (∆) = c. Now, assume that G does not contain a properly colored k-clique. Let ∆ = (δ 0 , . . . , δ k ) be a multiple circular shift with δ 0 = 0 (recall that we can assume this without loss of generality). Clearly, if δ j mod (m +1) = 0 for some j, then cost f (∆) ≥ c + ε (by Claim 3.4). Otherwise, by Claim 3.10 there are at most k + k 2 -1 weight-2 columns. By Claim 3.9 , cost f (∆) ≥ c + ε. This completes the proof of Lemma 3.3 which directly leads to our main result of this section. Let f be a polynomially bounded grouping function. Then, f -MSCS on binary strings is (i) NP-hard, (ii) W[1]-hard with respect to the number k of input strings, and (iii) not solvable in ρ(k) • n o(k) time for any computable function ρ unless the ETH fails. Proof. The polynomial-time reduction from Lemma 3.3 yields the NP-hardness. Moreover, the number of strings in the f -MSCS instance only depends on the size of the multicolored clique. Hence, it is a parameterized reduction from RMCC parameterized by the size of the clique to f -MSCS parameterized by the number of input strings and thus yields W[1]-hardness. Lastly, the number k = k + 1 of strings is linear in the size k of the clique. Thus, any ρ(k ) • n o(k ) -time algorithm for DTW-Mean would imply a ρ (k) • |V | o(k) -time algorithm for RMCC, contradicting the ETH. Note that Theorem 3.11 holds for the function σ since it is a polynomially bounded grouping function (as discussed earlier).The assumption that f is polynomially bounded is only needed to obtain a polynomial-time reduction in Lemma 3.3. Without this assumption, we still obtain a parameterized reduction from RMCC parameterized by the clique size to f -MSCS parameterized by the number of input strings, which yields the following corollary for a larger class of functions.

Theorem 4 . 1 .

 41 Circular Consensus String on binary strings is (i) NP-hard, (ii) W[1]-hard with respect to the number k of input strings, and (iii) not solvable in ρ(k) • n o(k) time for any computable function ρ unless the ETH fails.

Fig. 4 .

 4 Fig. 4. Reduction from an instance of g-MSCS (left) to an instance of f CS -MSCS, which is equivalent to the Circular Consensus String problem. Plots of the (polynomially bounded and order-independent) local cost functions for k = 4 are shown. Note that g 4 is obtained from f CS 6 by cropping the first two values in order to become grouping.

Theorem 5 . 1 .

 51 DTW-Mean on binary time series is (i) NP-hard, (ii) W[1]-hard with respect to the number k of input series, and (iii) not solvable in ρ(k) • n o(k) time for any computable function ρ unless the ETH fails.

Fig. 5 . 1 6

 51 Fig. 5. Left: The function φ 5 (x) = x 6(6+x) . Right: The function φ 5 (x) = 1 6(6+x) .

(here with r = 3 )Fig. 6 .

 36 Fig. 6. Top left: Illustration of the reduction to DTW-Mean from an instance of φ-MSCS with k = 3 and n = 5. An optimal circular shift ∆ = (3, 2, 4) is indicated by dotted lines, and the number of B's in a shifted column is below each column. The total cost is cost φ (∆) = 2φ 3 (1)+2φ 3 (3)+φ 3 (0). Top right: The intermediate strings s 1 , s 2 , s 3 encoding the original strings s 1 , s 2 , s 3 . Bottom: The resulting instance x 1 , . . . , x 4 of DTW-Mean (only coding blocks are shown) and an alignment to a time series z mimicking the circular shift ∆. The values of z are shown along with the cost of each position (positions that are only aligned to non-coding blocks are ignored, and contribute a background cost of either 0 or 3 4). Note that the cost function φ is chosen so that the cost of a position aligned to k coding blocks equals the cost of the corresponding column of the original circular shift (plus the background cost3 4 ). For example, a position aligned to two A-coding blocks and one B-coding block has cost4 5 = 3 4 + φ 3 (1), where φ 3 (1) is the cost of a column with two A's and one B in φ-MSCS. The value of m is chosen large enough to yield a large cost for misalignments, such as two consecutive coding blocks of the same series aligned together. The value of r is chosen such that only a periodic pattern ensures low cost of z, even though it requires to pay a high (but bounded) misalignment cost for the first and last positions.

Lemma 5 . 4 .

 54 For any a ≥ a ≥ 0 and b ≥ b ≥ 1, it holds ab a+b ≥ a b a +b . Proof. It suffices to see that the partial derivatives ∂ ∂a ab a + b = b 2 (a + b) 2 and ∂ ∂b ab a + b = a 2 (a + b) 2 are non-negative for a ≥ 0 and b ≥ 1.

  Cost of (Ir)regular Intervals. We aim at computing lower bounds on the cost of intervals of positions. Two positions i, i of the mean z at distance |i -i | = form an irregular pair if for some x j a block b is matched to i and a block b is matchedto i such that either |b -b | ≤ -m 2k or |b -b | ≥ + m 2k . An interval I ofpositions in z is called regular if it does not contain any irregular pair (otherwise it is called irregular ). The background, coding, and gap cost of I is the sum of the respective costs of its positions. The structure of regular intervals allows us to bound the coding cost from below using the minimum cost of the original φ-MSCS instance. Irregular intervals contain bad positions, which allow us to derive a lower bound on their gap cost.

  Fix j ∈ {1, . . . , k} and consider the first block b in x j matched to i and the last block b in x j matched to i (then b ≥ b). Note that all j-coding positions in [i, i ] have been assigned a distinct coding block in [b, b ]. Since i and i are not an irregular pair, it holds that b -b < i -i + m 2k ≤ 2αm. That is, b < b + 2αm, and thus x j contains at most α coding blocks in [b, b ]. These coding blocks are assigned to positions in [i, i ]. Hence, [i, i ] contains at most α j-coding positions. For the other direction, consider again blocks b and b as above. In this case there is a slight difference: If block b or b is coding, then it might be assigned to a coding position outside of the interval [i, i ], which then would not count in the lower bound. Thus, we consider only blocks strictly between b and b , among which all coding blocks are assigned to a coding position in [i, i ]. Since i -i ≥ 2αm + m 2k + 1, we have b -b > i -i + m 2k ≥ 2αm + 1, so there are at least 2αm blocks strictly between b and b , including at least α coding blocks. These are assigned to at least α j-coding positions in [i, i ].

Claim 5 . 11 .

 511 then there are at least m 2k pairs of consecutive positions having the same block in x j matched to them, and for every such pair at least one of the two positions is bad (by Observation 5.6). Since any bad position may be counted in at most two such pairs, the interval has at least m 4k bad positions. Hence, using g(h) ≥ 1for bad positions, we obtaini h=i g(h) ≥ m 4k .Cost of a Mean. To obtain a lower bound for F(z), we now partition the positions[1, |z|] into minimal irregular intervals (from left). To this end, let α 1 := 1 and let β 1 be the position such that the interval [α 1 , β 1 ] is irregular (if such a position does not exist, then β 1 := |z|) and [α 1 , β 1 -1] is regular. If β 1 < |z|, then we continue analogously and define α 2 := β 1 + 1 and β 2 to be the position such that [α 2 , β 2 ] is irregular and [α 2 , β 2 -1] is regular. This procedure is repeated until we obtain a partition [α 1:= 1, β 1 ], [α 2 := β 1 + 1, β 2 ], . . . , [α L := β L-1 + 1, β L := |z|]of[1, |z|] into L ≥ 1 intervals of which the first L -1 are irregular and the last is possibly regular. The following lower bounds hold. For 1 ≤ l < L, it holds thatC gap ([α l , β l ]) + C code ([α l , β l ]) ≥ (c + ε) W ([α l , β l ]) 2knm .For the coding and gap costs of [α L , β L ], it holds thatC gap ([α L , β L ]) + C code ([α L , β L ]) ≥ (c + ε) W ([α L , β L ]) 2knm -2(c + ε).

1 )+ 1 .

 11 C code ([α l , β l ]) ≥ C code ([α l , β l -1]) ≥ 2mn -2 (c + ε).For l < L, we combine both bounds on the gap cost of Claim 5.10 (by averaging their values):C gap ([α l , β l ])Using m ≥ 1600k(c + ε) (by definition) and m ≥ 100 c+ε n , we obtain(5.2) C gap ([α l , β l ]) ≥ c + ε 2nm W k -+ 2(c + ε).The sum of Inequations 5.1 and 5.2 yields the claimed lower bound.For interval [α L , β L ], we use the general lower bound from Claim 5.10, which yields(5.3) C gap ([α L , β L ])The sum of Inequations 5.1 and 5.3 yields the claimed lower bound.Finally, to finish the proof of Theorem 5.1, we show that the mean z has high cost, that is, (x 1 , . . . , x k+1 , c ) is a no-instance of DTW-Mean. Claim 5.12. F(z) > c . Proof. Using Claim 5.7 on each position of I := [1, |z|], we obtain the following lower bound F(z) = |z| i=1 C(i) ≥ C code (I) + C gap (I) + C back (I).For the coding and gap cost of I, we use Claim 5.11 together with the fact that all 2knmr blocks of x 1 , . . . , x k are involved in at least one match with a position of z,which yields W (I) = L l=1 W ([α l , β l ]) ≥ 2knmr. Thus, C code (I) + C gap (I) ≥ (c + ε)r -2(c + ε).The overall background cost is C back (I) = |z| i=1 ♦0(i) k+1 . Since overall there are knmr 0-blocks in x 1 , . . . , x k , and each of those is matched to at least one position of z, we have |z| i=1 ♦ 0 (i) ≥ knmr and thus C back (I) ≥ nmrk k Combining the two bounds above yields C code (I) + C gap (I) + C back (I) ≥ nmrk k + 1 + (c + ε)r -2(c + ε).

[ 8 ,

 8 Theorem 7] recently obtained the same hardness results as in Theorem 5.1 for the problem of computing an average series z that minimizes∈P |x j |,|z| (u,v)∈pj |x j [u] -z[v]| p

  Then, f -MSCS on binary strings is W[START_REF] Abboud | Tight hardness results for LCS and other sequence similarity measures[END_REF]-hard with respect to the number k of input strings and not solvable in ρ(k) • n o(k) time for any computable function ρ unless the ETH fails. A list of k strings s 1 , . . . , s k ∈ Σ n of length n and c ∈ Q.Question: Is there a string s * ∈ Σ n and a multiple circular shift (δ 1 , . . . , δ k ) such thatHere, d denotes the Hamming distance, that is, the number of mismatches between the positions of two strings. Although consensus string problems in general have been widely studied from a theoretical point of view[START_REF] Bulteau | Multivariate algorithmics for NP-hard string problems[END_REF], somewhat surprisingly this is not

	4. Circular Consensus String. In this section we briefly study the Circular
	Consensus String problem:
	Circular Consensus String (SCC)
	Input:
	k j=1 d(s ←δj j	, s

* ) ≤ c? the case for the circular version(s). For CCS, only an O(n 2 log n)-time algorithm for k = 3 and an O(n 3 log n)-time algorithm for k = 4 is known

[START_REF] Lee | Finding consensus and optimal alignment of circular strings[END_REF]

. However, for general k no hardness result is known. Note that without circular shifts the problem is solvable in linear time: It is optimal to set s * [i] to any element that appears a maximum number of times among the elements s 1 [i], . . . , s k [i].

  al. [8, Theorem 7] be strengthened to binary inputs? k-means-based clustering for temporal data under weighted and kernel time warp, Pattern Recognition Letters, 75 (2016), pp. 63-69. [37] S. Will and P. F. Stadler, A common framework for linear and cyclic multiple sequence alignment problems, in Proceedings of the 14th International Workshop on Algorithms in Bioinformatics (WABI '14), vol. 8701 of LNCS, Springer, 2014, pp. 135-147.

We cast all problems in this work as decision problems for easier complexity-theoretic treatment. Our hardness results correspondingly hold for the associated optimization problems.

For instance, Petitjean et al.[START_REF] Petitjean | Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm[END_REF] write "Computational biologists have long known that averaging under time warping is a very complex problem, because it directly maps onto a multiple sequence alignment: the "Holy Grail" of computational biology." Unfortunately, the term "directly maps" has not been formally defined and only sketchy explanations are given.This manuscript is for review purposes only.

This manuscript is for review purposes only.

Acknowledgments. We are very grateful to two anonymous reviewers of SIAM Journal on Discrete Mathematics whose very detailed and constructive feedback helped to improve the presentation of the paper significantly.