F S Évellec

A C Naveira Garabato

T Huck

Damping of climate-scale oceanic variability by mesoscale eddy turbulence

The impact of mesoscale eddy turbulence on long-term, climatic variability in the ocean's buoyancy structure is investigated using observations from a mooring deployed in the Drake Passage, Southern Ocean. By applying the Temporal-Residual-Mean framework and characterizing the variance contributors and the buoyancy variance budget, we identify the main source and sink of long-term buoyancy variance. Long-term buoyancy variance amplitude is set by long-term vertical velocity fluctuations acting on the steady stratification. This baroclinic buoyancy flux is also the main source of the variance, indicative of the effect of largescale baroclinic instability. This source is balanced by a sink of long-term buoyancy variance associated with the vertical advection of the steady stratification by the eddy-induced circulation. We conclude that mesoscale eddy turbulence acts as a damping mechanism for long-term, climatic variability in the region of the observations, consistent with an 'eddy saturated' behaviour of the Antarctic Circumpolar Current.

Introduction

Mesoscale eddy turbulence is ubiquitous in the ocean [START_REF] Wunsch | Ocean Observations and the Climate Forecast Problem[END_REF][START_REF] Chelton | Global observations of large oceanic eddies[END_REF]. It has long been hypothesized, and ultimately established, that this turbulence has significant impacts on the basin-scale ocean circulation, especially in the Southern Ocean (Gnanadesikan and [START_REF] Gnanadesikan | On the Relationship of the Circumpolar Current to Southern Hemisphere Winds in Coarse-Resolution Ocean Models[END_REF]. While there is a vibrant discussion on the mechanistic nature of the eddies' role [START_REF] Phillips | Eddy Variability and Energetics from Direct Current Measurements in the Antarctic Circumpolar Current South of Australia[END_REF][START_REF] Hallberg | An Exploration of the Role of Transient Eddies in Determining the Transport of a Zonally Reentrant Current[END_REF][START_REF] Meredith | Circumpolar response of Southern Ocean eddy activity to a change in the Southern Annular Mode[END_REF][START_REF] Danabasoglu | Effects of vertical variations of thickness diffusivity in an ocean general circulation model[END_REF][START_REF] Smith | A study of the sensitivity of ocean overturning circulation and climate to freshwater input in different regions of the North Atlantic[END_REF][START_REF] Gent | Response to Increasing Southern Hemisphere Winds in CCSM4[END_REF][START_REF] Thompson | Equilibration of the Antarctic Circumpolar Current by Standing Meanders[END_REF][START_REF] Sinha | Time Scales of Southern Ocean Eddy Equilibration[END_REF][START_REF] Marshall | Eddy saturation and frictional control of the Antarctic Circumpolar Current[END_REF], it is now widely accepted that eddy turbulence is central to several fundamental features of the time-mean ocean circulation, such as the inter-basin meridional overturning [START_REF] Nikurashin | A Theory of the Interhemispheric Meridional Overturning Circulation and Associated Stratification[END_REF]. This has recently been corroborated in local observations in the Southern Ocean [START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF]. However, no consensus exists on the eddies' effect on the ocean's climatic (i.e., interannual-and longer-time scale) variability (e.g., [START_REF] Huck | Multidecadal variability of the overturning circulation in presence of eddy turbulence[END_REF]Sérazin et al., 2018), with eddies having been argued to either enhance or suppress such variability. Settling this debate is a foremost outstanding challenge of the climate science community.

The debate on the role of mesoscale eddy turbulence in modulating oceanic variability on climatic time scales entails two opposing views. On the one hand, several studies have shown that the transfer of surface kinetic energy (or of velocity variance) exhibits an inverse cascade [START_REF] Arbic | Geostrophic turbulence in the frequency-wavenumber domain: Eddy-driven low-frequency variability[END_REF][START_REF] Sérazin | Intrinsic variability of sea level from global ocean simulations: Spatiotemporal scales[END_REF]Sérazin et al., , 2018)), implying that eddies are a source of long-term variability. On the other hand, mesoscale eddy turbulence is often represented as a sink of variance [START_REF] Gent | Isopycnal mixing in ocean circulation model[END_REF], whereby relatively small-scale baroclinic instability grows on a large-scale density front and induces a flattening of frontal isopycnals.

The apparent discrepancy between these two views might stem from their adoption of fundamentally different approaches to describe the system, based on either the ocean's momentum budget (for the first view) or the buoyancy budget (for the second view), as suggested by 1 10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020

Accepted for publication in Journal of Physical Oceanography. DOI the pioneering work on oceanic turbulence of [START_REF] Rhines | The Dynamics of Unsteady Currents[END_REF] and [START_REF] Salmon | Two-layer quasi-geostrophic turbulence in a simple special case[END_REF]Salmon ( , 1980)).

Despite its academic appearance, this debate has fundamental operational repercussions -for example, in the realm of interannual climate prediction. At present, climate projections are still provided by climate models incorporating eddy-less ocean models (i.e., ocean models where eddies are not resolved explicitly but only parameterized, [START_REF] Taylor | An overview of CMIP5 and the experiment design[END_REF].

However, these models are seemingly too noisy to provide reliable interannual climate projections, an occurrence known as the signal-to-noise paradox of interannual climate prediction [START_REF] Scaife | A signal-to-noise paradox in climate science[END_REF][START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF]. This calls for clarification of the role of mesoscale eddy turbulence. Is it a further source of noise, degrading even more the reliability of interannual climate prediction? Or is it a damping mechanism, which needs to be accurately incorporated to improve predictive skill?

In this study, we directly assess the effect of eddies on the ocean's interannual variability by analysing measurements from a 2-year-long mooring deployment in a hotspot of eddy activity within the Antarctic Circumpolar Current (ACC). Our approach is based on the Temporal-Residual-Mean (TRM) framework [START_REF] Mcdougall | The Temporal-Residual-Mean Velocity. Part II: Isopycnal Interpretation and the Tracer and Momentum Equations[END_REF], and involves the formulation of the local buoyancy variance budget in a way that distinguishes between mesoscale eddy fluctuations and 'long-term' (i.e., with periods longer than those of eddies) variability. This enables us to quantify the intensity, and characterize the sources and sinks, of long-term buoyancy variance. We find that the main source of long-term buoyancy variance is the vertical advection of time-mean stratification by the fluctuating long-term circulation, whereas mesoscale eddies provide the primary sink of long-term buoyancy variance. Thus, we show that eddies suppress variations of the ACC density structure by restoring it to its mean state in the area of the observations. The manuscript is organized as follows. The observational data are described in section 2.

Section 3 presents our methodology, including the TRM framework, the calculation of vertical velocity with single-mooring measurements, and the formulation and implementation of the Conclusions are included within this last section.

Data

We analyse in situ observations acquired by a mooring deployed within the ACC, at 56 • S, 57 • 50 W in the Drake Passage (Fig. 1a) under the auspices of the Diapycnal and Isopycnal Mixing Experiment in the Southern Ocean (DIMES, Naveira Garabato, 2010;[START_REF] Meredith | Cruise report: RRS James Cook JC054[END_REF]. This location lies over a topographic feature and equatorward of the strongest ACC flow (for details of the exact location, see [START_REF] Brearley | Eddy-induced modulation of turbulent dissipation over rough topography in the Southern Ocean[END_REF]. The mooring considered here is the central mooring of the DIMES array, which was deployed for over 2 years between 12 December 2009 and 5 March 2012. The mooring contains conductivity-temperature-depth (CTD) instrumentation and current meters spanning the depth range between 1,200 m and 3,600 m, with a cluster around 2,000 m at a resolution of 100 m (Tab. 1). The observational data sets are those used in [START_REF] Brearley | Eddy-induced modulation of turbulent dissipation over rough topography in the Southern Ocean[END_REF] and [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF][START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF], and a detailed quality control of the measurements is given in [START_REF] Brearley | Eddy-induced modulation of turbulent dissipation over rough topography in the Southern Ocean[END_REF]. The data are linearly interpolated onto constant pressure levels spaced by 100 dbar (other interpolating methods for mooring motion correction were tested, and found to induce quantitative changes in our diagnostics of less than 5%) with a temporal resolution of 15 minutes. We refer the reader to [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF] for a thorough estimation of measurement uncertainty.

Finally, density and depth are computed using the Gibbs -SeaWater Oceanographic toolbox [START_REF] Mcdougall | Getting started with TEOS-10 and the Gibbs Seawater (GSW) Oceanographic Toolbox[END_REF].

From these observations, vertical velocities can be inferred, and the terms of a time-mean buoyancy budget can be diagnosed. The method to compute vertical velocities from singlemooring measurements is described in [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF]; the mean statistical properties of the observational record are shown in Figs. 1b-g. Taking advantage of the equivalentbarotropic nature of the ACC flow [START_REF] Killworth | The Antarctic Circumpolar Current as a free equivalent-barotropic jet[END_REF], we define gradients in the Accepted for publication in Journal of Physical Oceanography. DOI along and across directions of the time-and depth-mean flow (as indicated in Fig. 1a). This enables us to eliminate contributions to the buoyancy budget from the time-mean flow in the across direction (Fig. 1c), except for a small baroclinic component.

Method

a. Temporal-Residual-Mean framework

We formulate the buoyancy variance budget of the study area within the Temporal-Residual-Mean framework [START_REF] Mcdougall | The Temporal-Residual-Mean Velocity. Part II: Isopycnal Interpretation and the Tracer and Momentum Equations[END_REF]. Starting from the evolution of buoyancy under negligible diffusion (Pe 1, where Pe is the Péclet number measuring the ratio of advection to diffusion), we have:

D t b = 0, ( 1
)
where t is time, b is buoyancy, and D t is the material derivative. This derivative can be expanded as D t =∂ t +u∂ x +v∂ y +w∂ z , where x and y are the horizontal units for the along and across the time-and depth-mean flow directions, respectively; z is the vertical unit; u and v are the horizontal velocities for the along and across directions, respectively; and w is the vertical velocity.

To explicitly distinguish short-term (shorter than an arbitrary time scale τ ) fluctuations from longer-term variability, we define X= X+X , where X represents any variable (e.g., b, u, v, or w), X(z, t)= Accepted for publication in Journal of Physical Oceanography. DOI the directions along and across the time-and depth-mean flow direction, respectively; and ŵ is the residual vertical velocity. The modified buoyancy is b= b+ b, where b=-∂ z ( φ/N 2 ) is the re-scaled buoyancy variance with φ=b 2 /2, and N 2 =∂ z b is the squared Brunt-Väisälä frequency. The residual velocities are û=ū+ũ, v=v+ṽ, and ŵ= w+ w, where ũ and ṽ are the eddy-induced velocities for the along and across directions, respectively; and w is the eddyinduced vertical velocity. In the TRM framework, the horizontal eddy-induced velocities

t+ τ 2 t-τ 2 X(z,
read ũ = ∂ z -u b + φ N 2 ∂ z ū N 2 , ( 3a
)
and

ṽ = ∂ z -v b + φ N 2 ∂ z v N 2 . ( 3b
)
To avoid confusion with the classical TRM literature, it is important to note that we use different notations to, for instance, [START_REF] Mcdougall | The Temporal-Residual-Mean Velocity. Part II: Isopycnal Interpretation and the Tracer and Momentum Equations[END_REF]. For the purpose of exactness, [START_REF] Mcdougall | The Temporal-Residual-Mean Velocity. Part II: Isopycnal Interpretation and the Tracer and Momentum Equations[END_REF] used different symbols to reflect the effects of different operators. Specifically, eddy-induced velocities and re-scaled buoyancy variance were expressed with distinct symbols in that work, since they were derived from two different operators. Here, without loss of accuracy, we choose a different approach. We refer to variables associated with eddy turbulent dynamics with a single symbol (˜), and to variables corrected from the eddy turbulent dynamics with a different symbol (ˆ), regardless of the actual operators leading to each term. This allows for more compact, simplified formulations.

Such an approach was already proposed in [START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF], to which the present study is a natural follow-up.

To compute the variance of long-term fluctuations (i.e., fluctuations on time scales longer than τ ), we can further decompose the time-averaged variables ( X) into steady ( X ) and fluctuating ( X ) components, such as X= X + X , with X (z)=

t f -τ 2 t i + τ 2 X(z, t)dt/ (t f -t i -τ ).
Using this time averaging, we can compute the temporal variance of the filtered modified buoyancy for different time filters, as σ 2 τ = b 2 . Taking the derivative with respect to the Accepted for publication in Journal of Physical Oceanography. DOI averaging time scale of this variance (∂ τ σ 2 τ ) yields the time-varying contribution of each time scale to the modified buoyancy variance (Fig. 2). This diagnostic shows that an important part of the modified buoyancy variance is contained in the super-and near-inertial regime (Fig. 2). However, although the contribution of this frequency range to variance is very high at any given time, its restricted spectral span (from 15 minutes to 1 day) makes it a negligible contributor to the total variance computed over the 2-year time scale of the observations.

On this time scale, the dominant contribution to the variance is linked to the mesoscale eddy regime (1-100 days).

Having decomposed buoyancy into short-term fluctuations (b ), long-term fluctuations ( b ), and a steady component ( b ), we find that, while the steady component is independent of τ , the short-and long-term fluctuations obviously depend on τ . In the remainder of this work, we set τ to 100 days, so that short-term fluctuations correspond to mesoscale eddy motions, and long-term fluctuations correspond to longer-time scale variability, following our previous analysis of the buoyancy variance (Fig. 2) and recent works by [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF][START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF].

It is important to remind the reader that, despite the compact form of the equations within the TRM framework, as e.g., in (2), it remains possible to decompose all terms in order to trace back the individual contributions of short-or long-term fluctuations. We will subsequently take advantage of this property to assess the relative roles of short-and long-term fluctuations in determining the long-term buoyancy variance.

b. Computation of vertical velocity

To estimate the balances in (1)-( 2 Accepted for publication in Journal of Physical Oceanography. DOI (Ro 1) and hydrostatic balance. This set of equations reads

∂ t u -f v = - 1 ρ 0 ∂ x P, (4a)
∂ t v + f u = - 1 ρ 0 ∂ y P, (4b)
∂ z P = ρ 0 b, ( 4c
)
where P is pressure; f is the Coriolis parameter; Re is the Reynolds number, which measures the ratio of inertial to viscous forces; and Ro is the Rossby number, which measures the ratio of inertial forces to the Coriolis acceleration. After algebraic manipulation, we obtain

∂ x b = -∂ t ∂ z u + f ∂ z v, (5a)
∂ y b = -∂ t ∂ z v -f ∂ z u. ( 5b
)
Since u and v are known at all times and as a function of depth, both along and across buoyancy gradients can be evaluated from the mooring.

Finally, vertical velocity is obtained with (1) and ( 5), such as:

w = - ∂ t b N 2 + f N 2 (v∂ z u -u∂ z v) + 1 N 2 (u∂ t ∂ z u + v∂ t ∂ z v) . (6)
This method closely follows the study of [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF], to which we refer the reader for further details. [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF] demonstrate the validity of the assumptions adopted here (in particular, Ro 1 along the vertical), and the consistency of the leadingorder balance of the equations with quasi-geostrophy, which is a widely used approximation in studying mesoscale turbulence. Errors in derived variables were also estimated by those authors, and confirm the accuracy of the method.

Following the same logic, the eddy-induced vertical velocity can be diagnosed using (2),

following [START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF], as:

w = -w - ∂ t b N 2 - û∂ x b + v∂ y b N 2 , ( 7
)
where N 2 =∂ z b is the modified stratification.

Accepted for publication in Journal of Physical Oceanography. DOI

c. Buoyancy variance budget and contributors

Now that the modified buoyancy and residual velocities have been defined, we can look at their temporal evolution across the 2-year mooring record, at all depths (Fig. 3). All the time series display substantial variations. For the buoyancy, these variations are intensified in the upper part of the mooring, between 1,200 m and 1,800 m, and decrease with depth with the same sign signature over the vertical. This is expected from the equivalent-barotropic structure of the ACC flow [START_REF] Killworth | The Antarctic Circumpolar Current as a free equivalent-barotropic jet[END_REF]. For the horizontal velocities, variations peak at 10 cm s -1 , a value comparable to the time-mean velocities. In relative terms, variations are stronger for the across velocities (with frequent sign reversals) than for the along velocities. For the vertical velocities, variations peak around 0.5 mm s -1 , and are intensified around 2,000 m with opposing velocities above and below this depth.

Since all aspects of buoyancy variability can be determined from a single mooring, we re-visit (2) with the aim of identifying the sources and sinks of such variability. With this purpose, we apply a Reynolds decomposition using an Eulerian time averaging. We decompose all terms into steady ( X ) and fluctuating ( X ) components, and find that the steady component is controlled by the equation:

∂ t b + û ∂ x b + v ∂ y b + ŵ ∂ z b = -û ∂ x b -v ∂ y b -ŵ ∂ z b . ( 8
)
This form of the mean buoyancy balance was applied and examined by [START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF].

We Accepted for publication in Journal of Physical Oceanography. DOI

1) Buoyancy Variance Budget

From ( 2) and ( 8), we can express the temporal evolution of the long-term fluctuations of buoyancy as

∂ t b + û ∂ x b + v ∂ y b + ŵ ∂ z b + û ∂ x b + v ∂ y b + ŵ ∂ z b = -û ∂ x b -v ∂ y b -ŵ ∂ z b + û ∂ x b + v ∂ y b + ŵ ∂ z b . (9)
Multiplying this equation by 2 b , we derive the time-evolving budget of long-term buoyancy variance estimated from low-pass filtered residual fields

∂ t b 2 = -2 û b ∂ x b -2 v b ∂ y b -2 ŵ b ∂ y b -2 û b ∂ x b -2 v b ∂ y b -2 ŵ b ∂ z b -2 û b ∂ x b -2 v b ∂ y b -2 ŵ b ∂ z b . (10)
The budget of long-term buoyancy variance is found to be controlled by three components:

the steady velocity term (Bud-SV, corresponding to the right hand side of the first line), the steady buoyancy term (Bud-SB, corresponding to the second line), and the turbulent long-term fluctuation term (Bud-TL, corresponding to the third line). Each component can be further decomposed into contributions from each of the three directions (along, across, and vertical), such as e.g., Bud-SV=Bud-SV x +Bud-SV y +Bud-SV z . The time-evolving form of the buoyancy variance budget synthesized in (10) will be especially useful in determining sources and sinks of long-term buoyancy variance. This method of computing the buoyancy variance budget has been applied in a range of studies to describe oceanic variability [START_REF] Sévellec | On the mechanism of centennial thermohaline oscillations[END_REF][START_REF] Arzel | The different nature of the interdecadal variability of the thermohaline circulation under mixed and flux boundary conditions[END_REF][START_REF] Buckley | On the relationship between decadal buoyancy anomalies and variability of the Atlantic meridional overturning circulation[END_REF].

2) Buoyancy Variance Contributors

In order to determine the overall (i.e., integrated over the entire mooring record

= b t 1 - t t 1 û ∂ x b ds - t t 1 v ∂ y b ds - t t 1 ŵ ∂ z b ds - t t 1 û ∂ x b ds - t t 1 v ∂ y b ds - t t 1 ŵ ∂ z b ds - t t 1 û ∂ x b ds - t t 1 v ∂ y b ds - t t 1 ŵ ∂ z b ds + û ∂ x b + v ∂ y b + ŵ ∂ z b (t -t 1 ) + u ∂ x b + v ∂ y b + w ∂ z b (t -t 1 ) . ( 11
)
Multiplying this equation by b , we derive a decomposition of the long-term buoyancy variance within the TRM framework in terms of its contributors:

b 2 = -û b t t 1 ∂ x b ds -v b t t 1 ∂ y b ds -ŵ b t t 1 ∂ z b ds -b t t 1 û ds ∂ x b -b t t 1 v ds ∂ y b -b t t 1 ŵ ds ∂ z b -b t t 1 û ∂ x b ds -b t t 1 v ∂ y b ds -b t t 1 ŵ ∂ z b ds + û ∂ x b + v ∂ y b + ŵ ∂ z b b t . ( 12
)
Following the decomposition principle used for the time-evolving budget of long-term buoyancy variance in (10), we define three distinct contributors: the steady velocity term (Var-SV, corresponding to the right hand side of the first line), the steady buoyancy term (Var-SB, corresponding to the second line), and the turbulent long-term fluctuation term (Var-TL, corresponding to the third and fourth lines). Also, as before, each component is further decomposed into contributions from each of the three directions, such as e.g., Var-SV=Var-SV x +Var-SV y +Var-SV z .

Results

The first important result of our TRM framework-based analysis of the long-term buoyancy variance is that both the time-evolving variance budget and the decomposition into overall 10 10.1175/JPO-D-20-0141.1.

Accepted for publication in Journal of Physical Oceanography. DOI variance contributors [given by ( 10) and ( 12), respectively] have negligible closure errors (Fig. 4). This endorses the robustness of our proposed formulations of the variance budget and of the variance contributors, and their subsequent application to the mooring data.

The long-term buoyancy variance contributor analysis (Fig. 5) shows that the two most important terms at all depths are the along advection of long-term buoyancy fluctuations by the steady velocity (Var-SV x ) and the across advection of steady buoyancy by long-term velocity fluctuations (Var-SB y ). The Var-SV x term makes a positive contribution to the total variance, whereas the Var-SB y term makes a negative contribution. The two terms compensate one another almost perfectly, and thereby exert a negligible joint impact on the long-term buoyancy variance. This result is consistent with the non-Doppler-shifted effect expected from the passage of large-scale Rossby waves [START_REF] Rossby | Relation between variations in the intensity of the zonal circulation of the atmosphere and the displacements of the semi-permanent centers of action[END_REF][START_REF] Held | Stationary and quasi-stationary eddies in the extratropical troposphere: Theory[END_REF][START_REF] Killworth | The speed of observed and theoretical long extratropical planetary waves[END_REF][START_REF] Sévellec | The leading, interdecadal eigenmode of the Atlantic meridional overturning circulation in a realistic ocean model[END_REF] The time-evolving budget of long-term buoyancy variance, which allows us to distinguish between sources and sinks of variance (Fig. 6), shows that the main balance is established between three terms: the along advection of long-term buoyancy fluctuations by the steady flow (Bud-SV x ), the across advection of steady stratification by long-term velocity fluctuations (Bud-SB y ), and the vertical advection of steady stratification by long-term velocity fluctuations (Bud-SB z ). This indicates that Bud-SV x and Bud-SB y act as upper and deeper sources of long-term buoyancy variance, respectively, whereas Bud-SB z provides a sink.

We may now effect a further decomposition of these three leading terms, in order to evaluate the role of short-term mesoscale eddy turbulence in energising or damping longterm buoyancy variance. With this purpose, we exploit a convenient property of the TRM framework, within which the respective roles of short-and long-term fluctuations can be traced back by splitting the modified buoyancy into the Eulerian time-mean buoyancy and the re-scaled buoyancy variance, and by partitioning the residual velocities into the Eulerian time-mean velocities and the eddy-induced velocities (as defined in section 3a.). This decomposition reads:

Bud-SV x = -2 û b ∂ x b , = -2 û b ∂ x b + b ∂ x b + b ∂ x b + b ∂ x b , = B L ∆ L + B L ∆ S + B S ∆ L + B S ∆ S , (13a)
Bud-SB y = -2 v b ∂ y b , = -2 v b + v b + ṽ b + ṽ b ∂ y b , = V L B L + V L B S + V S B L + V S B S , (13b
= W L B L + W L B S + W S B L + W S B S . (13c)
Applying this decomposition to our data (Fig. 7) reveals that, while all terms within Bud- and act as a baroclinic conversion between eddy potential energy and eddy kinetic energy, consistent with the occurrence of baroclinic instability [START_REF] Harrison | Energy analysis of open regions of turbulent flows: mean eddy energetics of a numerical ocean circulation experiment[END_REF][START_REF] Marchesiello | Equilibrium Structure and Dynamics of the California Current System[END_REF].

To conclude, it is interesting to note that a buoyancy variance budget of the short-term buoyancy variance (not shown) reveals that the main sink of long-term buoyancy variance

Conclusion

Oceanic variability on interannual and longer time scales has been established to play an important role in shaping regional and global climate [START_REF] Watanabe | Strengthening of ocean heat uptake efficiency associated with the recent climate hiatus[END_REF][START_REF] Haarsma | Decelerating Atlantic meridional overturning circulation main cause of future west European summer atmospheric circulation changes[END_REF]. Observational snapshots of the ocean, however, are mainly characterized by mesoscale eddy turbulence acting on shorter time scales of days to months [START_REF] Wunsch | Ocean Observations and the Climate Forecast Problem[END_REF][START_REF] Chelton | Global observations of large oceanic eddies[END_REF]. A significant outstanding challenge in physical oceanography and climate science is to reconcile these two disparate views of oceanic variability, by assessing the effect of mesoscale eddy turbulence on longer-term, climatic changes in the ocean. This question has hitherto been addressed in two ways, with contrasting results. On the one hand, several studies (largely based on the analysis of numerical models) have considered spectral surface kinetic energy transfers occurring within the ocean circulation to suggest the existence of an inverse cascade, via which mesoscale eddy turbulence energises motions on longer time scales (e.g., [START_REF] Arbic | Geostrophic turbulence in the frequency-wavenumber domain: Eddy-driven low-frequency variability[END_REF][START_REF] Sérazin | Intrinsic variability of sea level from global ocean simulations: Spatiotemporal scales[END_REF]Sérazin et al., , 2018)). The occurrence of this inverse kinetic energy cascade is interpreted to signify that mesoscale eddies act as a source of oceanic climate variability. On the other hand, a range of theoretical and numerical investigations propose that long-term oceanic variability is instead sourced from a large-scale baroclinic 14 10.1175/JPO-D-20-0141.1. Accepted for publication in Journal of Physical Oceanography. DOI instability that draws energy from the mean state (Colin de Verdière and [START_REF] De Verdière | Baroclinic instability: an oceanic wavemaker for interdecadal variability[END_REF][START_REF] Huck | Linear stability analysis of three-dimensional thermallydriven ocean circulation: application to interdecadal oscillations[END_REF][START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF][START_REF] Hochet | Direct temporal cascade of temperature variance in eddy-permitting simulations of multidecadal variability[END_REF], and that mesoscale eddies provide a damping mechanism for the variability. In the present work, we have attempted to shed light on this debate by putting forward a new, observationally grounded perspective, entailing the computation of the budget of long-term buoyancy variance within the TRM framework from mooring measurements in a Southern Ocean mesoscale eddy hotspot.

Our analysis shows that the buoyancy variance in the study area is dominated (∼80% of the total variance) by features acting on time scales between 2π/f and ∼ 100 days, associated with mesoscale eddy turbulence as determined by previous studies [START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF][START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF]. Although super-inertial buoyancy variability is large, its restricted spectral footprint makes its contribution negligible to the total buoyancy variance. Long-term variability (on time scales longer than 100 days) is also notable, and contributes between 15 and 20% of the total buoyancy variance.

Decomposing the long-term buoyancy variance into its distinct contributors reveals that long-term variability is predominantly induced by the along advection of long-term buoyancy fluctuations by the steady ocean circulation and by the across advection of steady buoyancy by long-term velocity fluctuations. There is, however, substantial cancellation between these two contributors, consistent with the non-Doppler-shifted effect expected from the passage of large-scale Rossby waves [START_REF] Rossby | Relation between variations in the intensity of the zonal circulation of the atmosphere and the displacements of the semi-permanent centers of action[END_REF][START_REF] Held | Stationary and quasi-stationary eddies in the extratropical troposphere: Theory[END_REF][START_REF] Killworth | The speed of observed and theoretical long extratropical planetary waves[END_REF][START_REF] Sévellec | The leading, interdecadal eigenmode of the Atlantic meridional overturning circulation in a realistic ocean model[END_REF]. As a result, long-term buoyancy variance primarily results from the vertical advection of the steady stratification by long-term velocity fluctuations.

Examination of the time-evolving budget of long-term buoyancy variance reveals the sources and sinks of long-term variability. Unlike in the case of kinetic energy (i.e., momentum variance) considered by previous studies (e.g., [START_REF] Arbic | Geostrophic turbulence in the frequency-wavenumber domain: Eddy-driven low-frequency variability[END_REF][START_REF] Sérazin | Intrinsic variability of sea level from global ocean simulations: Spatiotemporal scales[END_REF]Sérazin et al., , 2018)), mesoscale eddies are found to dampen long-term variability (consistenty with recent numerical simulations of [START_REF] Hochet | Direct temporal cascade of temperature variance in eddy-permitting simulations of multidecadal variability[END_REF]. This sink is balanced by a source of long-Accepted for publication in Journal of Physical Oceanography. DOI term buoyancy variance effected by long-term vertical velocity fluctuations acting on the steady stratification, as expected from large-scale baroclinic instability (Colin de Verdière and [START_REF] De Verdière | Baroclinic instability: an oceanic wavemaker for interdecadal variability[END_REF][START_REF] Sévellec | Theoretical investigation of the Atlantic multidecadal oscillation[END_REF]. The obvious difference between these two views is their depth of applicability: at surface for the kinetic energy-based view, and at sub-surface for the buoyancy variance-based view. Such consideration aside, these views' discrepancy on the expected impact of mesoscale eddies on oceanic climate variability suggests that the variances of horizontal velocities and of buoyancy behave in contrasting ways. A possible rationalization of this result is that, as kinetic energy is transferred to longer time scales, it energizes motions of increasingly larger horizontal scales (e.g., [START_REF] Arbic | Geostrophic turbulence in the frequency-wavenumber domain: Eddy-driven low-frequency variability[END_REF]. Through geostrophy, this implies that the buoyancy anomalies associated with eddies will be distributed over increasing horizontal scales too, such that the local amplitude of the anomalies will decrease as eddies grow (in both size and period). This is likely to result in eddies acting as a sink of long-term buoyancy variance. Note, however, that this apparent paradox is a classical result of quasi-geostrophic turbulence, as discussed in the works of [START_REF] Rhines | The Dynamics of Unsteady Currents[END_REF] and [START_REF] Salmon | Two-layer quasi-geostrophic turbulence in a simple special case[END_REF]Salmon ( , 1980)). In this context, kinetic energy exhibits an inverse cascade, whereas potential energy undergoes a forward cascade. Our results provide observational evidence for this predicted behavior of oceanic turbulence.

Our budget of long-term buoyancy variance indicates that a leading-order balance is established between a source and a sink underpinned by vertical flow (i.e., long-term fluctuations in the vertical buoyancy flux balanced by the eddy-induced vertical buoyancy flux).

Thus, within the TRM formalism, there is no net source or sink of long-term buoyancy variance in our observations. This result is consistent with the eddy turbulent closures based on [START_REF] Gent | Isopycnal mixing in ocean circulation model[END_REF], which have been shown to adequately represent the mean state of the study area [START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF]. This overall compensation suggests the implicit action of the eddy turbulence flux (i.e., only balancing the Eulerian mean); it would thus be interesting to diagnose its explicit impact through the momentum balance (i.e., acting as an Accepted for publication in Journal of Physical Oceanography. DOI extra stress, [START_REF] Mcdougall | The Temporal-Residual-Mean Velocity. Part II: Isopycnal Interpretation and the Tracer and Momentum Equations[END_REF].

Further, our diagnostics provide direct observational evidence of the 'eddy-saturated' behaviour of the ACC [START_REF] Thompson | Equilibration of the Antarctic Circumpolar Current by Standing Meanders[END_REF][START_REF] Hallberg | An Exploration of the Role of Transient Eddies in Determining the Transport of a Zonally Reentrant Current[END_REF][START_REF] Meredith | Circumpolar response of Southern Ocean eddy activity to a change in the Southern Annular Mode[END_REF][START_REF] Gent | Response to Increasing Southern Hemisphere Winds in CCSM4[END_REF][START_REF] Sinha | Time Scales of Southern Ocean Eddy Equilibration[END_REF][START_REF] Marshall | Eddy saturation and frictional control of the Antarctic Circumpolar Current[END_REF], by showing that long-term changes in the ACC's that long-terms changes in the density structure, induced (commonly by wind forcing) via a perturbed vertical buoyancy flux, are relaxed toward equilibrium via the damping action of eddies. More generally, our findings suggest that mesoscale eddy turbulence might suppress, or contribute to suppress, the signal-to-noise paradox [START_REF] Scaife | A signal-to-noise paradox in climate science[END_REF][START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF] of interannual climate prediction by removing or alleviating the level of noise in climate models.

While we believe that our study offers a significant contribution to the discussion on the impact of mesoscale eddy turbulence on oceanic climate variability, this contribution comes with some caveats. Chief amongst these is the possibly rather unusual dynamics of our study area, which is characterized by intense eddy activity and so is not necessarily representative of the wider Southern Ocean or, for that matter, other regions in the global ocean. A further shortcoming of our work is its reliance on a single mooring, which limits the geographical scope of our analysis. Both of these caveats call for an application of the analytical approach put forward here to mooring observations elsewhere, and to eddy-permitting and -resolving numerical models. This will be the goal of a follow-up study.

Our results indicate that mesoscale eddy turbulence exerts a stabilizing effect on oceanic climate variability. The question remains, however, of how this stabilizing role impacts the occurrence of basin-scale modes of climate variability, such as the Atlantic Multidecadal

Variability (e.g., [START_REF] Kushnir | Interdecadal variations in North Atlantic sea surface temperature and associated atmospheric conditions[END_REF]. Indeed, this question is the subject of an ongoing debate, whereby one school of thought (LaCasce and Pedlosky, 2004) suggests that mesoscale eddy damping inhibits the existence of basin-scale climatic modes; and another (Sévellec and Huck, Accepted for publication in Journal of Physical Oceanography. DOI 2015) proposes that the damping acts as a selector of unstable basin-scale climatic modes.

This latter hypothesis is supported by eddy-permitting simulations, which have been shown

to contain basin-scale climatic modes [START_REF] Huck | Multidecadal variability of the overturning circulation in presence of eddy turbulence[END_REF][START_REF] Hochet | Direct temporal cascade of temperature variance in eddy-permitting simulations of multidecadal variability[END_REF]. However, the debate remains unaddressed from an observational angle. Tackling this gap will be the aim of future work. (a) Long-term buoyancy variance and (c) long-term variance budget (i.e., 2-yr trend of the long-term buoyancy variance), with relative error of reconstruction after decomposition following ( 12) and ( 10

2

  10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020 Accepted for publication in Journal of Physical Oceanography. DOI buoyancy variance budget. Results are documented in section 4, and discussed in section 5.

  ), mooring measurements readily provide most of the needed quantities: ∂ t b, u, v, and ∂ z b. However, three required variables need to be estimated indirectly: ∂ x b, ∂ y b, and w. The horizontal buoyancy gradients are obtained using the three momentum equations, under the assumptions of low viscosity (Re 1), small inertial terms 6 10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020

  ) contributors to long-term buoyancy variance, we integrate (9) with respect to time, and obtain the 9 10.1175/JPO-D-20-0141.1. Accepted for publication in Journal of Physical Oceanography. DOI following expression for the long-term fluctuations of modified buoyancy: b

  , a phenomenon that has been extensively documented in the Southern Ocean. Invoking geostrophic balance to relate ū to ∂ y b and v to ∂ x b , we infer that the advection of the anomalous buoyancy by the mean along velocity ( ū ∂ x b , controlling Var-SV x ) and the advection of mean buoyancy by the anomalous across velocity (v ∂ y b , controlling Var-SB y ) balance each other almost perfectly. Thus, as a result of this compensation between Var-SV x and Var-SB y , we find that long-term buoyancy variance is primarily controlled by the vertical advection of steady buoyancy by long-term velocity fluctuations (Var-SB z ), again in accord with large-scale Rossby wave dynamics. It is interesting to note that neither the long-term nor the short-term turbulent components (not shown) contribute to setting the long-term buoyancy variance. This suggests, in other words, that mesoscale eddies do not directly affect the amplitude of the long-term buoyancy variance. This also reinforces the validity of the non-Doppler-shifted effect, where mesoscale eddy turbulent fluxes were ignored. [Note, however, that eddies do contribute to determining the steady components[START_REF] Sévellec | The Signal-to-Noise Paradox for Interannual Surface Atmospheric Temperature Predictions[END_REF], and so indirectly contribute to setting the amplitude of the long-term buoyancy variance.] Accepted for publication in Journal of Physical Oceanography. DOI

  Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020 Accepted for publication in Journal of Physical Oceanography. DOI and Bud-SB z = -2 ŵ b ∂ z b , = -2 w b + w b + w b + w b ∂ z b ,

  SV x and Bud-SB y (the sources of long-term buoyancy variance) are modest in comparison with Bud-SV x and Bud-SB y , respectively, the components of Bud-SB z (the sink of longterm buoyancy variance) can be as much as 4 times larger than Bud-SB z (or Bud-SV x and Bud-SB y ) and of opposite signs. This result indicates that the time-evolving budget of long-term buoyancy variance is primarily controlled by a balance concealed within Bud-SB z . In this balance, long-term buoyancy variance is generated by the vertical advection of the steady stratification by long-term velocity fluctuations (i.e., positive -2 w b ∂ z b ), and is damped by the vertical advection of the steady stratification by short-term velocity fluctuations (i.e., negative -2 w b ∂ z b ). Thus, our analysis of the observations shows that short-term mesoscale eddy turbulence suppresses long-term buoyancy variability in the study area, rather than stimulating such variability as an internal noise source as is often hypothesized. This finding is consistent with eddy turbulence closures following[START_REF] Gent | Isopycnal mixing in ocean circulation model[END_REF], which act to dampen buoyancy variance. Moreover, w b and w b are the baroclinic flux by the long-term fluctuations and the baroclinic eddy flux, respectively,

  Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020Accepted for publication in Journal of Physical Oceanography. DOI becomes the main source of short-term buoyancy variance. This illustrates that mesoscale eddy turbulence is sustained by short-term vertical advection of the steady stratification, consistently with small-scale baroclinic instability and the[START_REF] Gent | Isopycnal mixing in ocean circulation model[END_REF] eddy turbulent closure. It is also worth noting than the variance budget computed in the traditional Eulerian framework suggests that the mesoscale eddy turbulence is damping the long-term fluctuations too. The damping occurs through the horizontal buoyancy flux, however. This demonstrates the usefulness of the TRM framework to account for vertical buoyancy flux compensation (by accurately re-distributing the turbulent fluxes), and the overall robustness of the results.

  )(b and d, respectively). The total cumulative error over the vertical of the variance and its budget are indicated in the title(b and d, respectively). (a and c) Truth (red dashed line) and Total (black solid line) correspond to values computed using the left hand side and sum of the components from right hand side of (12) or (10), respectively. Values are shown on a uniformly spaced 100-m vertical grid (black and red crosses), connected by a cubic-spline interpolation (black solid and red dashed lines). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5 Long-term buoyancy variance contributors following (12). The time scale separating short-and long-term fluctuations is set at τ =100 days, such that mesocale dynamics are contained in short-term fluctuations, as shown by Sévellec et al. (2015, 2019) and Fig. 2. Values are shown on a uniformly spaced 100-m vertical grid (crosses), connected by a cubic-spline interpolation (lines). . . . 30 6 Budget of long-term buoyancy variance following (10). The time scale separating short-and long-term fluctuations is set at τ =100 days, such that mesocale dynamics are contained in short-term fluctuations, as shown by Sévellec et al. (2015, 2019) and Fig. 2. Values are shown on a uniformly spaced 100-m vertical grid (crosses), connected by a cubic-spline interpolation (lines). . . . 31 7 Decomposition of the three leading terms in the budget of long-term buoyancy variance following (13). The components in the decomposition are defined in (13). The time scale separating short-and long-term fluctuations is set at τ =100 days, such that mesocale dynamics are contained in short-term fluctuations, as shown by Sévellec et al. (2015, 2019) and Fig. 2. Values are shown on a uniformly spaced 100-m vertical grid (crosses), connected by a cubic-spline interpolation (lines). . . . . . . . . . . . . . . . . . . . . . . . . 32 Accepted for publication in Journal of Physical Oceanography. DOI

Figure 1 :

 1 Figure 1: (a) Location of the DIMES central mooring, with the red square denoting the location of the 6-mooring cluster. The inset shows a magnification of the region, with the blue circle indicating the central mooring site considered in this study. In the main panel, contours represent the dynamic ocean topography averaged from 1992 to 2002[START_REF] Maximenko | Mean dynamic topography of the ocean derived from satellite and drifting buoy data using three different techniquesP[END_REF]; the solid thick contour marks -1 m, and solid black and grey contours denote higher and lower values at intervals of 5 cm, respectively. Colour represents the absolute gradient of dynamic ocean topography rescaled as horizontal geostrophic velocity magnitude. In the inset, the solid thick contours indicate the 4,000 m isobath, and solid black and grey contours denote shallower and deeper isobaths at intervals of 100 m, respectively. The thick blue arrow shows the time-and depth-averaged direction and magnitude of the flow at the mooring location. This average flow direction defines the along direction used in the remainder of our analysis. The across direction is orthogonal to the along direction. (b) Along, (c) across, and (d) vertical velocities, as well as (e) along, (f) across, and (g) vertical buoyancy gradients at the mooring site. Time-mean values are shown on a uniformly spaced 100-m vertical grid (black crosses), connected by a cubic-spline interpolation (black line). The red shading represents plus / minus one temporal standard deviation. Modified from Sévellec et al. (2019).

Figure 2 :Figure 3 :Figure 4 :Figure 5 :Figure 6 :Figure 7 :

 234567 Figure 2: (a) Temporal contribution to the total variance of modified buoyancy. This can be related to the power spectral density through Parseval's identity. The vertical blue line represents the inertial period (2π/|f |, where f is the local Coriolis parameter); the grey crosses mark the internal gravity wave period (2π/N , where N 2 =∂ z b is the time-mean square of the local Brunt-Väisälä frequency); the red vertical line is set at τ =100 days and indicates the averaging time scale used in this study to separate short-term fluctuations (mainly driven by mesoscale eddy dynamics) and long-term fluctuations, following previous analyses (Sévellec et al., 2015, 2019). (Note that the horizontal logarithmic scale emphasizes short time scales, despite a weak overall contribution of superinertial motions.) (b) Relative contribution to the total variance of modified buoyancy by superinertial motions (SI, τ <2π/|f |, blue line), mesoscale eddy fluctuations [ME, (2π/|f |)≥τ ≤100 days, purple line] and long-term variability (LV, τ >100 days, red line)

  next exploit this relation to formulate the buoyancy variance budget.

	Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020

8 10.1175/JPO-D-20-0141.1.

  Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020

10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020

10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020 Accepted for publication in Journal of Physical Oceanography. DOI

Acknowledgment. This research was supported by the UK Natural and Environmental Research Council (SMURPHS, NE/N005767/1 to FS and DIMES, NE/F020252/1 to ACNG) and by the DECLIC project funded through the French CNRS/INSU/LEFE program. ACNG acknowledges the support of the Royal Society and the Wolfson Foundation This work was supported by ISblue project, Interdisciplinary graduate school for the blue planet (ANR-17-EURE-0015) and co-funded by a grant from the French government under the program "Investissements d'Avenir". 18 10.1175/JPO-D-20-0141.1. Downloaded from http://journals.ametsoc.org/jpo/article-pdf/doi/10.1175/JPO-D-20-0141.1/5016497/jpod200141.pdf by IFREMER/BILIOTHEQUE LA user on 13 November 2020 Accepted for publication in Journal of Physical Oceanography. DOI

Accepted for publication in Journal of Physical Oceanography. DOI

List of Figures

(a)

Location of the DIMES central mooring, with the red square denoting the location of the 6-mooring cluster. The inset shows a magnification of the region, with the blue circle indicating the central mooring site considered in this study. In the main panel, contours represent the dynamic ocean topography averaged from 1992 to 2002 [START_REF] Maximenko | Mean dynamic topography of the ocean derived from satellite and drifting buoy data using three different techniquesP[END_REF]; the solid thick contour marks -1 m, and solid black and grey contours denote higher and lower values at intervals of 5 cm, respectively. Colour represents the absolute gradient of dynamic ocean topography re-scaled as horizontal geostrophic velocity magnitude. In the inset, the solid thick contours indicate the 4,000 m isobath, and solid black and grey contours denote shallower and deeper isobaths at intervals of 100 m, respectively. The thick blue arrow shows the time-and depth-averaged direction and magnitude of the flow at the mooring location. This average flow direction defines the along direction used in the remainder of our analysis. The across direction is orthogonal to the along direction. [START_REF] Garabato | Cruise Report RRS James Cook JC041 (DIMES UK1) 5[END_REF][START_REF] Meredith | Cruise report: RRS James Cook JC054[END_REF].

Instrument type

Nominal depths (m) Nortek Acoustic Current Meter 1200, 1299, 1853, 1951, 2049, 2152, 3400, 3600 Seabird Microcat (SMP) 1200, 1299, 1853, 1951, 2049, 2152, 3400, 3600 34 10.1175/JPO-D-20-0141.1.


Nils Morawietz

Carolin Rehs
email: carolin.rehs@hhu.de

Mathias Weller
email: mathias.weller@u-pem.fr

A Timecop's Work Is Harder Than You Think

Keywords: 2012 ACM Subject Classification Theory of computation → Parameterized complexity and exact algorithms; Theory of computation periodic temporal graphs, cops and robbers, tally-intersection, congruence satisfyability

We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph.

Introduction

A cops and robbers game in graph theory is a pursuit-evasion game with two teams of players, the cops and the robbers, moving from vertex to vertex along the edges of a graph. The cops try to move onto the vertices where the robbers are positioned, thereby "catching" them, while the robbers try to evade such capture. Cops and robbers games with varying rules have been popular in graph theory as, on the one hand, they model a range of applications of pursuit-evasion games (see, for example [START_REF] Chung | Search and pursuit-evasion in mobile robotics[END_REF]), on the other hand, they relate to useful graph parameters, such as path-width and tree-width [START_REF] Hans | A partial k-arboretum of graphs with bounded treewidth[END_REF][START_REF] Paul | Graph searching and a min-max theorem for tree-width[END_REF], directed path-width [START_REF] Barát | Directed path-width and monotonicity in digraph searching[END_REF], directed tree-width [START_REF] Johnson | Directed tree-width[END_REF], DAG-width [START_REF] Berwanger | Dag-width and parity games[END_REF] or Kelly-width [START_REF] Hunter | Digraph measures: Kelly decompositions' games' and orderings[END_REF] (for surveys, see Amiri et al. [START_REF] Saeed Akhoondian Amiri | Graph Searching Games and Width Measures for Directed Graphs[END_REF], Fomin and Thiliko [START_REF] Fedor | An annotated bibliography on guaranteed graph searching[END_REF] and Nisse [START_REF] Nisse | Network Decontamination[END_REF], who considers the problem of "cleaning" a graph with mobile agents which is equivalent to a cops and robber game in which the robbers location is unknown to the cops). The special case of one robber trying to evade one cop has been fully characterized and is shown to be solvable in polynomial time by Nowakowski and Winkler [25] in the 80s using the concept of "dismantlable" graphs (see also [START_REF] Brightwell | Gibbs measures and dismantlable graphs[END_REF]). With the recent rise of dynamic graphs ("temporal graphs"), the cop and robber game regains traction. In particular, the one-cop one-robber version was recently reconsidered on "edge-periodic temporal graphs" by Erlebach and Spooner [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edge-connectivity[END_REF]. Temporal graphs exist in so-called time-steps, in which every edge may or may not appear. To this end, each edge is labeled with a set of integers corresponding to the time-steps this edge appears in [START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF]. Such graphs have recently received increased attention in the graph-theory community due to their versatility in modeling relations that evolve in time (see [START_REF] Akrida | The temporal explorer who returns to the base[END_REF][START_REF] Akrida | Temporal vertex cover with a sliding time window[END_REF][START_REF] Erlebach | On temporal graph exploration[END_REF][START_REF] Fluschnik | Temporal graph classes: A view through temporal separators[END_REF]). Considering time as infinite yields inputs of infinite size, unless we assume that the relation repeats periodically. This is modeled by "edge-periodic" temporal graphs, where each edge additionally has a number indicating the length of the period after which its occurrences repeat. This setting can also be modeled by assigning each edge a sequence x ∈ {0, 1} * , where x has a 1 at position p if and only if the edge exists in the time-steps p, p + |x|, p + 2|x|, . . . In their paper, Erlebach and Spooner [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edge-connectivity[END_REF] consider the one-cop one-robber variant on edge-periodic temporal graphs (called Cop-Win Periodic Cop and Robber, for short PCnR), characterizing strategies for both cops and robbers on edge-periodic cycles and showing how to solve the one-cop one-robber variant on any edge-periodic temporal graph in O(lcm(L)n 3 ), where L is the set of lengths of sequences occurring in the input and n is the number of vertices in the underlying static graph. Prominently, they leave open (and state as explicit open question) whether deciding the winner of their cop and robber game is NP-hard.

We resolve this open question by reducing an arithmetic problem of independent interest to PCnR. Indeed, introducing this periodic temporal concept makes the problem much harder than one would expect from the results on static graphs [START_REF] Nowakowski | Vertex-to-vertex pursuit in a graph[END_REF][START_REF] Brightwell | Gibbs measures and dismantlable graphs[END_REF]. To introduce the arithmetic problem from which we derive hardness of PCnR, let x[j] denote the j th symbol (starting with 0) of a sequence x ∈ {0, 1} * and let us abbreviate x[j]

• := x[j mod |x|]. Input: A finite set X ⊆ {0, 1} * and k ∈ N. Question: Is there some i ∈ N such that |{x ∈ X | x[i] • = 0}| ≥ k? Periodic Character Alignment (PCA)
The special case where k = |X| is called Periodic Full Character Alignment.

Input:

A finite set X ⊆ {0, 1} * . Question: Is there some i ∈ N such that, for all x ∈ X, we have

x[i] • = 0? Periodic Full Character Alignment (PFA)
We assume that |x| > 1 for all x ∈ X, since otherwise the instance is either a trivial no-instance (for PFA) or the sequences of length one can be removed. Likewise, we can assume for PFA that no two sequences, in X have the same length since we can replace two sequences x, y ∈ X of same length with the sequence resulting from the "bitwise-or" of x and y. Moreover, we abbreviate x∈X |x| =: n. Interestingly, PFA and PCA are closely related to the well-known Intersection problem for deterministic finite automata over the (unary) alphabet {1} (called Tally-DFAs, see [START_REF] Holzer | Descriptional and computational complexity of finite automata-a survey[END_REF] for a survey). Being deterministic and over a unary alphabet, each state of a Tally-DFA can only transition into at most one other state. Thus, any q-state Tally-DFA A can be represented as a rooted, directed graph G A with q vertices of out-degree one, some of which are marked as accepting states. Thus, A consists of a path plus one arc from the last vertex of the path to some other vertex of the path. Then, a word of length more than q is accepted by A if and only if it consists of a prefix 1 q followed by any number of repetitions of 1 c A (where c A is the number of vertices spanned by the last arc) followed by a suffix 1 s A (depending on which states on the path are accepting). Now, the Tally-Intersection problem asks whether some word is accepted by each of t given Tally-DFAs A i , that is, i L(A i ) = ∅. Clearly, Periodic Full Character Alignment is a special case of Tally-Intersection and they coincide if c Ai = q i (that is, G Ai is a cycle) for all i. We can achieve that c Ai = q i for all i by simulating each automaton for q max := max i q i steps, checking whether the automata accept a common word of length at most q max .

71:3 Corollary 1. Periodic Full Character Alignment is polynomial-time equivalent to

Tally-Intersection.

Regarding previous work, Fernau and Krebs [START_REF] Fernau | Problems on finite automata and the exponential time hypothesis[END_REF] show that Tally-Intersection for k automata, each with at most q states, cannot be solved in 2 o(min{k √ log q, √ q}) n O (1) time (unless the Exponential Time Hypothesis fails), but can be solved in q k n O(1) and 2.9 q n O(1) time.

The main relevance of PFA and PCA for this study are their strong relation to edgeperiodic temporal graphs: PCA is equivalent to the question whether there is a time-step in which a given edge-periodic temporal graph misses at least k edges and consequently PFA is equivalent to asking whether there is a time-step in which the graph is edgeless. We show that PFA is NP-complete (implying that PCA is) and reduce it to PCnR on temporal graphs that are acyclic in all time steps. Note that due to 1, the NP-hardness of Periodic Full Character Alignment is already clear but we present a new reduction from Multi-Colored Clique to Periodic Full Character Alignment (and, thus, to Tally-Intersection) which gives new insights into the parameterized complexity of both problems. We further prove that this hardness holds for the modification of PCnR where the robber moves first. We initiate the study of the parameterized complexity of PCA, PFA, and PCnR, proving positive and negative results for various parameterizations. The parameterized landscape for these problems seems surprisingly desolate, with W[1]hardness for most of the (single) parameters, culminating in the W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hardness of PCnR when parameterized by the size of the underlying input graph even for extremely restricted instances. A corollary that may be of independent interest is that Multi-Colored Clique is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF] hard when parameterized by the size k of the sought clique, even if the induced subgraph between any pair of distinct color classes is the union of vertex-disjoint bicliques.

Due to lack of space, some proofs are deferred to an appendix (statements marked as corollaries or observations do not have separate proofs).

Preliminaries

For a, b ∈ N, we abbreviate {a, a + 1, a + 2, . . . , b -1, b} =: [a, b]. We assume the reader to be familiar with parameterized complexity basics (see [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Cygan | Parameterized Algorithms[END_REF]) and we refer to [START_REF] Sorge | The graph parameter hierarchy[END_REF] for an overview of graph parameters considered in this work.

Sequences and Temporal Graphs

Let w ∈ {0, 1} * be a sequence and let j ∈ N. Then the length of w is denoted by |w| and the j th symbol (starting with 0) of w is denoted by w[j]. For a set X of sequences, we let L(X) := {|x| | x ∈ X} denote the set of lengths of sequences occurring in X and we let L(X) := max(L(X)) denote the maximum length of a sequence in X. If X is clear from the context, we may only write L and L. We often consider the infinite, periodic sequence resulting from repeating a sequence w indefinitely. In this case, we write w[j]

• := w[j mod |w|].
For two periodic sequences w and q, we define w & q as the "bitwise-and" of w and q, that is,

w & q has length lcm(|w|, |q|) and (w & q)[i] • = w[i] • • q[i] • .
A run of a sequence w is a consecutive part of w consisting only of 1s. Runs can be represented by the pair of their first and last index in w. We let Bl 1 (w) denote the set of runs in the sequence w, encoded as such pairs. For c ∈ N, we define the c-fold blow up of w as the sequence c × w with

(c × w)[i] = w[ i /c ] for all i ∈ [0, c|w| -1]. Moreover, for a set of sequences X we denote with c × X := {c × w | w ∈ X} the c-fold blow up of X.
An (edge-) periodic (temporal) graph G τ = (V, E, τ ) (see also [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edge-connectivity[END_REF]) consists of a graph G = (V, E) (called the underlying graph) and a function τ : E → {0, 1} * where τ maps each edge e to a sequence τ (e) ∈ {0, 1} * such that e exists in a time step t ≥ 0 if and only if τ (e)[t]

• = 1. Every edge e exists in at least one time step, that is, for each edge e there is some t e ∈ [0, |τ (e)| -1] with τ (e)[t e ] = 1.

Number Theory

We assume that the reader is familiar with the concepts of modulo arithmetic, the greatest common divisor (gcd), the least common multiple (lcm) and the extended Euclidean algorithm. Note that congruence modulo any integer q is an equivalence relation. In particular, given a ≡ b (mod q) and a ≡ c (mod q), we also have b ≡ c (mod q). Further, the modulo operation is linear, that is, for integers a, b, c ∈ Z, we have ac mod bc = c(a mod b). The Chinese Remainder Theorem (see for example [START_REF] Ireland | A classical introduction to modern number theory, chapter Congruence[END_REF]) roughly states that the congruence system x ≡ a i (mod n i ) with n i ∈ N pairwise coprime and a i ∈ Z always has a solution x ∈ Z and all solutions are congruent modulo N := i n i . In this work, we use a slightly more general version of the Chinese Remainder Theorem, proved as Lemma 4.

Lemma 2. Let x, y, p 0 , p 1 , . . . ∈ Z. Then, x ≡ y (mod lcm(p 0 , p 1 , . . .)) if and only if x ≡ y (mod p i ) for all i.

Proof. (⇒) Since p i divides lcm(p 0 , p 1 , . . .) which in turn divides x -y, we know that p i divides x -y. (⇐) x -y is clearly a common multiple of all p i , so it is divided by their least common multiple. Proof. Since gcd(a, b) divides a and b, it divides ax and by and thus ax -by. Lemma 4. Let m ≥ 1, let a 0 , a 1 , . . . , a m ∈ Z, let p 0 , p 1 , . . . , p m ∈ N. Then there is some j ∈ N with j ≡ a i (mod p i ) for all i ∈ [0, m] if and only if a i ≡ a i (mod gcd(p i , p i )) for all i, i ∈ [0, m], i < i .

Proof. The proof is by induction on m starting with m = 1.

(⇐) For the induction base, let u 0 , u 1 ∈ Z such that gcd(p 0 , p 1 ) = u 0 p 0 + u 1 p 1 be the Bézout coefficients [START_REF] Bézout | Théorie générale des équations algébriques par M. Bézout[END_REF] of p 0 and p 1 . Let z ∈ Z such that a 0 = z(u 0 p 0 + u 1 p 1 ) + a 1 . Then, a 0 -zu 0 p 0 = a 1 + zu 1 p 1 =: i and a 0 -zu 0 p 0 ≡ a 0 (mod p 0 ) and a 1 + zu 1 p 1 ≡ a 1 (mod p 1 ). For the induction step, we replace a m and a m-1 by some j with j ≡ a m (mod p m ) and j ≡ a m-1 (mod p m-1 ), which exists by induction hypothesis, and we replace p m and p m-1 by := lcm(p m , p m-1 ). Then, for all i ∈ [0, m-1], as a m ≡ a i (mod gcd(p m , p i )) and a m-1 ≡ a i (mod gcd(p m-1 , p i )), Lemma 2 implies j ≡ a i (mod lcm(gcd(p i , p m ), gcd(p i , p m-1 ))) which, by distributivity of gcd and lcm, implies j ≡ a i (mod gcd(lcm(p m , p m-1 ), p i )), that is, j ≡ a i (mod gcd( , p i )). Thus, we can apply the induction hypothesis, granting existence of j ∈ N with j ≡ a i (mod p i ) and j ≡ j (mod ). By Lemma 2, j ≡ j (mod p m ) and j ≡ j (mod p m-1 ), implying j ≡ a m (mod p m ) and j ≡ a m-1 (mod

p m-1 ). (⇒) For all i ∈ [0, m], let u i ∈ Z such that u i p i + a i = j. Then, for all i, i ∈ [0, m], we have a i -a i = (j -u i p i ) -(j -u i p i ) = u i p i -u i p i and, since u i p i -u i p i is divisible by gcd(p i , p i ) (see Lemma 3), so is a i -a i .
To compute a solution for a system of congruences x ≡ a i (mod n i ), assuming a i < n i for all i, we replace pairs of congruences by one, equivalent congruence using Lemma 2. Since this can be done using the extended Euclidean algorithm in O(log n i • log n j ) ⊆ O(log 2 N ) time, the whole congruence system can be solved in time

O(m log 2 N ) = O(m ( i log n i ) 2 ),
where m is the number of input congruences, which is polynomial in the input size,

Complexity of PFA and PCA

While the NP-hardness of PFA already follows from its equivalence to Tally-Intersection (see Corollary 1), we present here another reduction with implications on parameterized complexity, which can then be transferred to Cop-Win Periodic Cop and Robber. As a side note, we remark that PCA is in NP since the input sequences can easily be verified to be 0 at a given common index.

Input: An integer k and an undirected k-partite

graph G = (V 1 V 2 . . . V k , E).
Question: Is there a clique of size k in G?

Multi-Colored Clique (MCC)

Lemma 5. Periodic Full Character Alignment is NP-hard. Proof. Given an instance (G = (V, E), k) of MCC with k-partition (V 1 , . . . , V k ) of V , we construct an equivalent instance X of PFA in polynomial time such that |X| = k 2 .
To this end, we compute distinct prime numbers p 1 , . . . , p k in polynomial time

1 such that |V i | ≤ p i for all i ∈ [1, k]. Let V i := {v i 1 , . . . , v i |Vi| }. We define a sequence w i,j ∈ {0, 1} pi•pj for all i, j ∈ [1, k], i < j to represent all edges in the induced subgraph G[V i ∪ V j ]. We set for every r ∈ [0, |w i,j | -1], w i,j [r] := 0 if and only if {v i r mod pi , v j r mod pj } ∈ E. (1)
Finally, we set

X := {w i,j | 1 ≤ i < j ≤ k}. Claim 6. Let i, j ∈ [1, k], i < j and let t ∈ N. Then, w i,j [t] • = 0 if and only if {v i t mod pi , v j t mod pj } ∈ E.
Proof. By construction of w i,j , we have |w i,j | mod p i = |w i,j | mod p j = 0 and thus (t mod |w i,j |) mod p i = t mod p i and (t mod |w i,j |) mod p j = t mod p j . Then, by [START_REF] Akrida | The temporal explorer who returns to the base[END_REF],

w i,j [t mod |w i,j |] = 0 ⇐⇒ {v i t mod pi , v j t mod pj } ∈ E.
Next, we show that (G, k) is a yes-instance of MCC if and only if X is a yes-instance of PFA.

(⇒) Assume that (G, k) is a yes-instance of MCC. Then, there is a clique

S ⊆ V such that S ∩ V i = {v i ai } for all i ∈ [1, k].
By construction, p i and p j are coprime for all i, j ∈ [1, k], i < j. Hence, the Chinese Remainder Theorem implies that the congruence system ∀ i∈ [1,k] t ≡ a i (mod p i ) has a solution t ∈ N. We show w i,j [t]

• = 0 for all i, j ∈ [1, k], i < j.
Since S is a clique, {v i ai , v j aj } ∈ E and therefore by Claim 6, w i,j [t] • = 0.

(⇐) Let X be a yes-instance of Periodic Full Character Alignment. Then, there is an index t ∈ N with w[t]

• = 0 for all w ∈ X. Let

a i := t mod p i for all i ∈ [1, k]. We set S := {v i ai | i ∈ [1, k]}. Since w i,j [t] • = 0 for all i, j, ∈ [1, k], i < j, Claim 6 implies that {v i ai , v j aj } ∈ E. Hence, S is a clique of size k in G.
Note that it is possible to "blow up" the input sequences for PCA by any factor c ∈ |X|

O(1)
without changing the answer to the instance.

Observation 7. Let c, j ∈ N, let X ⊆ {0, 1} * such that X = c × X for some X , and let x ∈ X. Then, x[j] • = x[c • j /c ] • .
1 Since, by the Prime Number Theorem, the k th prime p k is in O(k log k), these can be computed in O(k 2 log k) time.

M F C S 2 0 2 0 71:6

A Timecop's Work Is Harder Than You Think

We show for every c ∈ |X| O (1) with c ≥ 1 that PFA (and, thus, PCA) remains NP-complete even if X = c × X for some X .

Proposition 8. Let (X , k) be an instance of PFA and let c ∈ |X |

O (1) . Then, (X , k) is a yes-instance of PFA if and only if (X, k) is a yes-instance of PFA where X = c × X .

Proof. Let S ⊆ X . We show that S is a yes-instance of PFA if and only if S = c × S ⊆ X is a yes-instance of PFA. (⇒) Let j ∈ N such that for all x ∈ S we have x [j] • = 0. Then cj ∈ N and for all

x ∈ S x[cj mod |x|] = x[cj mod c|x |] = (c × x )[c(j mod |x |)] = x [j mod |x |] = 0.
(⇐) Let j ∈ N such that, for all x ∈ S, it holds that x[j] • = 0. By Observation 7, we also have x[c • j /c ] • = 0. Then, j /c ∈ N and, for all x ∈ S , 1) , c ≥ 1, Periodic Full Character Alignment and Periodic Character Alignment are NP-complete even if X = c × X for some X .

x [ j /c mod |x |] = x [ j /c mod |x| /c] = x[c • ( j /c mod |x| /c)] = x[c • j /c mod |x|] = x[j] • = 0. Theorem 9. For every c ∈ |X| O(

Parameterized Complexity of PFA and PCA

The quest for finding a good parameterization is one of the main challenges of every parameterized analysis. However, seeing that the input consists of a set of sequences over a size-2 alphabet, options are limited. An immediate choice might be the total number of sequences |X| in the input, but a closer inspection of Lemma 5 reveals that Periodic Full Character Alignment (and, thus Periodic Character Alignment) is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard with respect to this parameter. It is thus natural to combine |X| with other structural parameters capturing the complexity of the input sequences. One way that the input sequences might be "well-behaved" is that they may all be short, but combining |X| with max L already bounds the input size and is therefore not interesting. Motivated by the observation that an instance of PFA is trivially yes if the lengths of sequences in X are pairwise prime, we can parameterize by the "distance to this triviality", by considering the maximum pairwise GCD d of the input lengths. Indeed, we show that even PCA is tractable for the parameter |X| + d. Another trivial special case is that each input sequence contains at most one letter 1 or one letter 0. This can be generalized to the condition that the input sequences have a small number of "runs" of 1s and we show that already PCA is tractable with respect to this parameter.

A different approach would be to restrict the lengths of the sequences instead of their number. Since, by Lemma 2, it suffices to consider solutions j ∈ N with j < lcm(L), implying that PCA can trivially be solved in L L • n O (1) time (recall that L = max L). It turns out, however, that the stronger parameter |L| does not lead to fixed-parameter tractability.

Parameter |X|

The next corollary follows directly by the fact that Multi-Colored Clique is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard when parameterized by k [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Cygan | Parameterized Algorithms[END_REF] and |X| = k 2 in the construction of the proof of Lemma 5.

Corollary 10. PFA is W[1]-hard when parameterized by |X|.

The equivalence with Tally-Intersection (see Corollary 1) implies the following.

Corollary 11. Determining whether k Tally-DFAs accept a common word is W[1]-hard wrt. k.

To solve PFA, we can construct a graph whose vertices are all positions of sequences in X and two such positions are adjacent if and only if they will eventually coincide. Then, PFA becomes equivalent to solving Multi-Colored Clique on this particular graph. In order to check if two positions will eventually coincide, we use Lemma 4. Now, we formally define an |X|-partite graph • = 0 for all x ∈ Y .

G X := (V, E) with V := {(x, j) | x ∈ X ∧ x[j] = 0}
Proof. (⇒) Let C be a size-k clique in G. Let a i denote its vertices and let x i ∈ X denote the sequence in X that contains a i . Then, for each edge {a i , a i } in C, we have

a i ≡ a i (mod gcd(|x i |, |x i |))
and, by Lemma 4, there is some j ∈ N with j ≡ a i (mod

|x i |) for each a i ∈ V (C). Thus, x i [j] • = x i [a i ] • = 0 for all a i ∈ V (C).
(⇐) Let j ∈ N and let Y ⊆ X be a size-k set of sequences with x[j] • = 0 for all x ∈ Y .

For each x ∈ Y , let a x := j mod |x|. Then, by Lemma 4, we have a x ≡ a y (mod gcd(|x|, |y|)) for all distinct x, y ∈ Y , implying that the edge {(x, a x ), (y, a y )} exists in E. Note that in the worst case, this algorithm is not faster than the known algorithm for Tally-Intersection but our algorithm works even for Periodic Character Alignment and might be much faster on instances where d has a small value.

Since the number of color classes in the constructed Multi-Colored Clique instance is |X| and PFA is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard by Corollary 10, Lemma 12 implies that MCC remains W[1]-hard, even on such restricted instances. While this has no further consequences for the problems at hand, we found this to be a noteworthy fact, in particular given the central role that MCC plays in many W[1]-hardness proofs.

Corollary 14. Multi-Colored Clique is W[1] hard with respect to k even if the induced subgraph between any pair of distinct color classes is a union of vertex-disjoint bicliques.

Parameter #runs

We present an ILP formulation that will set a variable i to the index we are looking for. We further use variables z j to indicate which sequences x j have a 1 at position i and variables r j indicating how many times x j is repeated before reaching position i. Thus, for each x j , either z j = 1 or, for each run (s j , t j ), we have i < s j or i > t j (herein, we use another variable y j,st to indicate which of the two applies).

z j ∈ {0, 1}, r j ∈ N for all x j ∈ X y j,st ∈ {0, 1} for all x j ∈ X and (s, t) ∈ Bl 1 (x j ) i ∈ N minimize z j subject to r j |x j | ≤ i < (r j + 1)|x j | for all x j ∈ X (2) i -r j |x j | + (1 -y j,st )|x j | > t for all x j ∈ X, (s, t) ∈ Bl 1 (x j ) (3) i -r j |x j | -(y j,st + z j )|x j | < s for all x j ∈ X, (s, t) ∈ Bl 1 (x j ) (4)
Note that i-r j |x j | denotes the position i j := i mod |x j | in x j . If this position is in the interval [s, t] for any (s, t) ∈ Bl 1 (x j ), then y j,st = 0 (since, otherwise Note that, while seemingly natural, guessing the correct run for each sequence in X (plus one for "not in the solution") is not enough to solve PCA since, by Proposition 16, the problem remains NP-hard, even if each sequence contains a single 0. However, this hardness breaks down for PFA (corresponding to prepending an 2 |X| -way guessing step for PCA). We consider it an interesting open question whether PFA is fixed-parameter tractable with respect to the maximum number of runs in any input sequence. A possible hint that PFA might also be hard for a constant number of runs per sequence is given by Lemma 2 which could be used to represent a multi-run sequence by a set of single-run sequences.

i j + (1 -y j,st )|x j | = i j ≤ t contradicting (3)) and z j = 1 (since, otherwise, i j -(0 + z j )|x j | = i j ≥ s contradicting (4)).

Parameter #lengths |L|

While PCA is fixed-parameter tractable for L = max L, the stronger parameter |L| is not enough to yield tractability results even if every x ∈ X contains exactly one 0.

Proposition 16. PCA is W[1]-hard with respect to k + |L(X)| even if every x ∈ X contains exactly one 0.

Proof. Let X be an instance of PFA and let Z x := {z | x[z] = 0} denote the set of positions where x has a 0 for each x ∈ X. We set k := |X| and X := {x z | x ∈ X, z ∈ Z x } where |x z | := |x| and x z [t] := 0 if and only if t = z for all t ∈ [0, |x| -1]. We show that X is a yes-instance of PFA if and only if (X , k) is a yes-instance of PCA.

(⇒) If X is a yes-instance of PFA, there is some i ∈ N such that, for all x ∈ X, we have x[i]

• = 0 and, by construction, x i mod |x| [i] • = 0. Thus, (X , k) is a yes-instance of PCA. Y contains exactly one sequence of length |x| for each x ∈ X. Thus, for each x ∈ X there is some

z ∈ Z x such that x z ∈ Y . Hence, x z [i] • = 0 and therefore x[i] • = 0 for all x ∈ X.
Consequently, X is a yes-instance of PFA. Since, by Corollary 10, PFA is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard when parameterized by |X|, PCA is W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard when parameterized by k + |L(X)| even if every x ∈ X contains exactly one zero.

Periodic Cop and Robber

We consider a cops and robbers game with rules identical to those introduced in [START_REF] Quilliot | Jeux et pointes fixes sur les graphes[END_REF][START_REF] Nowakowski | The smallest graph variety containing all paths[END_REF] (variant with one cop and one robber), which has been defined on edge-periodic graphs by Erlebach and Spooner [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edge-connectivity[END_REF]. There are two players, a cop C and a robber R. First C, then R (in knowledge of C's choice) choose a start vertex on a given edge-periodic graph G τ = (V, E, τ ). Then for each time step t ≥ 0, both players take alternating turns, either remaining on their current vertex or moving to a vertex that is adjacent to their current vertex in time step t. In every time step, C moves first, knowing R's position and R moves second, knowing the move C just made. The game terminates whenever C moves onto a vertex on which R resides in that moment. If there is a strategy for C such that the game terminates, then G τ is called cop-win and this strategy is a winning strategy for C.

Otherwise, G τ is called robber-win and the strategy for R that enables infinite evasion of C is called winning strategy for R.

Input: An edge-periodic graph G τ = (V, E, τ ). Question: For the above defined cop and robber game, is there a winning strategy for C, that is, is G τ cop-win?

Cop-Win Periodic Cop and Robber (PCnR)

We will show NP-hardness of this problem by reducing from PFA. Proof. Given an instance X of PFA which is the 3-fold blow up of some X , we construct a K 2,2|X|+1 on the vertex set

V 1 V 2 with V 1 = { , r} and V 2 = {m} ∪ {v j , w j | 0 ≤ j < |X|} τ ({ , m}) := 100 ∀ xj ∈X τ ({ , w j }) := τ ({r, v j }) := x j & 010 τ ({m, r}) := 010 ∀ xj ∈X τ ({ , v j }) := τ ({r, w j }) := x j & 101
Note that G τ consists of two disjoint stars in each time step. To show that X is a yes-instance of PFA if and only if the constructed G τ is cop-win, we use the following claim.

r v0 x 0 & 0 1 0 x 0 & 1 0 1 w0 x 0 & 0 1 0 x 0 & 1 0 1 v |X|-1 w |X|-1 m 0 1 0 1 0 0 . . . Claim 18.
At the start of a time step t with t mod 3 = 0, the cop has a winning strategy if C is on vertex and R is on any of the vertices {v j | 0 ≤ j < |X|} or C is on vertex r and R is on any of the vertices {w j | 0 ≤ j < |X|}.

It seems thus that the intrinsic hardness of the underlying algebraic problem can hardly be overcome by structural limitations of the temporal graph. therefore, we investigated parameters of the τ -function leading to tractability for PFA, such as the number of lengths |L(τ (E))| and the number of 1s in each τ (e). For PCnR, however, we are met with hardness again. Curiously, by extending standard techniques [START_REF] Gurski | Knapsack problems: A parameterized point of view[END_REF][START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], kernelization can be pushed to any root of lcm(L(τ (E))) but not to its logarithm. With dynamic graphs, the modification of the cop and robber game in which the robber moves first in each round makes sense (contrary to the "static" case, where this modification has no effect on the game).

Input: An edge-periodic graph G τ = (V, E, τ ). Question: For the periodic cop and robber game where in every time step R moves first and C moves second, is there a winning strategy for C?

Conclusion

In this paper we showed that, unless P = NP, there is no polynomial-time algorithm for the pursuit-evasion game with one cop and one robber on edge-periodic temporal graphs, thereby answering an open question of Erlebach and Spooner [START_REF] Erlebach | A game of cops and robbers on graphs with periodic edge-connectivity[END_REF]. We analyzed the parameterized complexity of deciding this game and showed that it is W[1]-hard, even if the parameter is the size of the underlying input graph. Thus, unless FPT = W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF], there is no graph parameter for which Cop-Win Periodic Cop and Robber is fixed-parameter tractable.

This hardness even applies for severely restricted instances. The open question remains whether PCnR is in NP (and is thus NP-complete) or maybe even harder.

Our hardness results are based on intuitive algebraic problems called Periodic Character Alignment and Periodic Full Character Alignment, asking whether a given set of periodic sequences over {0, 1} is unanimously 0 at any index or, equivalently, whether all of a given set of Tally-DFAs accept a common word.

As a side node, we showed that Multi-Colored Clique remains W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hard when parameterized by the size k of the sought clique, even if the induced subgraph between any pair of distinct color classes is the union of vertex-disjoint bicliques.

Lemma 3 .

 3 Let x, y, a, b ∈ Z. Then, ax ≡ by (mod gcd(a, b)).

  and there is an edge between (x, j) and (y, ) in G X if and only if x = y and j ≡ (mod gcd(|x|, |y|))}.For Y ⊆ X let G[Y ] denote the |Y |-partite subgraph induced by {(x, j) | x ∈ Y ∧ 0 ≤ j < |x|}. Note that G[{x,y}] consists of at most gcd(|x|, |y|) vertex-disjoint bicliques (one for each congruence class modulo gcd(|x|, |y|)). We prove the correctness of our reduction to Multi-Colored Clique. Lemma 12. Let k ∈ N. Then, G has a size-k clique if and only if there is some j ∈ N and some Y ⊆ X with |Y | = k and x[j]

Lemma 12 can

 12 also be used to reduce PCA to a version of Multi-Colored Clique that allows more color classes than vertices in the target colorful clique. A straight-forward method of solving Multi-Colored Clique on instances produced by Lemma 12 is to guess one of the at most gcd(|x|, |y|) bicliques for each pair of color classes of the vertex |X|-partition. Corollary 13. PCA can be solved in d |X| 2 n O(1) time where d = max x,y∈X,x =y gcd(|x|, |y|).

Proposition 15 .

 15 PCA and PFA can be solved in b O(b) •n O(1) time, where b = x∈X Bl 1 (x).

(

  ⇐) If (X , k) is a yes-instance, then there are Y ⊆ X and k ∈ N with |Y | ≥ k and y[i]• = 0 for all y ∈ Y . By construction (and no two sequences in X have the same length),

Theorem 17 .

 17 Cop-Win Periodic Cop and Robber is NP-hard even on edge-periodic temporal graphs G τ whose underlying graph is K 2,n for some n ∈ N and G τ consists of two disjoint stars in each time step. Further, Cop-Win Periodic Cop and Robber is W[1]-hard when parameterized by |G| = |V | + |E| in this setting.

Theorem 23 .

 23 Cop-Win Periodic Cop and Robber is W[1]-hard when parameterized by the sum of |L(τ (E))| and the vertex cover number of the underlying graph, even if (a) the underlying graph is bipartite and planar, (b) at most two edges exist in each time step, and (c) τ (e) contains a single 1 for each e ∈ E. Theorem 24. Unless NP ⊆ coNP/poly, there is no polynomial compression for Cop-Win Periodic Cop and Robber parameterized by the sum of L(τ (E)) and the number of vertices to delete to turn the underlying graph into a clique. For the parameter L := |L(τ (E))|, we can use the O(lcm(L(τ (E))) • n 3 )-time algorithm of Erlebach and Spooner [13] (as lcm(L(τ (E))) < L L ). Together with Theorem 24, we obtain the following corollary. Corollary 25. Cop-Win Periodic Cop and Robber is solvable in O(L L n 3 ) time and does not admit a polynomial compression when parameterized by L, unless NP ⊆ coNP/poly.

Proposition 26 .

 26 For every d ∈ N, Cop-Win Periodic Cop and Robber admits a kernel of size d lcm(L(τ (E))) but does not admit a kernel whose size is polynomial in log(lcm(L(τ (E)))), unless NP ⊆ coNP/poly.

Theorem 27 .

 27 Robber-First Cop-Win Periodic Cop and Robber (RfPCnR) Unsurprisingly, this modification does little to change the complexity of the problem. Robber-First Cop-Win Periodic Cop and Robber is NP-hard even on edge-periodic temporal graphs whose underlying graph is K 2,n for some n ∈ N. Further, Robber-First Cop-Win Periodic Cop and Robber is W[1]-hard when parameterized by |G| = |V | + |E| in this setting.

Recall that the cop wins by staying on until the point where he can win in

moves using m. Thus, the robber cannot escape the chosen G τ i in this scenario.

Acknowledgements

We thank our anonymous reviewers for their various helpful suggestions, in particular the connection to Tally-DFAs.

Proof. Suppose that C is on and R is on v j for some j ∈ [0, |X| -1]. By definition, there is a time step t ≥ t such that the edge { , v j } exists in time step t but not in any time step between t and t -1. Hence, C can stay on the vertex until the beginning of time step t and move onto v j in step t . To show that this is a winning strategy, it remains to show that R must stay on v j in all time steps between t and t -1. By construction, if { , v j } does not exist in some time step t with t mod 3 = 0, then the edge {v j , r} does not exist in the time steps t , t + 1, and t + 2. Thus, R must stay on v j until the beginning of time step t since {v j , r} is the only other edge adjacent to v j . The case for C is on r and R is on w j , j ∈ [0, |X| -1] is symmetric.

(⇒) Suppose that X is a yes-instance of PFA. We describe a winning strategy for the cop in G τ . Choose vertex as the start position. Since X is a yes-instance of Periodic Full Character Alignment, Observation 7 implies that there is some i ∈ N with i mod 3 = 0 and x j [(i + p)]

• = 0 for all x j ∈ X and p ∈ [0, 2]. Thus, in time steps i, i + 1 and i + 2, no edge except { , m} and {m, r} exists. The strategy for C is thus to stay on for the first i -1 time steps. By Claim 18 we can assume that at the beginning of time step i, the robber is not on any vertex of {v j | 0 ≤ j < |X|} as, otherwise, C has a winning strategy. In time step i, the cop moves to m which is a valid move since i mod 3 = 0 and τ ({ , m})[0] = 1. If R is currently on m then C wins immediately. Otherwise, the robber is on r or on any of the vertices {w j | 0 ≤ j < |X|}. As no edge incident with any of these vertices exists in time step i, the robber can only stay on his current vertex. Since τ ({m, r}) [START_REF] Akrida | The temporal explorer who returns to the base[END_REF] = 1, the cop can move to r in time step i + 1 and thus win the game if R is on r. Otherwise, R has to be on w j for some j ∈ [0, |X| -1] and can only stay on this vertex on the time steps i, i + 1, and i + 2. Thus, C can stay on r until the beginning of time step i + 3. Due to Claim 18, C has winning strategy. Hence, C has a winning strategy in all cases.

(⇐) We show the contraposition. Supposing that X is a no-instance of Periodic Full Character Alignment, we show that the robber has a winning strategy on G τ , that is, G τ is a no-instance of Cop-Win Periodic Cop and Robber. Since X is a no-instance, for each time step t, there is some index i(t) such that x i(t) [t] • = 0 and i(t) = i(t -1) unless t mod 3 = 0. In the following, we call a vertex u r safe for a vertex u c = m if (a) u r = m, (b) u c and u r are at distance two in the underlying graph G and (c)

. Further, we also call u r safe for m in time step t if (a) u r = w i(t) and t mod 3 = 2 or (b) u r = r and t mod 3 = 2.

Claim 19. Let the cop move onto (or stay on) a vertex u c in time step t. Then, the robber can move onto a vertex u r that is safe for u c in step t.

Proof. The proof is by induction on t. For t = 0, note that r and are safe with respect to each other, v i(0) is safe for all vertices except m, r, , and v i(0) and w i(0) is safe for m and v i(0) . Thus, no matter the start position of the cop, the robber can move onto a safe vertex. For the induction step, we know that, in step t -1, the robber was on a safe vertex u r with respect to the vertex u c of the cop.

Case 1: u c = m. If t mod 3 = 0, then u c ∈ {m, } by construction of G τ , implying u r = r (by induction hypothesis), and the robber can move to w i(t) , which is safe for m in step t. If t mod 3 = 1 then, by construction of G τ , we have u c ∈ {r, m}, implying u r ∈ { , w i(t-1) = w i(t) } and the robber can move to w i(t) , which is safe for m in step t. If t mod 3 = 2 then, u c = m by construction of G τ , implying u r = w i(t-1) = w i(t) and the robber can move to r which is safe for m in time step t.

Case 2: u c = m and u c = m. Then, by construction of G τ , either t mod 3 = 0 and u c = and u r = r (by induction hypothesis), which is also safe for u c , or t mod 3 = 1 and N. Morawietz, C. Rehs, and M. Weller 71:11 u c = r and u r = w i(t-1) = w i(t) (by induction hypothesis), implying that the robber can move to which is safe for r in step t.

Case 3: u c = m and u c = m. If u c = u c , then u r is still safe for u c so the robber can stay put. Thus, suppose u c = u c . If u c = r, then u c ∈ {v j , w j } for some j ∈ N by construction of G τ and u r = {v j , w j } -u c (by induction hypothesis) and, since the edge {r, u c } exists in time step t, so does { , u r }, and the robber can move to . The case that u c = is symmetric. Finally, if u c = v j for some j ∈ N, then u c ∈ { , r} and u r ∈ { , r} -u c (by induction hypothesis). Since the edge {u c , v j } exists in G[t], so does {u r , w j } and, thus, the robber can move to w j . The case that u c = w j is symmetric. Now, if u c = m, u r = r in time step t with t mod 3 = 2, then the cop cannot catch the robber in time step t + 1. Otherwise, being safe implies being at distance two in the underlying graph and the cop cannot catch the robber in time step t + 1. Thus, Claim 19 implies a winning strategy for the robber.

The W [START_REF] Akrida | The temporal explorer who returns to the base[END_REF]-hardness for Cop-Win Periodic Cop and Robber when parameterized by |G| in this setting now follows directly by Corollary 10 and the fact that |G| ∈ O(|X|).

A quick inspection of the proof of Theorem 17 allows us to also exclude polynomial compressions, even when combining structural parameters with L(τ (E)).

Proposition 20. Cop-Win Periodic

Cop and Robber does not admit a polynomial compression when parameterized by the sum of L(τ (E)), the maximum degree of the underlying graph, and the treedepth, unless NP ⊆ coNP/poly.

Sketch. Given k instances G τ

i of PCnR as constructed in the proof of Theorem 17 (where we assume that k is a power of 2), construct a binary tree T (whose edges are labeled with 1) with k leaves, which we identify with the -vertices in the instances G τ i . The cop chooses the root of T as its start vertex and follows the robber into one of the G τ i -subgraphs. At this point, the winning strategies of the cop and robber, respectively, hold 2 as in the proof of Theorem 17. Thus, the cop wins if and only if all input instances are cop-win, implying that PCnR is AND-composable, which implies the result (see [START_REF] Cygan | Parameterized Algorithms[END_REF]Section 15]).

Note that Theorem 17 excludes any kind of graph-structural parameterization as the hardness relies entirely on the hardness of the underlying algebraic problem. However, since the problem can be solved trivially if the underlying graph G is a tree or a clique, we might still hope that restricting G (and G τ ) to be either very sparse or very dense yields tractability. It turns out that such restrictions would have to be severe.