Michel Daher Mansour

Romain Parret

Fabien Cheynis

Matthieu Petit

Fadi Choueikani

Lisa Michez

Laurence Masson
email: masson@cinam.univ-mrs.fr

Magnetic anisotropy of one-dimensional Co nanostructures

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Tremendous efforts have been devoted in the last two decades to investigate the magnetic properties of nanometer-size particles adsorbed on surfaces [1][2][3][4], motivated by both fundamental and practical interests such as magnetic recording or memory devices. An important attractive feature of these low-dimensional systems is the possibility to tune their magnetic properties by a fine control of their atomic structure or geometry and the chemical environment of the magnetic atoms. However, reducing the dimensionality of magnetic systems is known to reduce the stability of their magnetic ordering. One key parameter to describe the magnetic behavior of such nanoparticles is the magnetic anisotropy energy (MAE) which determines the tendency of the magnetization to align along specific axis rather than randomly fluctuate over time. Remarkably, transition metal (TM) nanostructures have been found to possess high magnetic anisotropy compared to two-dimensional (2D) ultrathin films or bulk materials, originating from the extremely low coordination of atoms [1]. Nevertheless, subnanometric nanostructures investigated are generally paramagnetic down to the lowest temperature, i.e. no remanent field is observed. In this context, one-dimensional (1D) TM nanostructures have received great attention since the discovery in 2002 of an unprecedented long-range ferromagnetic order in Co monoatomic chains formed at step edges of Pt(997), associated with the enhancement of Co orbital magnetic moments and, in turn, of MAE [5]. Such behavior results from kinetic barriers and below a threshold temperature, called blocking temperature (15 K in [5]), the MAE efficiently pins the orientation of the magnetization of each spin blocks along an easy axis without external magnetic field, on the timescale of the experiments. In these experiments, the average length of a continuous Co chains, uninterrupted by kinks, was  80 Co atoms. At 45 K, a short range ferromagnetic order, associated with a 1D superparamagnetic system, was found to extend over about 15 Co atoms only. This experimental pioneering work corroborates numerous theoretical calculations predicting that the reduced symmetry of 1D magnetic systems produces strong modifications of the electronic band structure and thus, significant effects on the MAE are expected [6][7][8][9]. The attractiveness of these 1D magnetic systems is reinforced with the recent theoretical prediction of an anisotropic spin-polarized electronic current along TM nanolines, such as Mn, Fe or Co nanolines on graphene [10], which opens the possibility of their integration in spintronic-based devices.

Another important feature of 1D magnetic nanostructures is an expected strong anisotropic behavior of the magnetization axis, determined by both the 1D geometry of the nanolines and their interaction with the substrate. Experimental studies have often revealed an uniaxial easy axis of magnetization in the plane perpendicularly to the TM chain axis, canted from the surface normal with different tilt angles [5,11,12]. Moreover, it has been shown that the easy axis of magnetization oscillates in the plane perpendicular to the chains axis as a function of the transverse width of Co chains grown on Pt(977) [13]. The different orientations of the easy axis can also originate from any changes in the environment as shown in several theoretical studies. For instance, a rotation of the easy axis from the direction parallel to the chain to the out-of-plane one has been theoretically predicted when cobalt chains are whether freestanding or supported on Pd(110) [6] while the magnetization of Co wires supported on Cu(100) and Pt(100) substrates was found to align with the wire axis [14].

Developments in atomic engineering during the last two decades have made possible the fabrication 1D TM systems with a high structural control over the width of the chains, allowing productive confrontations with theoretical works. Template directed-growth using intrinsic structural properties of surfaces has proven to be a powerful route to produce high densities of 1D nanostructures with controlled geometries, regular sizes and spacings, allowing the investigation of their magnetic properties using either local probes (spin-polarized scanning tunneling microscopy) or surface-average probes (x-ray magnetic circular dichroism (XMCD) in the total electron yield (TEY) mode) [5,[11][12][13]15]. Recently, we have shown that a nanopatterned Ag(110) surface with a Si nanoribbon (NR) array (density  5×10 6 cm -1 ) can be advantageously used to grow identical and highlyordered Co dimer nanolines [16]. Preliminary investigations of their magnetic properties using XMCD revealed that the first Co atomic layers directly adsorbed onto the Si NRs present a weak magnetic response (magnetic dead layer), while upper Co layers exhibit an enhanced magnetization with an inplane easy axis of magnetization, perpendicular to the Co nanolines.

In this paper, we have further investigated the magnetic properties of the ultrathin film composed of Co nanolines grown on the 1D Si nanotemplate. Advanced magnetic investigations using XMCD evidence a superparamagnetic behavior of thermally fluctuating 1D segments, with a low blocking temperature lying between 20 K and 40 K and the size of the spin blocks composed of ferromagnetically coupled Co atoms is estimated. Our results clearly evidence that an in-plane magnetization is favored. The magnetic moments together with the MAE associated with the directions parallel and perpendicular to the nanolines are measured.

II. EXPERIMENT

Growth and characterization measurements were performed in ultrahigh vacuum (UHV, base pressure 10 -10 Torr) set-ups. The Ag(110) single-crystal surface was prepared in the UHV chamber by repeated cycles of Ar + sputtering followed by annealing at 770 K. Si was evaporated from a direct current heated piece of silicon wafer kept at 1520 K, after preoutgassing at 1070 K for several hours, onto the clean Ag(110) surface heated at 490 K. The Ag surface nanopatterned with Si was checked by scanning tunneling microscopy (STM) and low energy electron diffraction (LEED) before the deposition of Co. Co was evaporated from a rod (purity 99.99 %) inserted in a commercial Scienta Omicron ebeam evaporator and was deposited on the Si NR template at 220 K prior to magnetic measurements. STM images were acquired at the CINaM in Marseille using Scienta Omicron scanning tunneling microscopes, working at room temperature (RT) and 77 K in constant current-mode. The STM data were processed using Gwyddion software [START_REF] Nečas | Gwyddion: an open-source software for SPM data analysis[END_REF]. XMCD experiments were performed at the DEIMOS beamline at the French national synchrotron facility (SOLEIL), which operates in the soft x-ray range [18]. XMCD measurements were performed by measuring x-ray absorption spectra (XAS) at the Co L2,3 edges (2p to 3d transitions) using left and right full circularly polarized light in the TEY mode.

The magnetization curves were recorded using fast scan mode [19] at various substrate temperatures, ranging from 4 K to 100 K, under a variable magnetic field of up to 6 T, collinear with the incident x-ray direction. The experiments performed with a magnetic field varying along or perpendicularly to the axis of the Co nanolines correspond to two different sets of experiments. The uncertainties associated with the measurements of the magnetic moments and the MAE result from XAS analysis. The Co coverages have been estimated using combined XAS and STM measurements. 1 monolayer of Co (MLCo) corresponds to the 5 × 2 Si NR array completely covered with Co nanolines and equals 0.6 monolayer (ML) in silver (110) surface atom density. The lattice parameters of Ag(110) are denoted aAg|| = 0.289 nm in the [11 ̅ 0] direction and aAg = 0.409 nm in the [001] direction.

III. RESULTS AND DISCUSSION

A. Growth of Co dimer nanolines on Si/Ag(110)

Prior to Co deposition, the Ag(110) surface was firstly nanopatterned with a Si atomic layer, widely described in the literature (see for instance [20] and references therein, [21]). This nanotemplate consists in a Si NR array with a pitch of  2 nm, formed during Si deposition at 490 K onto the bare Ag(110) surface. The Si NRs are self-assembled in a 52 superstructure covering uniformly the whole Ag surface at completion with a short-and long-range high structural order. The atomic structure of the Si NRs was solved in 2016 with an original Si pentamer chain model lying in the missing row troughs of the reconstructed Ag(110) surface [20,22]. In this description, Si NRs of the 52 superstructure correspond to twin Si pentamer chains and will be denoted hereafter as double nanoribbons (DNRs). The Si NR array is stable until 490 K [21], temperature above which a silver surface faceting induced by Si adatoms occurs [23].

It has been already reported in our group that this Si 1D nanotemplate can advantageously be used to grow Co nanolines [24,25]. It has been shown that upon Co deposition at RT, Co atoms are adsorbed on top of the Si NRs, giving rise to the growth of identical Co nanolines perfectly aligned with the NR axis. The high-resolution STM image of Fig. 3 published in [24] revealed that these Co nanolines of the first layer are composed of dimers oriented perpendicularly to the nanoline axis. Based on the accurate calibration of the STM image using the crystallographic atomic positions determined by grazing incidence x-ray diffraction (GIXD) (see [20] Supplemental Material) , the distance between two Co atoms of a dimer is dCo-Co = (3.0 + 0.5) Å and the distance between two adjacent Co atoms along the nanolines is higher, dCo-Co// = (4.5 + 0.5) Å i.e  1.5 aAg||. This latter periodicity, in the direction parallel to the nanolines, leads to a modulation of the corrugation observed by STM: one out of every two dimers appears slightly brighter. Interestingly, STM images showed that after deposition of 0.16 ML of Co at RT, more than 80 % of the dimer nanolines are side by side with two nanolines of similar length on the same Si DNR. Moreover, it has been shown that the length of Co nanolines is governed by the atomic process of Co inter-diffusion into the Si array, leading to the local destruction of the Si NRs [25]. To partially hinder this thermally activated process and thus increase the length of the Co nanolines, Co was deposited on the substrate held at 220 K prior to the XMCD measurements reported in the next section.

The STM image in Fig. 1(a) illustrates the growth of the first and second layers of Co nanolines on the 52 Si array, after deposition at 220 K. The brighter protrusions correspond to Co dimers of the second layer while the other protrusions correspond to those of the first layer. Closer inspection of Fig. 1(a) reveals the presence of some black holes, mostly located at the terminations of the Co nanolines and attributed to the local destruction of the Si NRs induced by Co diffusion into the Si layer, leaving uncovered parts of the silver substrate [25]. For both Co layers, the distance between the protrusions along the nanoline axis is 2 dCo-Co//, indicating that only protrusions with the higher corrugation of each layer are visible. Our STM observations suggest that the Co atomic arrangement in nanolines directly adsorbed on Si NRs and in the upper layers is similar. From STM images, we have analyzed the height of the Co nanolines measured from local bare parts of the silver substrate. As exemplified by the height profile displayed in Fig. 1(b), the corrugation of the first and second Co nanolines is found to be  50 pm.

For higher coverages, the Co growth reproduces the 1D pattern of the Si template as shown in Fig. 2(a). By measuring the height of the different species observed in STM images, Co nanolines of the different layers can be identified, as illustrated in Fig. 2(b). The length of the nanolines cannot be accurately estimated due to the non-perfect layer-by-layer growth. Based on a statistical analysis of STM images, the average length at completion of the first Co layer grown at RT is  4.5 nm. Assuming that the nanoline length of this first Co layer determines those of the following layers, the length of the Co nanolines of upper layers is  4.5 nm, which is in agreement with the STM image of Fig. 2(b).

The average length at completion of the first Co layer grown at 220 K is  6 nm, determining the length of the Co nanolines of the upper layers. We will consider in the following this length to be 6 nm, which corresponds to nanolines composed of  14 Co dimers.

B. Magnetic properties of the Co dimer nanolines

XAS spectra were recorded under a magnetic field of 6 T applied in the different geometries illustrated in Fig. 3(a), for right-and left-handed circularly polarized light denoted as µ+ and µ-, respectively. H// and H denote a magnetic field parallel or perpendicular to the axis of the Co nanolines, respectively. To probe both the out-of-plane and the in-plane magnetic moments, the sample was rotated with respect to the direction of H// or H collinear to the x-ray beam, by an angle  comprised between 0 ° (normal incidence) and 70 ° (close to grazing incidence). The strong nonmagnetic background signal coming from the Ag substrate has been removed from the Co-L2,3 XAS spectra. The background for each considered temperature has been assessed as the difference between the XAS spectra recorded at the temperature of interest and 300 K where the Ag extended xray absorption fine structure (EXAFS) oscillations are greatly attenuated. The spectra are normalized to the incident beam intensity and then to the L3 pre-edge value. All the XAS spectra presented here have been recorded at the same Co coverage of (4.0 + 0.5) MLCo i.e. an average of four layers of Co nanolines. This coverage has been estimated from XAS measurements at the L2,3 Co absorption edges, taking into account the escape depth of electrons coming from the substrate through the adsorbate and the photoionization cross sections of both Ag and Co at the L3 Co absorption edge [26]. Height profiles measured in STM images recorded in situ on the samples probed by XAS are in agreement with this coverage. These STM images are very similar to the one presented in Fig. 2, with a mean thickness of 4 Co monolayers but with a lower resolution and thus not shown here. The XAS spectra are similar for both orientations of the magnetic field. The XMCD signal that represents the difference between the XAS spectra for left-and right-handed light polarization gives access to the magnetization magnitude of a specific element. The spin (mS) and orbital (mL) moments per atom can be quantitatively determined using the magnetic sum rules described in [28,29]. Here, we have applied the formalism described by Chen et al. [30], in order to evaluate the spin and orbital contributions to the magnetization of the Co nanolines. The number of holes in the Co 3d band has been considered to be 2.5, which corresponds to an average theoretical value for bulk Co [31,32], in agreement with the value of 2.4 used in the case of Co adatoms on Pt(111) [1]. For each configuration, the spin and orbital moments of the 4 MLCo ultrathin film derived from our measurements at grazing and normal incidences are similar, showing that the magnetization is saturated at 6 T. We found mS// = (0.51 + 0.06) µB per atom (µB/at) and mL// = (0.073 + 0.010) µB/at for H// and mS = (0.47 + 0.05) µB/at and mL = (0.070 + 0.010) µB/at for H. The lower values of ms and mL compared to those of ms// and mL// could result from a slightly lower Co coverage for the measurements performed in the H configuration, as revealed by the lower intensity in the XAS spectrum (see Fig. 3 (b)). Indeed, as already mentioned in [16] and confirmed below, the magnetic properties of the Co film depend on its thickness. To evaluate the real orbital and spin moments per atom, the weak contribution of the first two Co layers have been retrieved to the measurements reported above for 4 MLCo. For 2 MLCo, the magnetic moments at normal incidence for the H// and H configurations are found to be similar and equal to mS = (0.09 + 0.01) µB/atom and mL = (0.012 + 0.002) µB/atom. The moments of the Co atoms in the two upper layers of the 4 MLCo film can thus be estimated to mS// = (0.93 + 0.13) µB/at and mL// = (0.134 + 0.022) µB/at in the H// configuration. Similar estimations for the Hconfiguration lead to mS = (0.85 + 0.11) µB/at and mL = (0.128 + 0.022) µB/at. These values are significantly lower than the bulk magnetic moments (mS = 1.55 µB/at and mL = 0.153 µB/at) [30]. We stress that a thicker Co film of nanolines should be deposited to recover bulk magnetic moments in the upper layers grown on the magnetic dead layer. These values are also significantly lower than the ones reported in our precedent work [16] for a 2 MLCo Co film (mS = 1.66 µB/at ; mL = 0.20 µB/at). A closer inspection of the XAS spectra shown in Figs.

3(a) and 3(b) published in [16] reveals that the shoulder at +4eV above the L3 edge is more pronounced in [16] than in the present work, suggesting that the chemical composition of the grown film or of the Si-Co interface was different in our previous study. The higher magnetic moments measured in [16] could result, for instance, from a less pronounced effect of the magnetic dead layer observed in the Co film. Field-dependent magnetization curves, obtained from the XMCD signal for a coverage of 4 MLCo, have been recorded at 4 K for different angles  varying from normal incidence ( = 0°) to grazing incidence ( = 70°) in the H// and H configurations (see Fig. 4). No significant remanent magnetization at zero magnetic field was observed for both configurations, indicating the absence of long-range ferromagnetic order. However, the square shape of the magnetization curves suggests a short-range magnetic order and therefore an interatomic magnetic coupling. The angular dependence of the magnetization measured for an applied magnetic field of 0.25 T and normalized to the saturation value at 6 T is plotted in the inset of Figs. 4(a) and 4(b) for the H// and H configurations, respectively. The results clearly evidence that an in-plane magnetization is favored. The MAE in the directions parallel and perpendicular to the nanolines can be derived from the magnetization curves along the easy and hard axes displayed in Figs. 4(a) and 4(b) using Eq. (2) in Ref. [33]. We obtain a MAE in the direction parallel to the Co nanolines : K// = (48 + 10 ) µeV/at and a MAE in the direction perpendicular to the Co nanolines : K = (51 + 10 ) µeV/at. These values are slightly lower than bulk h.c.p. Co (70 µeV/at). Surprisingly, the measured MAE is similar in both directions, suggesting an isotropic in-plane magnetization. Nevertheless, since strong in-plane anisotropic behavior of the magnetization has been evidenced theoretically and experimentally in similar 1D Co-and Fe-based systems [6,8,11,14], such isotropic in-plane magnetization is not expected. We outline than no privileged in-plane orientations for the magnetization other than the direction parallel or perpendicular to the chains have been reported in all these studies. Interestingly, a theoretical study has shown that for Co monoatomic wires deposited on Cu(001), the easy axis is along the wires with a very small energy barrier between the directions parallel and perpendicular to the chain axis [14]. Similarly, a weak in-plane magnetic anisotropy between the axes parallel and perpendicular to the nanolines may be present, hidden in the uncertainty of our MAE measurements. To provide a comprehensive description of the magnetic behavior of our Co system, temperature-dependent magnetization measurements have been carried out. In Fig. 5, we have plotted the magnetization measured for an applied magnetic field H// and H of 0.25 T as a function of the temperature, after having applied a magnetic field of 6 T. A plateau is observed below 20 K for both H// and H configurations, suggesting that a transition from a blocked state to a superparamagnetic configuration occurs above 20 K. We can thus estimate that the blocking temperature TB is between 20 K and 40 K. where MSat is the saturation value of the magnetization, 𝒆 ̂, 𝒎 ̂𝒕𝒐𝒕 , and 𝑯 ̂ represent the unit vectors of the easy axis direction, the magnetic moment per atom and the field direction, respectively and 𝒎 ⃗⃗⃗ 𝐭𝐨𝐭 , 𝐇 ⃗⃗ represent the vectors of the magnetic moment per atom and the applied field, respectively.

The integration is carried out over the solid angle Ω of the magnetic moment in spherical coordinates.

Considering that the upper Co layers are decoupled from the metallic silver substrate by the weakly magnetic first two Co layers, the total magnetic moments in both configurations of the two upper Co layers are given by mtot// = mL// + mS// and mtot = mL + mS. The dashed lines in Figs. 6(a) and 6(b) represent the magnetization given by Eq. ( 1) with N=1. We clearly see that the magnetic response of our Co system is different from the one expected for an assembly of isolated Co atoms. Thus, the Co nanolines behave more likely as a superparamagnetic system composed of segments (spin blocks) containing N exchange-coupled Co atoms. We define N// and N the number of coupled Co atoms derived from Eq. ( 1) with a magnetic field applied along and perpendicularly to the axis of the nanolines, respectively. By fitting with Eq. (1) the experimental magnetization curves shown in Figs. The fits made at T= 40 K, 60 K, 80 K and 100 K are summarized in Table I. The upper (respectively lower) values of N// and N are obtained by fitting the magnetization with the lower (respectively upper) values of the total magnetic moment and the MAE. We can assume that within the uncertainties N// and N remain constant while varying the temperature, leading to an average value of (171 + 30) Co atoms and (163 + 25) Co atoms, respectively. Thus, as expected, N// and N are identical within the uncertainties. A statistical analysis of STM images published in [25] revealed that, in the early stages of growth, more than 80% of the Co dimer nanolines are coupled to a second nanoline of similar length on the same Si DNRs. Thus, considering double rows of Co dimers and the two upper Co magnetic layers, the length of a spin block measured in the H// configuration corresponds to N///8 = (21 + 4) dimers i.e. (9 + 2) nm and to N/8 = (20 + 3) dimers i.e. (8.5 + 1.5) nm in the H configuration. We outline that from an experimental point of view, the size of the spin blocks cannot be straightforwardly compared to the length of the Co nanolines since XMCD probes the magnetic response of the whole Co ultrathin film while STM gives only access to the morphology of the top layer. In our case of a nonperfect layer-by-layer growth, we thus solely observe by STM the uncovered parts of the different Co layers. Nevertheless, the length of the spin blocks is remarkably similar to the length of the Co nanolines ( 6 nm) estimated from STM measurements. We remind that this length has been assimilated to the nanoline length of the first Co layer. It can be assumed that, during the growth, some Co nanolines in the upper layers have coalesced in the direction parallel to the Si NRs, forming longer Co nanolines. Moreover, the larger length derived from our fits could result from the fact that the contribution of the first two Co layers is not considered in the fits using Eq. ( 1). Even if XMCD measurements revealed that these two Co layers have a weak magnetic response, taking into account their contribution would reduce the estimated length of the spin blocks. Thus, our fit process strongly suggests that the Co system behaves as a superparamagnetic system composed of thermally fluctuating 1D segments.

IV. CONCLUSION

The combined STM-XMCD study reported in this paper provides a comprehensive description of the magnetic Co nanolines grown on a 1D Si nanotemplate. The Co ultrathin film,  4 MLCo thick, is composed of dimer nanolines aligned with respect to the Si NRs and are  6 nm in length. Fielddependent magnetization measurements evidence that an in-plane magnetization is favored. The Co system behaves as a superparamagnetic system composed of thermally fluctuating 1D segments (spin blocks) of two layers thick, containing each  170 coupled Co atoms. The length of the spin block,  9 nm, is found to be similar to the length of the grown Co nanolines. This length is didacted by the Co diffusion into the Si layer. It would appear interesting to grow longer nanolines to known whether the ferromagnetic coupling of magnetic atoms is limited by the length of the nanolines or is related to the occurrence of critical fluctuations. Finally, we stress that our study illustrates the richness of the magnetic anisotropy of low dimensional systems.

FIG. 1 :

 1 FIG. 1: (a) STM image of Co nanolines grown at 220 K on the 52 Si nanoribbon array. Co nanolines of the 1 st and 2 nd layers are indicated by colored rectangles (b) Height profile along the blue line in (a), showing typical corrugations associated with the different grown nanostructures on Ag(110).

Fig. 3 (

 3 Fig. 3(b) shows the XAS spectra at 4 K for both x-ray polarizations and respectively H// (upper panel) and H (middle panel). The XAS spectra, that clearly show no trace of cobalt silicides, are characteristic of metallic Co [5]. Two broad absorption resonances are clearly visible at the L3 and L2 edges of Co. The weak shoulder peak present at about 4 eV above the L3 edge can be attributed to the presence of interface states for Co atoms located at the Co/Si interface as suggested by Pong et al. [27].

FIG. 3 :

 3 FIG. 3: (a) Schematic representation of the H// and H configurations for the XAS and XMCD measurements. For the angle dependant measurements, the sample was rotated by an angle  relative to the surface normal, from normal ( = 0 °) to grazing incidence ( = + 70°). (b) XAS spectra for a Co coverage of 4 MLCo, taken at grazing incidence (θ) at 4 K with a magnetic field of 6 T for both light helicities (µ+ and µ-) and for H (upper panel) and H// (middle panel). The corresponding XMCD spectra are displayed in the lowest panel for both H// and H configurations.

FIG. 4 :

 4 FIG. 4: Magnetization (M) of 4 MLCo recorded at 4 K at the L3 Co edge. M as a function of the applied field in the (a) H// configuration and (b) H configuration. Magnetization curves are measured at the grazing incidence ( = 70°, filled red dots and filled blue squares) and at the normal incidence ( = 0°, open red dots and open blue squares). The curves have been normalized to their saturation value at 6 T. Insets: angular dependence of the magnetization. Variation in both configurations of the magnetization at 0.25 T normalized to the saturation magnetization at 6 T (Msat) as a function of the incidence angle θ. The solid lines are fits of the data according to the function asin(-0 ).

FIG. 5 :

 5 FIG. 5: Variation of the magnetization for an applied magnetic field of 0.25 T normalized to the saturation magnetization at 6 T (Msat) as a function of the temperature, for an applied magnetic field H// (filled red dots) and H (filled blue squares) at  = 70°. Black dashed lines are eye-guides for the blocked state and the superparamagnetic behavior.

  FIG. 6: Magnetization (M) of 4 MLCo recorded at 60 K at the L3 Co edge. (a) M as a function of the applied field measured in the H// configuration with  = 70°, normalized to its saturation value at 6 T (filled red dots). The solid line is the fit to the data according to Eq. (1) with mtot//= 1.06 µB/at and K// = 48 µeV/at, giving N// = 171. The dashed line corresponds to the magnetization of an isolated Co atom, given by Eq. (1) with N =1. (b) the same as (a) in the H configuration with mtot= 0.98 µB/at and K = 51 µeV/at, giving N = 174. Experimental magnetization M is represented with filled blue squares.

  TableI. Values of N// and N as a function of the temperature derived from fits of the experimental magnetization of 4 MLCo according to Eq. (1).

ACKNOWLEDGMENTS

Support from the DEIMOS beamline staff at SOLEIL is greatly acknowledged. The authors gratefully thank Andrés Saúl and Philippe Ohresser for fruitful discussions.


Giulia Bernardini
email: giulia.bernardini@unimib.it

Alessio Conte

Garance Gourdel
email: garance.gourdel@ens-paris-saclay.fr

Roberto Grossi

Grigorios Loukides
email: 5grigorios.loukides@kcl.ac.uk

Nadia Pisanti
email: nadia.pisanti@unipi.it

Solon P Pissis
email: 6solon.pissis@cwi.nl

Giulia Punzi
email: giulia.punzi@phd.unipi.it

Leen Stougie
email: leen.stougie@cwi.nl

Michelle Sweering
email: michelle.sweering@cwi.nl

Hide and Mine in Strings: Hardness and Algorithms

Keywords: data privacy, data sanitization, knowledge hiding, frequent pattern mining, string algorithms

We initiate a study on the fundamental relation between data sanitization (i.e., the process of hiding confidential information in a given dataset) and frequent pattern mining, in the context of sequential (string) data. Current methods for string sanitization hide confidential patterns introducing, however, a number of spurious patterns that may harm the utility of frequent pattern mining. The main computational problem is to minimize this harm. Our contribution here is twofold. First, we present several hardness results, for different variants of this problem, essentially showing that these variants cannot be solved or even be approximated in polynomial time. Second, we propose integer linear programming formulations for these variants and algorithms to solve them, which work in polynomial time under certain realistic assumptions on the problem parameters.

I. INTRODUCTION

A string is a sequence of letters over some alphabet Σ. Strings are commonly used to represent individuals' data in domains ranging from transportation to web analytics and bioinformatics. For example, a string can represent a user's location profile, with each letter corresponding to a visited location [START_REF] Ying | Semantic trajectory mining for location prediction[END_REF], a user's purchasing history, with each letter corresponding to a purchased product [START_REF] Agrawal | Mining sequential patterns[END_REF], or a patient's genome sequence, with each letter corresponding to a DNA base [START_REF] Koboldt | The next-generation sequencing revolution and its impact on genomics[END_REF]. Mining patterns from such strings is thus useful in a gamut of applications, including route planning [START_REF] Chen | Mining moving patterns for predicting next location[END_REF], marketing [START_REF] Agrawal | Mining sequential patterns[END_REF], and clinical diagnostics [START_REF] Koboldt | The next-generation sequencing revolution and its impact on genomics[END_REF]. To support these applications while preserving privacy, strings representing individuals' data are often being disseminated after sanitization [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF], [START_REF] Wu | Hiding sensitive association rules with limited side effects[END_REF].

In this paper, we study the fundamental relation between data sanitization [START_REF] Abul | Hiding sequential and spatiotemporal patterns[END_REF], [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF], [START_REF] Wu | Hiding sensitive association rules with limited side effects[END_REF] (also known as knowledge hiding) and frequent pattern mining [START_REF] Keich | Finding motifs in the twilight zone[END_REF], [START_REF] Martinez | An efficient method for finding repeats in molecular sequences[END_REF], [START_REF] Shen | Sequential pattern mining[END_REF]. The objective of frequent pattern mining in strings is to obtain all patterns occurring frequently enough in a string, or in a collection of strings. There may also be constraints for the mined strings (e.g., to be of fixed length k [START_REF] Arimura | An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence[END_REF], [START_REF] Cristianini | Introduction to computational genomics -a case studies approach[END_REF]). In string sanitization, the privacy objective is to transform a string to ensure that a given set of sensitive patterns, modeling confidential knowledge, does not occur in the sanitized version of the string; sensitive patterns are selected based on domain expertise [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF], [START_REF] Gkoulalas-Divanis | Revisiting sequential pattern hiding to enhance utility[END_REF], [START_REF] Wu | Hiding sensitive association rules with limited side effects[END_REF]. This transformation may incur some utility loss that should be minimized. Recent methods achieve this using combinatorial algorithms [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF], [START_REF] Bernardini | String sanitization under edit distance[END_REF]. Let W be the input string over Σ, k > 0 be an integer, and S be the set of sensitive length-k substrings. These methods construct a string X such that: (I) X contains no element of S as a substring; (II) the total order and thus the frequency of all non-sensitive length-k substrings of W is preserved in X; and (III) the length of X is minimized [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF], or the edit distance between W and X is minimized [START_REF] Bernardini | String sanitization under edit distance[END_REF]. These methods work by copying carefully selected substrings of W into X and separating them by a special letter # / ∈ Σ.

Example 1. Let W = GACAAAAACCCAT, k = 3, and the set of sensitive patterns S = {ACA, CAA, AAA, AAC, CCA}. Further, let X TR = GAC#ACC#CCC#CAT, X MIN = GACCC#CAT and X ED = GAC#AA#ACCC#CAT be three sanitized strings. All three strings contain no sensitive pattern and preserve the total order and thus the frequency of all nonsensitive length-3 patterns of W : X TR is the trivial solution of interleaving the non-sensitive length-3 patterns of W with #; X MIN is the shortest possible such string [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF]; and X ED is a string closest to W in terms of edit distance [START_REF] Bernardini | String sanitization under edit distance[END_REF].

Unfortunately, as noted in [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF], the occurrences of # reveal the locations of sensitive patterns and thus must be ultimately replaced by letters of the original alphabet Σ. This replacement gives rise to another string over Σ, which we denote by Z. However, this replacement may create spurious patterns that could not be mined from X at a minimum frequency threshold τ but would be mined from Z at the same frequency threshold. These patterns are referred to as τ -ghosts.

We investigate the crucial interplay between # replacements and τ -ghosts, posing here the following question that, to the best of our knowledge, has not been addressed: Given a string X containing #'s, a positive integer k, and a positive integer τ , how should we replace the #'s in X with letters in Σ, so that the number of length-k τ -ghosts in the resulting string Z is minimized? This question helps preserving the accuracy of frequent pattern mining and tasks based on it (e.g., pattern-based clustering [START_REF] Guralnik | A scalable algorithm for clustering sequential data[END_REF] and classification [START_REF] Rangavittal | RecoverY: k-mer-based read classification for Y-chromosome-specific sequencing and assembly[END_REF], as well as sequential rule mining [START_REF] Spiliopoulou | Managing interesting rules in sequence mining[END_REF]) that we may not know a priori.

The above question is also of quite general interest, as it applies to sequential datasets that may have occurrences of a special letter for a variety of reasons beyond data sanitization. This special letter, denoted here by # for consistency, represents some information that is missing from these datasets. For instance, in genome sequencing data, # corresponds to an unknown DNA base [START_REF]IUPAC-IUB Commission on Biochemical Nomenclature. Abbreviations and symbols for nucleic acids, polynucleotides, and their constituents[END_REF]; in databases, # represents a value that has not been recorded [START_REF] Biessmann | deep" learning for missing value imputationin tables with non-numerical data[END_REF], [START_REF] Fiot | Approximate sequential patterns for incomplete sequence database mining[END_REF]; and in masked data outputted by other privacy-preserving methods [START_REF] Bier | The rules of redaction: Identify, protect, review (and repeat)[END_REF], # is introduced deliberately to achieve their privacy goal.

Like in data outputted by sanitization methods, the occurrences of # in other string datasets often have to be replaced. For example, since the DNA alphabet consists of four letters (A, C, G, and T), off-the-shelf algorithms for processing DNA data use a two-bits-per-base encoding to represent the DNA alphabet. In order to use these algorithms with input strings containing unknown bases, we would have to amend them to work on the extended alphabet {A, C, G, T, #}. This solution may have a negative impact on the time efficiency of the algorithms or the space efficiency of the data structures they use. Thus, instead, in several state-of-the-art DNA data processing tools (e.g., [START_REF] Li | SOAP2: an improved ultrafast tool for short read alignment[END_REF]), the occurrences of # are replaced by an arbitrarily chosen letter from the DNA alphabet, so that off-the-shelf algorithms can be directly employed. This, however, may introduce a large number of spurious patterns, negatively affecting the accuracy of DNA analyses.

Replacing the occurrences of # in a database is often needed to be able to perform frequent pattern mining with offthe-shelf algorithms [START_REF] Fiot | Approximate sequential patterns for incomplete sequence database mining[END_REF]. To this end, the occurrences of # are commonly replaced by some statistical estimate, such as the most frequent value [START_REF] Fiot | Approximate sequential patterns for incomplete sequence database mining[END_REF], [START_REF] Grzymala-Busse | A comparison of several approaches to missing attribute values in data mining[END_REF]. However, such a replacement does not generally maintain the accuracy of frequent pattern mining, since it may introduce many spurious patterns [START_REF] Fiot | Approximate sequential patterns for incomplete sequence database mining[END_REF].

Example 2. Let again W = GACAAAAACCCAT, k = 3, and S = {ACA, CAA, AAA, AAC, CCA}. Further, let the frequency threshold be τ = 2. Note that the frequency of all non-sensitive length-3 patterns in W is preserved in all three sanitized strings X TR = GAC#ACC#CCC#CAT, X MIN = GACCC#CAT, and X ED = GAC#AA#ACCC#CAT. Replacing, however, all #'s with G would create τ -ghost GAC both in X TR and in X ED .

Contributions. To our knowledge, there does not exist a general solution to the question we pose here that simultaneously guarantees effectiveness and efficiency. In this work, we provide compelling evidence as to why this is the case. Within the string sanitization context, we also provide algorithms for answering this question. Specifically: 1) We embark on a theoretical study to understand the relation between replacing #'s and creating τ -ghosts. In particular, we define the following problems and examine their hardness:

• HMD (Hide and Mine decision): This is the core decision version of the problem asking whether or not we can replace all #'s in X, so that no sensitive pattern and no τ -ghost occurs in Z. Deciding this may allow for sanitizing X with no utility loss in frequent pattern mining. We show that HMD is strongly NP-complete via a reduction from a variant of the well-known Bin Packing problem [START_REF] Garey | Strong" NP-completeness results: Motivation, examples, and implications[END_REF] (see Section III). This is the most technically involved part of the paper, as the provided reduction is highly non-trivial. • HM (Hide and Mine): This is the optimization version of HMD asking how we can replace all #'s, while ensuring that no sensitive patterns and a minimal number of τghosts occur in Z. This would minimize the utility loss in frequent pattern mining. HM is clearly NP-hard as a consequence of HMD being NP-complete, but we also show that it is hard to approximate. • HMMT (Hide and Mine minimum threshold): Given a parameter τ , this problem asks for the minimum frequency threshold τ 1 ≥ τ for which no sensitive pattern and no τ 1ghost occurs in Z. Solving HMMT would imply no utility loss in frequent pattern mining at a higher frequency threshold τ 1 that is as close as possible to τ . We show that HMMT is (NP-hard and) hard to approximate. The hardness (see Section III) and inapproximabilty (see Section IV) results for our problems provide solid evidence for the lack of polynomial-time exact or approximation algorithms for these problems and motivate our next contribution.

2) We develop exact algorithms for HMD and HM (see Section V) that require polynomial time, under certain realistic assumptions on the problem parameters:

• Exact algorithms based on an Integer Linear Programming (ILP) formulation of HMD. The main idea is to identify all length-k strings over Σ in X that may potentially become τ -ghosts in Z, and then decide whether each of the #'s can be replaced by a letter in Σ without creating any sensitive pattern or any τ -ghost pattern in Z. We prove that HMD is fixed-parameter tractable [START_REF] Cygan | Parameterized Algorithms[END_REF] in most cases encountered in practice (e.g., when the number of distinct letters in the string and the length k of sensitive patterns are upper bounded by a constant). • Exact algorithms based on an ILP formulation of HM.

This ILP formulation differs from the HMD formulation in that it takes into account the number of τ -ghosts created by replacing #'s, so as to minimize their number. We prove that HM is fixed-parameter tractable in many cases encountered in practice (e.g., when the length k of sensitive patterns and the number of distinct patterns that may become τ -ghosts are upper bounded by a constant).

II. PRELIMINARIES AND PROBLEM STATEMENT

An alphabet Σ is a finite nonempty set whose elements are called letters. We also consider an alphabet

Σ # = Σ ∪ {#}, where # is a special letter not in Σ. We fix a string X = X[0] • • • X[n -1] of length |X| = n over Σ # . The set of length-k strings over Σ is denoted by Σ k . For two indices 0 ≤ i ≤ j < n, X[i . . j] = X[i] • • • X[j]
is the substring of X that starts at position i and ends at position j of W . Freq X (U ) denotes the number of occurrences (starting positions) of string U as a substring of X. A prefix of X is a substring of X of the form X[0 . . j], and a suffix of X is a substring of X of the form X[i . . n-1]. A dictionary over Σ is a set of strings over Σ. The dictionary used in our work is a set of length-k strings that do not occur in X; we refer to these strings as sensitive patterns. Any element of Σ k that is not in this dictionary is referred to as a non-sensitive pattern. In combinatorics on words, such a dictionary is known as antidictionary and the sensitive patterns are known as forbidden patterns (e.g., see [START_REF] Crochemore | Text compression using antidictionaries[END_REF]).

Problem 1 (HIDE & MINE (HM)). Given an integer

k > 0, a string X = X 0 #X 1 # • • • #X δ of length n over an alphabet Σ # , with |X i | ≥ k -1, for all i ∈ [0, δ],
a dictionary S ⊆ Σ k such that no S ∈ S occurs in X, and an integer τ > 0, compute a function g : [δ] → Σ such that the following hold for string

Z = X 0 g(1)X 1 g(2) • • • g(δ)X δ : I The number of strings U ∈ Σ k , with Freq X (U ) < τ and Freq Z (U ) ≥ τ in Z, is minimized. II No S ∈ S occurs in Z.
Note that function g replaces each # by exactly one letter from Σ. Condition |X i | ≥ k -1 means that any two #'s in X are at least k positions apart. Thus, any length-k substring X[i . . i+k-1] of X is affected by at most one # replacement. The sanitization method of [4, Lemma 1] produces an X satisfying this condition, for any set S ⊆ Σ k , to guarantee that the frequency of every non-sensitive pattern is preserved in X. Thus, HM is directly applicable to the output of [START_REF] Bernardini | String sanitization: A combinatorial approach[END_REF].

A string U ∈ Σ k with Freq X (U ) < τ and Freq Z (U ) ≥ τ is referred to as τ -ghost. To prove NP-completeness, we consider the decision variant HMD of HM, which asks to decide if there exists any function g : [δ] → Σ such that the following hold:

I No τ -ghost occurs in Z. II No S ∈ S occurs in Z.

III. HMD IS NP-COMPLETE

Problem HMD is clearly in NP. In this section, we show it to be strongly NP-complete via a reduction from a variant of Bin Packing [START_REF] Garey | Strong" NP-completeness results: Motivation, examples, and implications[END_REF].

A. The UNIQUE-WEIGHTS BIN PACKING problem

The BIN PACKING (BP) problem is defined as follows. Given three positive integers, M (number of bins), B (capacity of every bin), and N (number of items), and a vector [w 1 , . . . , w N ] of positive integers (the weights of the items), BP asks whether we can partition the items into M subsets (bins) without exceeding the capacity of any bin.

BP is strongly NP-complete [START_REF] Garey | Strong" NP-completeness results: Motivation, examples, and implications[END_REF], i.e., it is NP-complete even when weights and bin capacities are bounded by a polynomial function of N and M . We can thus use gadgets whose size is proportional to the numerical values in the instance I BP of BP, as if we were representing those numbers in unary notation. To simplify the reduction, we assume there are no items of weight 1 (they can be added at the end where capacity is left), and that no two items have the same weight. We refer to this variant as UNIQUE-WEIGHTS BIN PACKING (UWBP). UWBP is also strongly NP-complete; we defer the proof of this claim to the full version of the paper.

Lemma 1. UWBP is strongly NP-complete.

B. Overview of the Reduction from UWBP to HMD

For any UWBP instance, we construct in polynomial time an instance of HMD that has positive answer if and only if UWBP has positive answer. To this end, we will introduce several gadgets which will serve to model the different constraints of UWBP. Each gadget consists of a string of length 2k -1 over a specific alphabet: #, x, y, $, and a letter b i for each i ∈ [M ]. We will explain how all UWBP constraints are linked to the gadgets. The gadget t ij models whether item j ∈ [N ] is placed in bin i ∈ [M ]:

t ij = b i x . . . x k-wj -1 b i . . . b i wj -1 # b i . . . b i k-1
The structure models the weight of items placed in bin i: when we replace the # with b i , we introduce w j occurrences of b k i . The gadget u ij , together with t ij and the set of forbidden patterns, ensures that each item is placed in some bin:

u ij = b i x . . . x k-wj -1 b i . . . b i wj -1 # y . . . y wj x . . . x k-wj -2 y
We link the filling of the ith bin with the number of occurrences of b k i . To limit the other non-sensitive patterns flexibly, we then choose a value τ high enough, and lower the available occurrences of each pattern by adding extra copies of them at the end. Namely, we have k = max j w j + 3 and τ = max{M, B} + 1.

The final instance of HMD is the concatenation of the following patterns separated by the string $$:

1) t ij , ∀i, j. 2) u ij , ∀i, j. 3) τ -B -1 occurrences of b k i , ∀i (allowed occurrences of b k i model the capacity of bin i). 4) τ -2 occurrences of b i x k-wj -1 b wj -1 i
x, ∀i, j (only one more occurrence of this pattern is allowed, and one is created by replacing the # in t ij or u ij with x). 5) τ -M occurrences of y wj +1 x k-wj -2 y, ∀j (allowed occurrences force us to replace at least one u •j with x for each j, thus forcing us to use b ij in the corresponding t ij gadget, i.e., placing each item in a bin). The set S of sensitive patterns is carefully chosen to link these gadgets, and consists of the union of the following sets:

1)

{b i b k-1 i | i, i ∈ [M ], i = i}, which forbids putting a b i to replace the # in any t ij , if i = i. 2) {b i yb k-2 i | i ∈ [M ]}, which forbids putting a y to replace the # in a t ij . 3) {b i $b k-2 i | i ∈ [M ]}, which forbids putting a $ to replace the # in a t ij . 4) {b i y wj x k-wj -2 y | i ∈ [M ], j ∈ [N ]}, which forbids putting any b i to replace the # in a u ij . 5) {b i $y wj x k-wj -2 | i ∈ [M ], j ∈ [N ]
}, which forbids putting a $ to replace the # in a u ij . It can be shown that this instance of HMD has positive answer if and only if the original UWBP does, thus proving our claim. We defer the details to the full version of the paper.

Theorem 1. HMD is strongly NP-complete.

IV. HM IS HARD TO APPROXIMATE

Given the hardness of HMD, we now shift our focus on checking whether an approximately optimal solution of HM can be obtained instead. Given any instance I M of a minimization problem M , an algorithm is called an α-approximation, for some α ≥ 1, if it runs in polynomial time in the size of I M and always outputs a solution value Γ ≤ α • OPT, where OPT denotes the optimal value for I M . We start with the following: Theorem 2. There is no α-approximation algorithm for HM, for any α ≥ 1, unless P=NP.

Proof. Suppose by contradiction that an α-approximation algorithm A existed for minimizing the number of τ -ghosts in HM. We could then use A to solve HMD: the answer to HMD would be positive (i.e., there would exist a function g that creates 0 τ -ghosts) if and only if the answer of A was Γ = 0 ≤ α • OPT = 0, which contradicts Theorem 1.

The reader may now wonder whether the problem becomes easier should one relax the requirement for a fixed threshold τ . Thus, the following problem arises naturally.

Problem 2 (HMMT). Given an integer

k > 0, a string X = X 0 #X 1 # • • • #X δ of length n over alphabet Σ # , with |X i | ≥ k -1 for all i ∈ [0,
δ], a dictionary S ⊆ Σ k such that no S ∈ S occurs in X, and an integer τ 0 > 0, compute the smallest integer τ 1 ≥ τ 0 so that there exists a function g : [δ] → Σ, such that the following hold for string

Z = X 0 g(1)X 1 g(2) • • • g(δ)X δ : I No U ∈ Σ k , with Freq X (U ) < τ 1 and Freq Z (U ) ≥ τ 1 occurs in Z. II No S ∈ S occurs in Z.
The practical rationale for considering HMMT is that it could be useful if, for instance, τ 1 is only slightly larger than τ in a given HM instance. Unfortunately, we show that HMMT is NP-hard, and it is even hard to approximate. Theorem 3. HMMT is NP-hard.

Proof. We reduce HMD to HMMT as follows. Let I HMD be the instance of HMD we would like to solve for some threshold τ . We construct an instance of HMMT consisting of the X, k, and S from I HMD , and we also set τ 0 = τ . We denote this instance by I HMMT . The reduction takes linear time in the size of HMD. We seek to find the minimum threshold τ 1 ≥ τ 0 such that no length-k substring of Z is a τ 1 -ghost. Then I HMD has a positive answer if and only if the answer τ 1 of I HMMT is equal to τ 0 = τ . The statement thus follows.

Observe that a pattern U is a τ -ghost if and only if τ ∈ (Freq X (U ), Freq Z (U )]. Therefore, the minimal number of τ -ghosts is not monotonous in τ . On the contrary, the minimal number of τ -ghosts is zero when τ = 0 and all patterns are already frequent (i.e., they appear at least τ times), or when τ > n and the threshold is so high that no pattern can ever become a τ -ghost. In between, the minimal number of τ -ghosts increases whenever τ equals the frequency of some patterns in X, and then slowly decreases again. We will use this behavior, and the fact that HMD is NP-hard, to construct a string for which we cannot determine in polynomial time whether τ 1 = τ 0 or τ 1 > ατ 0 (and for which we can prove that τ 1 ∈ [τ 0 + 1, ατ 0 ]), implying inapproximability. Theorem 4. There is no α-approximation algorithm for HMMT, for any α ≥ 1, unless P=NP.

Proof. Let X be an arbitrary string and S be the set of sensitive patterns as defined in HMD. Further, let T be the length-(k -2) suffix of X and Z be a string obtained by replacing the #'s of X. From this instance of HMD, we will construct an instance of HMMT consisting of a string Y and a set S of sensitive patterns, so that if an α-approximation algorithm existed for HMMT, we could decide HMD in polynomial time. We define Y over Σ ∪ {#, &} to be

Y = X(&&T ) τ0 &(#T &) (α-1)τ0 .
Let R be the set of all strings &sT , with s ∈ Σ. We define the dictionary of sensitive patterns be S = S ∪ R. Note that we need to replace all #'s in (#T &) (α-1)τ0 by &'s in order not to introduce any sensitive patterns. However, doing so increases the number of &T & patterns (and all other newly created patterns) from τ 0 to ατ 0 . Therefore, if τ = τ 0 , then the number of τ -ghosts in Z equals that in Z(&&T ) τ0 &(&T &) (α-1)τ0 , because the additional new patterns were already occurring at least τ times in Y . However if τ 0 < τ ≤ ατ 0 , then there will always be at least one τ -ghost, namely &T &. Recall that deciding HMD is NPcomplete. Therefore it is NP-complete to decide whether or not τ 1 = τ 0 or τ 1 > ατ 0 . We conclude that there exists no α-approximation algorithm for HMMT, unless P=NP.

V. EXACT ALGORITHMS FOR HM

We resort to ILP to design exact algorithms for HMD and HM. In particular, we show that both problems are fixedparameter tractable for several combinations of parameters.

We say that the length-(k-1) substring U preceding an occurrence of # in X, and the length-(k-1) substring V following it, form its context U V . Recall that there are δ occurrences of # in X, and that any two occurrences are at least k letters apart, so U V is in Σ 2k-2 . We assign to every context U V a unique identifier (id). We write # i for # in X if its context U V has id i. A string N ∈ Σ k is critical if it may become a τ -ghost, i.e., if an additional occurrence of N can be created by replacing some # by a letter in Σ and Freq X (N ) ∈ [τ -kδ, τ -1]. This is because the frequency of N cannot increase by more than kδ, and the frequency of N in X must be less than τ for N to become τ -ghost. We assign to each critical string N a unique id , and denote it by N . We introduce the following parameters:

γ number of distinct contexts present in X; δ i number of occurrences of letter # i in X, for i ∈ [γ]; λ number of distinct critical length-k strings; α i ,j
additional number of occurrences of N introduced by replacing a # i with a letter j ∈ Σ, for ∈

[λ]; e difference (τ -1) -Freq X (N ), for ∈ [λ].
Intuitively, e is the budget we have for N : the number of its additional occurrences we can afford. Since replacing an occurrence of # i by j ∈ Σ adds k new strings in Σ k , α i ,j counts how many of them are equal to N . Let x i,j be the number of times we replace # i by j ∈ Σ, and let F ⊆ [γ]×Σ be the set of forbidden replacements: (i, j) ∈ F if and only if replacing # i by j introduces a sensitive pattern. To determine whether there exists a way of replacing all #'s with letters without introducing any sensitive patterns nor τ -ghosts, we need to find a solution x ∈ Z γ×|Σ| to the following problem:

         x i,j ≥ 0 ∀(i, j) ∈ [γ] × Σ x i,j = 0 ∀(i, j) ∈ F i∈[γ],j∈Σ α i ,j x i,j ≤ e ∀ ∈ [λ] j∈Σ x i,j = δ i ∀i ∈ [γ] (1)
The first and fourth constraints ensure that each # is replaced by exactly one letter, the second constraint that we do not reinstate any sensitive patterns, and the third constraint that we do not introduce any τ -ghosts. This is clearly an ILP with m = γ|Σ| variables and at most 2m+λ+γ constraints. The well-known algorithm by Megiddo [START_REF] Megiddo | Linear programming in linear time when the dimension is fixed[END_REF] solves the ILP problem in linear time in the number constraints (resp. variables) when the number of variables (resp. constraints) is upper bounded by a constant. Hence, although HMD is NP-complete in general, if appropriate subsets of parameters are bounded by a constant, we can count on polynomial-time solutions.

To show that HMD takes polynomial time in certain cases, let us start with a general preprocessing step. We construct a static dictionary with O(1) access time of the letters in X and the letters in strings of S. The value (id) of each key (letter) is chosen from {1, . . . , k|S| + n}. This construction can be done in O(n + k|S|) time using perfect hashing [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF]. We can thus lexicographically sort all length-k substrings of X and all length-k strings in S (viewed as strings over letter id's) using radix sort in O(nk + |S|k) time, and construct two dictionaries, one for X and one for S, as follows. For X, we construct a trie of all its non-sensitive length-k substrings. The value of each key (non-sensitive pattern) is its multiplicity in X. We also construct a trie of all strings in S in a similar fashion (no multiplicities are relevant here, so no values are stored). We store in both tries, for every node, the first letter on each of its outgoing edges in a static dictionary with O(1) access time [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF]. Thus both trie dictionaries support O(k) access time: if a length-k string Q is given as a query, we first convert it to a string I(Q) of id's in O(k) time using the letter dictionary, and then search for I(Q) from the root of the tries in O(k) time. The total construction time is O(nk+|S|k).

When δ = O(1), the brute-force algorithm checking all possible ways to replace the #'s with letters of Σ runs in polynomial time. There are |Σ| δ ways to replace the #'s. Each of these ways generates δk new length-k strings for which we have to check if they are sensitive or create a τ -ghost. Checking if they are sensitive can be done using the trie of S in O(k) time per each length-k string. Counting the additional number of occurrences of each length-k substring of X can be done using the trie of X in O(k) time. Counting the number of occurrences of each length-k string that does not occur in X can be done by constructing a trie of all such strings (we have at most δk of them per way), similar to the preprocessing step. This gives O(nk + |S|k + |Σ| δ δk 2 ) time in total.

A problem with parameters p and q is fixed-parameter tractable (FPT) in p if there exists a function f and a polynomial P such that the problem has time complexity O(f (p) • P (q)) [START_REF] Cygan | Parameterized Algorithms[END_REF]. The following theorem shows three scenarios where an FPT algorithm exists for HMD. Proof. We first perform the above-mentioned preprocessing.

(a) We will solve this case by constructing and solving the ILP in Eq. 1. We can count the number of occurrences of each length-k substring of X using the trie of X (and thus determine e for these strings) in O(nk) time. The id i of each context # i and its number δ i of occurrences can be determined within the same complexity using a similar preprocessing: this is possible because the length of every context is 2k -2 = O(k). Finally, the α i ,j 's and F can be computed in O(γ|Σ|k 2 ) total time as follows. For a context # i and a letter j ∈ Σ, we create k new length-k strings when replacing # i with j, each of which is either sensitive (in which event we add (i, j) to F) or non-sensitive (we increase α i ,j by 1). Checking if they are sensitive can be done using the trie of S in O(k) time per length-k string. Counting the additional number of occurrences of a critical length-k substring of X can be done using the trie of X in O(k) time. Counting the number of occurrences of a critical length-k string that does not occur in X (note that e = τ -1 for these strings) can be done by constructing a trie of all such strings, similar to the preprocessing step. The ILP is thus constructed in O(nk + |S|k + γ|Σ|k 2 ) total time. Since the number of variables in the ILP is m = γ|Σ| = O(1) and solving ILP's is fixed-parameter linear in the number of variables [START_REF] Megiddo | Linear programming in linear time when the dimension is fixed[END_REF], HMD is FPT if γ and |Σ| are fixed. , the numbers of constraints and variables in the ILP are not necessarily upper bounded by a constant. Therefore, we cannot directly solve the ILP in polynomial time. However, since the λ critical length-k strings contain overall at most λk different letters, we actually only need to distinguish among a bounded number of letters.

Since we do not need to consider explicitly the remaining letters, we rather represent them by a single special letter. Let σ ⊆ Σ denote the set of letters contained in critical length-k strings. Note that critical length-k strings can be determined as described in part (a). Thus σ can be specified and indexed using perfect hashing [START_REF] Fredman | Storing a sparse table with O(1) worst case access time[END_REF] within the same time complexity. We introduce a new letter $ representing all the letters in Σ\σ, and we denote by F| $ the set of forbidden replacements where all pairs (i, j) ∈ F with j ∈ Σ \ σ are collapsed in a single pair (i, $). We thus need to find a solution x ∈ Z γ×(|σ|+1) for:

         x i,j ≥ 0 ∀i ∈ [γ], j ∈ σ ∪ {$} x i,j = 0 ∀(i, j) ∈ F| $ i∈[γ],j∈σ α i ,j x i,j ≤ e ∀ ∈ [λ] j∈σ∪{$} x i,j = δ i ∀i ∈ [γ] (2)
This new ILP can be constructed in O(nk + |S|k + γ|Σ|k 2 ) time, like Eq. 1. Since the ILP has only γ(|σ| + 1) = O(1) variables, HMD is FPT for fixed k and λ [START_REF] Megiddo | Linear programming in linear time when the dimension is fixed[END_REF]. We can obtain a solution to the original problem by replacing $ by any letter in Σ \ σ that does not create a sensitive pattern.

We can decide in polynomial time if HM has a solution: we check all |Σ| letter replacements at each of the δ positions where a # occurs. If, at each position, there exists at least one letter replacement that does not create a sensitive pattern, then HM has a solution. Thus, without loss of generality we assume that HM always has a solution. To minimize τ -ghosts in Z, we define a binary variable z , ∈ [λ], which is equal to 1 (resp. 0) when N has (resp. has not) become τ -ghost. The ILP formulation for HM is to find x ∈ Z γ×|Σ| so as to: Minimize

λ =1 z subject to                x i,j ≥ 0 ∀(i, j) ∈ [γ] × Σ x i,j = 0 ∀(i, j) ∈ F z ≥ 0 ∀ ∈ [λ] i∈[γ],j∈Σ α i ,j x i,j -kδz ≤ e ∀ ∈ [λ] j∈Σ x i,j = δ i ∀i ∈ [γ] (3)
Note that, in the ILP of Eq. 3, i∈[γ],j∈Σ α i ,j x i,j -kδz ≤ e if and only if N is not a τ -ghost or z = 1.

Theorem 5 .

 5 HMD is fixed-parameter tractable if (a) |Σ| = O(1) and γ = O(1); or (b) |Σ| = O(1) and k = O(1); or (c) k = O(1) and λ = O(1).

  (b) Since every context has length 2k -2 and also |Σ| = O(1) and k = O(1), we have that γ ≤ |Σ| 2k-2 = O(1). Thus, if k and |Σ| are fixed, we are in case (a), and HMD is FPT. (c) If k = O(1) and λ = O(1)

Theorem 6 .

 6 HM is fixed-parameter tractable if (a) |Σ| = O(1), γ = O(1), and λ = O(1); or (b) k = O(1) and λ = O(1).Proof. (a)We can obtain the ILP of Eq. 3 in O(λ) time from the ILP of Eq. 1, which can be constructed in O(nk + |S|k + γ|Σ|k 2 ) time; see the proof of Theorem 5(a). The ILP of Eq. 3 has at most 2m + 2λ + γ constraints and m + λ = |Σ|γ + λ variables. Therefore HM is FPT if |Σ|, γ and λ are fixed[START_REF] Megiddo | Linear programming in linear time when the dimension is fixed[END_REF].(b) Similar to the ILP of Eq. 2 (see Theorem 5(c)), we can reduce the alphabet Σ to the letters of the critical length-k strings and a special letter $. This new minimization ILP has γ(|σ|+1)+λ ≤ (kλ+1) 2k-1 +λ = O(1) variables. Therefore HM is FPT if k and λ are fixed[START_REF] Megiddo | Linear programming in linear time when the dimension is fixed[END_REF].

Acknowledgments. MIUR Grant 20174LF3T8 AHeAD; University of Pisa "PRA -Progetti di Ricerca di Ateneo" (Institutional Research Grants) Grant PRA 20202021 26 "Metodi Informatici Integrati per la Biomedica"; and NWO Gravitation-grant NETWORKS-024.002.003.