S V Snegir
email: ssnegir@gmail.com

A A Khodko

D Sysoiev

E Lacaze

O Pluchery

T Huhn

 S V Snegir

Optical Properties of Gold Nanoparticles Decorated with Furan-based Diarylethene Photochromic Molecules

Keywords: photo-switching, , cyclization dynamics, furan-based diarylethene, gold nanoparticles, femtosecond pump-probe, UV/visible spectroscopy, SEM

A reversible triggering of furan-based diarylethene molecules chemically attached on gold nanoparticles surface is studied  A reversible blue shift of local surface plasmon resonance of gold nanoparticles decorated with diarylethene molecules is observed.  Deceleration of the ring closing kinetics of diarylethene molecules being covalently attached to gold nanoparticles is detected ABSTRACT The optical properties of the photochromic 1,2-bis(2-methyl-5-((4-mercaptophenyl)ethynyl)furan-3-yl)perfluorocyclopentene (YnPhT) covalently attached to gold nanoparticles (AuNP) (d=17±1 nm ) were studied in air at ambient conditions. The reversible ring-opening/closing photochromic reactions of molecules attached on AuNP surface can occur under similar light irradiation conditions as observed for free molecules in ethanolic solution. An unexpected blue shift of the local surface plasmon resonance band (LSPR) of AuNP covered by photochromic molecules was observed after UV light irradiation. A reverse red shift of LSPR was observed when the AuNP are illuminated by visible light. Moreover, increased amplitude of the LSPR was observed for AuNP covered with molecules in the closed-ring state. These observations are discussed in view of molecule -AuNP interactions. These interactions decelerate the kinetics of the ring-closing reaction of YnPhT on AuNP surfaces under UV light irradiation.

INTRODUCTION

There is a growing interest toward molecular switches that can be reversely triggered between two well-defined forms by external optical and/or electrical stimuli due to their potential use as ultracompact 3D data storage [1][2] , heavy metal sensors [3][4][5] , elements of nano-scaled molecular-based flexible devices [6][7] and molecular machines [8][START_REF]Molecular Switches[END_REF] . To be implemented in a real device, photoresponsive organic molecules have to display: long-term thermal stability, good fatigue resistance, highly sensitive response to light irradiation, non-destructive readout capability and small structural changes during switching. Among the best studied photochromic molecules i.e. stilbenes, spiropyrans, azobenzenes and diarylethenes (DAE), the DAE are closest to meet the above requirements.

Moreover, open (OF) and closed form (CF) DAE display strong variation of electric conductance [2] when contacted by metallic electrodes, making them perfect candidates for development of optically driven molecular switches, an intensely investigated field during recent years [START_REF] Kim | [END_REF][11][12] . However, further progress in design of DAE-based molecular electronics requires a detailed understanding of the photo-switching mechanism of hybrid (molecules-metallic contact) systems and the factors controlling them.

Several attempts were made to combine photochromic properties of DAE with metallic, mainly gold, flat surfaces [13][14][15][16][17][18][19] or nano electrodes (nanoparticles) [START_REF] Hania | Ultrafast Phenomena XIV: Proceedings of the 14th International Conference[END_REF][START_REF] Kudernac | [END_REF][22][23][24][25][26][27] to yield hybrid materials with photochromic properties closely resembling those of DAE molecules in solution. In consequence, two main challenges were identified: The first one is the inhibition of photochromic properties (quenching) of DAE covalently attached to metallic electrodes due to strong hybridization of molecular orbitals (MO) in close vicinity to the gold surface [13,15,[START_REF] Hania | Ultrafast Phenomena XIV: Proceedings of the 14th International Conference[END_REF]26,[28][29][30][31] . This can be overcome by using a short, insulating alkyl chain as linker to decouple the photochromic core from the surface electrons i.e. reducing molecular π-electron interaction with surface atoms [32] . However, these alkyl groups are highly resistive thus diminishing applicability of the resulting hybrid system as molecular electronics element. In some studies this was overcome by adapting the linking groups to the electrode material. This efficiently separates (decouples) the MOs of the electronic system from the electrodes thus enabling at least the ring-closing reaction [2,18,32] .

The second challenge arises from coupling the plasmon resonance of the electrode with the MO of DAE. Localized surface plasmon resonsance (LSPR) is a collective excitation of the electrons of metallic nanoparticles induced by the electric field of an optical wave. For gold nanoparticles, the LSPR is excited by visible light and might be in the same energy range as the electronic transitions implied in the MO. Therefore, since LSPR and the photochromic properties of DAE occurs in the same energy range, we anticipate some mutual influences such as changes in the switching rate [31] .

To address these two problems, specific structured functional groups have to be proposed and implemented in the DAE. Unfortunately, so far there is no clear understanding of what class of chemical structures might be suitable to bind photochromic molecules on metallic electrodes without degrading their optically induced reactions. Different linking groups were monitored for this purpose and in addition to ring-closing, the reverse ring-opening even with some enhancement of photochromic reaction on AuNP was observed in some studies. [24-25, 27, 31] In one previous study we focused on the synthesis of new sulphur-free photochromic molecules based on the bisfuryl-perfluorocyclopentene core connected to different anchoring groups via -extended wires. [33] The influence of the anchoring group on the electrical conductance through a single-molecule junction and the alignment of the MOs to the Fermi energy level of gold electrodes were systematically studied in a gold-break junction setup. [34][35] From this data it was concluded that for rather short molecules the nature of the anchoring group and side chain (i.e. -extended wires) is dominating the level alignment with respect to the Fermi-level of the electrode material. Moreover, we could also show that DAE with difurylethene-based photochromic core and suitable anchoring groups switch from the OF to the CF within the picosecond [36] or even sub-picosecond [37] timeregime. Using these findings, flexible molecular devices based on the YnPhT DAE were designed and showed reversible conductance switching (Fig. 1) [START_REF] Kim | [END_REF]38] . Apparently, YnPhT molecules sandwiched between a macroscopic non-symmetric Au-reduced graphene-oxide electrode pair preserved their optically induced reversible switching behaviour. However, in nano-scaled or even uni-molecular electronic devices the drastically limited number of photochromic molecules has to be directly contacted by the nano electrodes which results in different electronic and photophysical properties compared to the meso or even macro scale [START_REF]Gold Nanoparticles for Physics, Chemistry and Biology[END_REF] .

In the present study we use AuNP to model the surface of gold nano-electrodes and studied optical properties of YnPhT photochromic molecules covalently attached to them. Our aim is to monitor the light induced switching of an assembly of DAE on a nano scaled model of a gold electrode and to compare it with the reversible switching of free YnPhT in solution. Furthermore we want to identify the correlations between collective switching of the ensemble and the processes undergone by a single YnPhT molecule between two gold nano-electrodes in molecular break junction setup. [35] As for the UV-induced ring-closing reaction we show that the molecule degradation is attenuated on gold nanoparticles. This will provide some advice to develop different approaches that drive or facilitate the electro-optical properties of molecules and devices on their basis at ambient conditions. EXPERIMENTAL SECTION Synthesis and purification of the acetyl-protected YnPhT were performed according to ref [35] .

In all experiments conducted in the presence of AuNP the acetyl protecting group was removed prior to use by addition of a drop of ammonia to the solution of YnPhT to liberate the free SH form of YnPhT.

The irradiation of YnPhT in ethanolic solution by UV light (λ = 250-370 nm) leads to a 6electrocyclization with concomitant formation of the CF (Fig. 1). During irradiation the color of YnPhT solution gradually changes from transparent to violet. Consequently, the photoinduced cyclization reaction can be monitored by pump-probe spectroscopy by probing the corresponding CF absorption band in the visible range (discussed below). Synthesis of gold nanoparticles was conducted according to the Turkevich protocol [START_REF] Enustun | [END_REF][41][42][43] . An aqueous solution of HAuCl4 (2.5×10 -4 mol.L -1 ) was heated to the boiling point in an Erlenmeyer flask (20 mL). Then an aqueous sodium citrate solution (1 mL, 1.7×10 -2 mol.L -1 ) was added with vigorous magnetic stirring. The colour of the solution quickly changed from transparent to light-violet (2 min) and finally reached a stable red colour 5 min after citrate addition. This aqueous solution of stabilized gold nanoparticles exhibits a peak of absorbance at λmax = 520 nm (Fig. 2a) in the absorption spectra. This peak corresponds to the LSPR band. An analysis of the scanning electron microscopy (SEM) images (inset of Fig. 2a) confirms that AuNP have spherical shape with average diameter of about 17 ±1 nm. The resultant solution was stored at 4°C to avoid nanoparticle aggregation. All chemicals were purchased from Aldrich and used as received. Glass slides (10×15 mm 2 ) were cut from commercially available cover slips (SCHOTT). The flatness of the surface was controlled with atomic force microscopy (AFM) measurements and the average roughness did not exceed 3 nm peak to peak. These slides were carefully cleaned several times in pure ethanol and dried in a flow of dry nitrogen.

Finally, they were immersed in a methanol solution of (3-aminopropyl)-triethoxysilane (APTES) (1%). After 3h the slides were sonicated three times in fresh methanol to remove all physisorbed APTES. The pre-coated glass slides were subsequently immersed in an aqueous solution of the AuNP [44] . The immersing time used in the current experiment was 20 minutes. These slides covered by AuNP were finally rinsed several times with pure water (18 MΩ) and dried in a stream of dry nitrogen. SEM reveals that AuNP are randomly dispersed on the surface with coverage of about 100 AuNP per μm 2 (Inset, Fig. 2b). The colour of the glass became light pink due to the plasmon absorption of the AuNP under ambient light. The optical spectrum obtained in transmission, exhibits the LSPR at a wavelength of λ = 521 ± 1 nm (Fig. 2b). The surface coverage of AuNP was controlled by the immersion-time of glass slides in the colloidal water solution of AuNP. Immersion time was chosen to obtain a coating-density in which LSPR of neighboring gold AuNP do not interfere.

Therefore no additional light absorption above 530 nm was observed (Fig. 2b.) Functionalization of the AuNP with the YnPhT molecules was achieved by immersion of the cover slides in an ethanolic solution of deprotected YnPhT (1.2×10 -4 mol.L -1 ) for 12h. Afterwards the cover slides were cleaned with copious amounts of fresh ethanol and dried in a stream of dry nitrogen.

The switching of YnPhT was triggered by UV or visible irradiation. A Pen-Ray® lamp (UVP, USA) with λmax = 254 nm (0.75 μW•cm -2 ) was used to induce ring closing reaction while a Schott KL 1500 LCD lamp (P = 150 W, T=3300 K) was used for reverse reaction. The AFM characterizations of AuNP attachment was performed by a Bruker Multimode apparatus operating in the PeakForce® mode at ambient atmospheric conditions. UV-visible spectra were recorded using a CARY 5000 spectrometer in transmission geometry at normal incidence within the wavelength range λ = 400 -700 nm. For measuring the modulation of the absorbance spectra when the molecule is switched, the stability of the sample holder is critical. Therefore the UV or visible irradiations were carried out directly in the spectrometer compartment without moving of the sample. The UV and visible light sources were systematically placed at 2 cm distance from the samples. SEM of glass surface covered by AuNP was performed using Zeiss Ultra55. TEM of AuNP deposited from water colloidal solution on a carbon surface was performed using Zeiss Libra120.

The formation of CF on the picosecond time-scale was investigated by femtosecond transient absorption spectroscopy. For these experiments, YnPhT with concentration of c = 5×10 -5 mol.L -1 in ethanol was used. To avoid accumulation of CF molecules, the solution was pumped through a quartz flow-cell with 2 mm optical path and a buffer volume by a peristaltic pump with 2 ml/s flow rate. We irradiated the solution in the buffer volume by broad visible radiation (Schott KL 1500 LCD, P = 150 W), which caused the reverse ring-opening reaction. This approach allowed refreshing of the solution in the cell with OF molecules by inducing CF → OF transformation. As for the optical setup, a Ti:Sapphire laser (Coherent, USA) was used to produce femtosecond pulses (E = 0.5 mJ, t = 150 fs, λ= 800 nm, υ = 1 kHz). This beam was split in two: the pump beam initiated the ring closing reaction, while the probe beam tracked changes of the optical density on the femtosecond timescale. The third harmonic generation was used to generate laser pulses with following parameters E = 0.4 μJ, t = 150 fs, λ = 266 nm, υ = 250 Hz. As probe radiation, the supercontinuum (SC, λ = 540-600 nm), generated in an Al2O3 crystal by femtosecond pulses at 800 nm, was used. The SC beam was split into probe and reference beams before entering the sample. Both beams were recorded by a multichannel spectrograph (Imaging Spectrograph SP-2500i, Acton, USA). In order to determine the time delay, the approximate zero position was obtained from mixing fundamental λ=800 nm and SC in the nonlinear BBO crystal. In our data and figures the zero point position was chosen as the starting point of absorption changes. To correct SC fluctuations, the transient absorbance spectra were obtained by comparing the probe and the reference spectra for different time delays, and then, the group-velocity dispersion of SC pulse was corrected numerically at all obtained transient traces.

RESULTS AND DISCUSSIONS

Femtosecond pump-probe spectroscopy studies of ring closing reaction of YnPhT molecules in ethanol solution revealed an uptake of the optical density at λ = 540-610 nm when the delay between pump and probe pulses is increased stepwise up to 0.8 ps (Fig. 3). Above 0.8 ps, we detected only slight optical density fluctuation. No progressive spectral shifts during the first hundreds of femtoseconds after pump pulse were detected. From the normalized time profile (Fig. 3, inset) we determined the upper value of the rise-time as the characteristic of the gradual growth of optical density during the ring-closing reaction of YnPhT molecules to be equal to 420 fs. This value is smaller than that of thiophene based DAE [45][46] , revealing a faster ring-closing reaction of furanbased DAE functionalized by 4-mercaptophenyl-ethynyl side groups. From these results of the pump probe experiment we expect that furans grafted onto AuNP will also show a faster cyclization dynamics compared with thiophenes.

The glass slides covered with AuNP decorated by YnPhT molecules were characterized by UV-visible spectroscopy. When YnPhT molecules are covalently bound in OF, the optical spectrum undergoes a slight modification. i.e the LSPR changes from 521 nm to 525 nm and the intensity increases by about 6% compared to bare AuNP on glass (Fig. 4a). This 6 nm wavelength shift accompanied with a slight increase of the absorbance is typical when a molecular layer is formed on gold nanoparticles. The small change of the refractive index in the close vicinity of the nanoparticle is modeled with the Mie theory and is largely documented [47][48][49] . In our case this plasmon shift is a proof of the attachment of molecules in OF and was discussed previously [50] . The concomitant increase of the absorbance is typical for hybrid systems where molecules are grafted onto nanoparticles and do not induce any electronic effect or any charge transfer. We deduce from recent observations done with STM on Au(111) surface covered by YnPhT molecules [50] , that the rather low increase in signal intensity is in agreement with a relatively low coverage of the YnPhT on the AuNP surface.

Upon irradiation of the glass slide by UV light for 6 minutes an increase of light absorbance by 22% of the overall absorbance was measured (Fig. 4a. dashed curve). Irradiation of the sample by visible light for the same amount of time as before led to a decrease in light absorption of the glass-AuNP-YnPhT system (Fig. 4a). This behaviour is similar to the photochromic properties of the free YnPhT molecules in ethanolic solution (Fig. 1), i.e. UV light leads to ring-closing reaction of molecules (colored solution) and visible light induces reversible ring-opening reaction (solution bleaching). Therefore, the observed changes of the light absorbance in Fig. 4a can be attributed to reversible switching of YnPhT molecules covalently bound to AuNP surface, since UV/visible irradiation is known to induce no modification of the intensity of the LSPR of bare AuNP [51][52][START_REF] Pluchery | Optical characterization of supported gold nanoparticles for plasmonic biosensors[END_REF] . To demonstrate reversible switching we performed several OF→CF→OF cycles (Fig. 4b). These confirmed that the material interacts efficiently with UV as well as visible light and possesses pronounced photochromic properties. However, some experimental effects were observed and will be discussed in the following paragraphs.

The CF→OF transition under visible light irradiation (Fig. 4) leads to a red shift of LSPR and lowering of the overall light absorbance. A complete recovering of the absorption spectra during OF→CF→OF cycles was not observed (Fig. 4a). Such effect is not related to some specific properties of AuNP-YnPhT hybrid material. It represents intrinsic properties of all DAE photochromic molecules including YnPhT i.e. OF→CF transition under UV irradiation has a higher quantum yield than the reverse CF→OF under visible light irradiation [2] . <InlineShape1> Interestingly, an increase in the light absorbance upon OF → CF transition is not accompanied by a red-shift of the LSPR as it might be expected when dielectric constant is increasing according to Mie theory [START_REF]Gold Nanoparticles for Physics, Chemistry and Biology[END_REF] . Instead the λmax of LSPR is blue-shifted by 5 nm upon UV irradiation of initially attached molecules to initiate the OF → CF transition (red solid curve → blue dashed curve; Fig. 4a).

This was observed systematically for different samples each time when they were subjected to UV light. This blue-shift might have two origins. One might be a simple additive effect of the absorption spectra of bare AuNP, i.e. the LSPR at 521 nm (Fig. 4a, black curve) with the intrinsic absorption of CF molecules (max at 554 nm; Fig. 1, dashed curve). However, since CF in solution exhibits a broad absorption band (Fig. 1), the additive effect would favor an overall red shift of the LSPR as recently shown by Nishi [54]. Seemingly the observed blue shift in our experiments is not simply based on variation of the refractive index during OF→ CF switching. In agreement with theoretical calculations for other DAE-NP hybrids which are predicting an electronic interaction [55][56] , it seems more plausible that a specific interaction between AuNP and molecular-orbitals of the closed form of YnPhT is present in our system, which enhances the impact onto the optical properties of YnPhT molecules. To confirm this, we subtracted the spectrum of unmodified AuNP on glass from the ones corresponding to YnPhT modified AuNP after alternating UV-/visible-irradiation cycles (Fig. 5).

The resulting spectra describe the interaction of AuNP and YnPhT (in optical meaning) dynamically as a function of YnPhT ring-opening/-closing reaction. The spectra are characterized by a prominent absorption band centered at max = 547 nm (Fig. 5, red curve). Upon irradiation with UV to initiate OF → CF transition the overall light absorbance in the visible region increases strongly with a concomitant blue-shift of the absorption band by 15 nm to max = 532 nm (Fig. 5, blue dotted curve). This specific absorption band in the region of 540 nm was observed systematically in all curves of Fig. 5. Initially, we suspected a contamination of our OF-solution by a small amount of CF molecules during AuNP modification. However, under repetitive UV-/visible-irradiation the intensity of this band remains unchanged relative to its background. This revealed independence of this absorption band from the process of ring closing/opening of YnPhT molecules. Moreover, the width of this band is about 70 nm whereas the CF of YnPhT has a much broader (410-680 nm) intrinsic absorption band (Fig. 1). Thus, we cannot attribute this band to the one observed for CF of molecules attached to AuNP. As mentioned above, upon UV-irradiation the position of the absorption band is slightly blue shifted, whereas it is back-shifted to the red region when irradiated by visible light. Based on these findings, we hypothesize that this band results from an interaction of specific molecular orbitals of terminal 4-mercaptophenyl-ethynyl linker groups with AuNP. However, this hypothesis requires additional clarification by theoretical calculations of MOs for YnPhT linked to AuNP.

the reversible increase of absorbance during alternating irradiation with either UV or visible light clearly indicates a switching process (Fig. 5). Seemingly, the photochromic properties of the hexafluorocyclopentene core of YnPhT on the surface of AuNP are not quenched.

We attribute this to the linker groups efficiently decoupling the photochromic core from electronic states of the AuNP. These groups act as a barrier for surface electrons aiming to occupy lowest unoccupied MO during YnPhT switching. Thus, it shows that photo-excited MO are not mixed with Au surface states like in the case of thiophene-base linkers which led consequently to partial loss of photochromic properties [13,[START_REF] Kudernac | [END_REF] . At the same time our linker provides sufficient π-conjugation in electronic transport measurements, as evidenced by recent molecular-break junction experiments [35] .

To investigate the influence of the AuNP on the switching kinetics of surface bound YnPhT we compared the optical response of the AuNP-YnPhT system toward irradiation with that of YnPhT in solution. We increased the duration of UV irradiation of the glass-AuNP-YnPhT sample stepwise and measured the value of light absorbance at 554 nm after each irradiation cycle (Fig. 6a). A sample of YnPhT in ethanol solution was treated exactly the same way (Fig. 6b). Both samples were irradiated in two series with increments of 10 and 30s UV irradiation, respectively.

In experiments with the glass-bound AuNP-YnPhT system with 10 sec increments the intensity of light absorption at 554 nm is linear increasing (Fig. 6a). Using longer increments of Δt = 30s lead to non-linear and more progressive increasing of light absorbance during first two cycles followed by deceleration over remaining cycles (Fig. 6a). Repeating the experiment with unbound YnPhT molecules in solution (Fig. 6b) resulted in an initially fast absorbance increase which reached quickly saturation. The process occurs more rapidly in the experiment with 30s. increment whereas the experiment with shorter irradiation intervals of 10 sec took longer to reach saturation (Fig. 6b). Independent of the irradiation time, the absorbance increase is much faster in solution than in the AuNP-YnPhT hybrid system (Fig. 6b). Saturation is reached in solution either after 60s (30s intervals) or 150s (10s intervals) of accumulated UV irradiation whereas the AuNP-YnPhT system does not achieve saturation even after 350s of accumulated UV irradiation.

Longer UV irradiation of YnPhT solution leads to a slow decrease of light absorbance mainly by decomposition of YnPhT [START_REF] Sekkat | Photoreactive Organic Thin Films[END_REF] .

The kinetics of ring-closing reaction of YnPhT molecules chemically attached to AuNP surface is thus different from the one of free YnPhT in solution. During continuous UV irradiation of ethanolic solution all YnPhT molecules are transformed to CF much more rapidly than the one attached to AuNP surface. YnPhT molecules attached to AuNP apparently show a slower ring closing reaction. This observation is consistent with our recent UV/visible light switching experiments for YnPhT anchored to a flat gold mono crystal [START_REF] Kim | [END_REF] . These experiments revealed higher stability of DAE on a metallic surface under mechanical and temperature stresses albeit with reduced switching kinetics. This effect can be explained by modification of the HOMO-LUMO gap which is responsible for the ring-closing reaction of YnPhT on a gold surface. The effect of HOMO-LUMO gap modification was experimentally proven in break-junction measurements [35] and predicted theoretically for other DAE attached to small gold cluster [56] . Consequently this leads to different quantum yields for the OF→CF transformation of free YnPhT in solution and the ones connected to AuNP.

Unexpectedly, our experiments show a slightly different kinetic of ring-closing reaction when different irradiation increments were used. Samples irradiated with longer intervals of UV irradiation show a stronger increase of absorbance over time than those samples which were irradiated using 10 sec intervals. Whereas in the AuNP-YnPhT hybrid sample both curves merge after a total of ~300 sec, the situation in solution is different. Here samples irradiated in 30 sec intervals reach saturation faster and start decomposition while samples irradiated by shorter intervals of UV light lag behind.

We do not know yet if the solvent is involved in this process. At present this effect remains largely unclear and demands further investigations.

CONCLUSIONS

YnPhT photochromic molecules with 4-mercaptophenyl-ethynyl linker-groups display subpicosecond cyclization reaction in solution. Pump-probe experiments revealed a faster ring closing process compared to thiophene-based analogues. Grafting AuNP (17 ±1 nm) on APTES modified glass substrates allowed the functionalization of AuNP with YnPhT molecules by standard thiol-Au bond forming technique. The thus generated hybrid system was characterized by UV spectroscopy during alternating UV/vis-irradiation cycles. The interaction of YnPhT with the gold surface does not lead to complete quenching of photochromic properties; instead it induces a moderate deceleration of the ring closing kinetics. It is expected that the optical properties of created hybrid material may improve if attachment geometry of molecules on AuNP surface can be controlled [55][56] . However this requires strong theoretical calculation performed in combination of molecular dynamics, DFT and TD-DFT methods.

We explain this by the presence of the 4-mercaptophenyl-ethynyl linker-group which attaches the YnPhT to the AuNP. Apparently it decouples the MO of the photochromic core from electronic states of the Au-NP thus suppressing quenching effects. These renders YnPhT molecules good candidates for the construction of nano sized organo-metallic hybrid switches with optically controlled properties.

Figure. 6

 6 Figure.6 Evolution of absorbance change of (a) glass-NPs-YnPhT sample in air and (b) of

Figure 1 .Figure 2 .

 12 Figure 1. Temporal evolution of absorption spectra of YnPhT molecules in ethanol showing the

Figure 3 .

 3 Figure 3. Time-resolved spectra of YnPhT molecules in ethanol solution displaying optical density

Figure 4 .

 4 Figure 4. Absorption spectra of AuNP attached to glass slides. (a) Black curve (lowest)

Figure 5 .

 5 Figure 5. Difference spectra obtained by subtracting the signal of unmodified AuNP from the

ACKNOWLEDGMENTS

The work was supported by the DNIPRO program (2015-2016) established by Ministry of Education and Science of Ukraine and Ministry of foreign affairs of France; the Deutsche Forschungsgemeinschaft through SFB767; the FP7 Marie Curie ILSES project No 612620.


Janka Chlebíková
email: janka.chlebikova@port.ac.uk

Morgan Chopin
email: morgan.chopin@lip6.fr

The firefighter problem: further steps in understanding its complexity *

.

In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any b ≥ 1. Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter "cluster vertex deletion".

Introduction

The firefighter problem was introduced by Hartnell [START_REF] Hartnell | Firefighter! an application of domination[END_REF] and received considerable attention in a series of papers [START_REF] Anshelevich | Approximability of the firefighter problem[END_REF][START_REF] Cai | Firefighting on trees: (1 -1/e)-approximation, fixed parameter tractability and a subexponential algorithm[END_REF][START_REF] Costa | More fires and more fighters[END_REF][START_REF] Develin | Fire containment in grids of dimension three and higher[END_REF][START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF][START_REF] Hartnell | Firefighting on trees: how bad is the greedy algorithm?[END_REF][START_REF] Iwaikawa | Improved approximation algorithms for firefighter problem on trees[END_REF][START_REF] King | The firefighter problem for cubic graphs[END_REF][START_REF] Macgillivray | On the firefighter problem[END_REF][START_REF] Ng | A generalization of the firefighter problem on ZxZ[END_REF]. In its original version, a fire breaks out at some vertex of a given graph. At each time step, one vertex can be protected by a firefighter and then the fire spreads to all unprotected neighbours of the vertices on fire. The process ends when the fire can no longer spread. At the end all vertices that are not on fire are considered as saved. The objective is at each time step to choose a vertex which is protected by a firefighter such that a maximum number of vertices in the graph is saved at the end of the process. In this paper we consider a more general version which allows us to protect b ≥ 1 vertices at each step (the value b is called budget).

The original firefighter problem was proved to be NP-hard for bipartite graphs [START_REF] Macgillivray | On the firefighter problem[END_REF], cubic graphs [START_REF] King | The firefighter problem for cubic graphs[END_REF] and unit disk graphs [START_REF] Fomin | Making life easier for firefighters[END_REF]. Finbow et al. [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF] showed that the problem is NP-hard even on trees. More precisely, they proved the following dichotomy theorem: the problem is NP-hard even for trees of maximum degree three and it is solvable in polynomial-time for 1 graphs with maximum degree three, provided that the fire breaks out at a vertex of degree at most two. Furthermore, the problem is polynomial-time solvable for caterpillars and socalled P-trees [START_REF] Macgillivray | On the firefighter problem[END_REF]. Later, Bazgan et al. [START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] extended the previous results by showing that the general firefighter problem is NP-hard even for trees of maximum degree (b + 3) for any fixed budget b ≥ 2 and polynomial-time solvable on k-caterpillars. From the approximation point of view, the problem is e e-1 -approximable on trees ( e e-1 ≈ 1.5819) [START_REF] Cai | Firefighting on trees: (1 -1/e)-approximation, fixed parameter tractability and a subexponential algorithm[END_REF] and it is not n 1-ε -approximable on general graphs for any ε > 0 unless P = NP [START_REF] Anshelevich | Approximability of the firefighter problem[END_REF]. Moreover for trees in which each non-leaf vertex has at most four neighbours, the firefighter problem is 1.3997approximable [START_REF] Iwaikawa | Improved approximation algorithms for firefighter problem on trees[END_REF]. Very recently, a significant progress has been achieved on the approximability status of the problem for trees. Chalermsook et al. claimed in [START_REF] Chalermsook | New integrality gap results for the firefighters problem on trees[END_REF] that the integrability gap of the standard LP relaxation can be arbitrarily close to e e-1 and finally Adjiashvili et al. claimed to prove a PTAS for the firefighter problem on trees [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF]. Costa et al. [START_REF] Costa | More fires and more fighters[END_REF] extended the e e-1 -approximation algorithm on trees to the case where the fire breaks out at f > 1 vertices and b > 1 firefighters are available at each step. From a parameterized perspective, the problem is W [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF]-hard with respect to the natural parameters "number of saved vertices" and "number of burned vertices" [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF]. Furthermore, it admits an O(2 τ kτ )-size kernel where τ is the minimum vertex cover of the input graph and k the number of burned vertices [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF]. Cai et al. [START_REF] Cai | Firefighting on trees: (1 -1/e)-approximation, fixed parameter tractability and a subexponential algorithm[END_REF] presented first fixed-parameter tractable algorithms and polynomial-size kernels for trees for each of the following parameters: "number of saved vertices", "number of saved leaves", "number of burned vertices", and "number of protected vertices".

In this paper we provide a complexity dichotomy result of the problem with respect to the parameters maximum degree and pathwidth of the input graph. In Section 2 we first provide the formal definition of the problem as well as some preliminaries. In Section 3 we extend the hardness results on trees by proving that the problem is also NP-complete on trees of pathwidth three. The presented proof is also a simpler proof of the NP-completeness of the problem on trees. In Section 4 we devise a parameterized algorithm with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph. In Section 5 we show that the problem is also NP-hard on co-bipartite graphs which are very dense graphs, but fixed-parameter tractable with respect parameter "cluster vertex deletion" (cvd). This last result strengthens the previous O(2 τ kτ )-size kernel as it suppresses the dependence with k and the cvd number is smaller than the vertex cover number τ . The conclusion is given in Section 6.

Preliminaries

Graph terminology. Let G = (V, E) be an undirected graph of order n. For a subset

S ⊆ V , G[S] is the induced subgraph of G. The neighborhood of a vertex v ∈ V , denoted by N (v), is the set of all neighbors of v. For a vertex set V ⊆ V we define N V (v) = N (v) ∩ V .
We denote by N k (v) the set of vertices that are at distance at most k from v. The degree of a vertex v is denoted by deg G (v) and the maximum degree of the graph G is denoted by Δ(G).

A linear layout of G is a bijection π : V → {1, . . . , n}. For convenience, we express π by the list L = (v 1 , . . . , v n ) where π(v i ) = i. Given a linear layout L, we denote the distance between two vertices in L by d L (v i , v j ) = ji.

The cutwidth cw(G) of G is the minimum k ∈ N such that the vertices of G can be arranged in a linear layout L = (v 1 , . . . , v n ) in such a way that, for every i ∈ {1, . . . , n -1}, there are at most k edges between {v 1 , . . . , v i } and {v i+1 , . . . , v n }.

Vertex Cover

Cutwidth (Th. 10)

Pathwidth

(Th. 3)

Cluster vertex deletion (Th. 12)

Treewidth [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF][START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] Cliquewidth Maximum degree [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF][START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] Figure 1: The parameterized complexity of the Firefighter problem with respect to some structural graph parameters. An arc from a parameter k 2 to a parameter k 1 means that there exists some function h such that k 1 ≤ h(k 2 ). For any fixed budget, a dotted rectangle means fixed-parameter tractability for this parameter and a thick rectangle means NP-hardness even for constant values of this parameter.

The bandwidth bw(G) of G is the minimum k ∈ N such that the vertices of G can be arranged in a linear layout L = (v 1 , . . . , v n ) so that |d L (v i , v j )| ≤ k for every edge v i v j of G.
A path decomposition P of G is a pair (P, H) where P is a path with node set X and H = {H x : x ∈ X} is a family of subsets of V such that the following conditions are met

1. x∈X H x = V.
2. For each uv ∈ E there is an x ∈ X with u, v ∈ H x .

3. For each v ∈ V , the set of nodes {x : x ∈ X and v ∈ H x } induces a subpath of P .

The width of a path decomposition P is max x∈X |H x |-1. The pathwidth pw(G) of a graph G is the minimum width over all possible path decompositions of G.

We may skip the argument of pw(G), cw(G), bw(G) and Δ(G) if the graph G is clear from the context.

A star is a tree consisting of one vertex, called the center of the star, adjacent to all the other vertices.

Problem definition. We start with an informal explanation of the propagation process for the firefighter problem. Let G = (V, E) be a graph of order n with a vertex s ∈ V , let b ∈ N be a budget. At step t = 0, a fire breaks out at vertex s and s starts burning. At any subsequent step t > 0 the following two phases are performed in sequence:

1. Protection phase : The firefighter protects at most b vertices not yet on fire.

2. Spreading phase : Every unprotected vertex which is adjacent to a burned vertex starts burning.

Burned and protected vertices remain burned and protected until the propagation process stops, respectively. The propagation process stops when in a next step no new vertex can be burned. We call a vertex saved if it is either protected or if all paths from any burned vertex to it contain at least one protected vertex. Notice that, until the propagation process stops, there is at least one new burned vertex at each step. This leads to the following obvious lemma.

Lemma 1

The number of steps before the propagation process stops is less or equal to the total number of burned vertices.

A protection strategy (or simply strategy) Φ indicates which vertices to protect at each step until the propagation process stops. Since there can be at most n burned vertices, it follows from Lemma 1 that the propagation unfolds in at most n steps. We are now in position to give the formal definition of the investigated problem.

The Firefighter problem: Lemma 2 Among the strategies that maximize the number of saved vertices (or equivalently minimize the number of burned vertices) for a tree, there exists one that protects vertices adjacent to a burned vertex at each time step.

Input: A graph G = (V, E), a vertex s ∈ V ,
Throughout the paper, we assume all graphs to be connected since otherwise we can simply consider the component where the initial burned vertex s belongs to.

Firefighting on path-like graphs

Finbow et al. [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF] showed that the problem is NP-complete even on trees of degree at most three. However, the tree constructed in the proof has an unbounded pathwidth. In this section we show that the Firefighter problem is NP-complete even on trees of pathwidth three. For that purpose we use the following problem.

The Cubic Monotone 1-In-3-Sat problem: Input: A CNF formula with no negative literals in which every clause contains exactly three variables and every variable appears in exactly three clauses. Question: Is there a 1-perfect satisfying assigment (a truth assignment such that each clause has exactly one true literal) for the formula?

The NP-completeness of the above problem is due to its equivalence with the NP-complete Exact Cover by 3-Sets problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

Theorem 3 For any budget b ≥ 1, the Firefighter problem is NP-complete even on trees of pathwidth three.

Proof : Clearly, Firefighter belongs to NP. Now we provide a polynomial-time reduction from Cubic Monotone 1-In-3-Sat. We start with the case where b = 1 and later explain how to extend the proof for larger values of b.

In the proof, a guard-vertex is a star with k leaves where the center is adjacent to a vertex of a graph. It is clear that if at most k vertices can be burned, then the guard-vertex has to be saved.

Let φ be a formula of Cubic Monotone 1-In-3-Sat with n variables {x 1 , . . . , x n } and m initial clauses {c 1 , . . . , c m }. Notice that we have n = m since there is a total of 3n = 3m literals in φ. First, we extend φ into a new formula φ by adding m new clauses as follows.

For each clause c j we add the clause cj by taking negation of each variable of c j . A perfect satisfying assignment for φ is then a truth assignment such that each clause c j has exactly one true literal (1-perfect) and each clause cj has exactly two true literals (2-perfect). Clearly, we have that φ has a 1-perfect satisfying assignment if and only if φ has a perfect one. To see this, observe that a clause c j has exactly one true literal if and only if cj has two true literals.

Now we construct an instance I = (T, s, 1, k) of Firefighter from φ as follows (see Figure 2). We start with the construction of the tree T , the value of k will be specified later.

• Start with a vertex set {s = u 1 , u 2 , . . . , u p } and edges of {su 2 , u 2 u 3 , . . . , u p-1 u p } where p = 2n -1 and add two degree-one vertices v x i and v xi adjacent to u 2i-1 for every i ∈ {1, . . . , n}.

Then for each i ∈ {1, . . . , n} in two steps:

• Add a guard-vertex g i (resp. ḡi ) adjacent to v x i (resp. v xi ). • At each vertex v x i (resp. v xi ) root a path of length 2 • (n -i) at v x i (resp. v xi )
in which the endpoint is adjacent to three degree-one vertices (called literal-vertices) denoted by x i 1 , x i 2 , and x i 3 (resp. xi 1 , xi 2 , and xi 3 ). Each literal-vertex corresponds to an occurence of the variable x i in an initial clause of φ. Analogously, the literalvertices xi 1 , xi 2 , and xi 3 represent the negative literal xi that appears in the new clauses of φ .

Notice that each literal-vertex is at distance exactly p + 1 from s.

• For each variable x i (resp. xi ), i ∈ {1, . . . , n}, there are exactly three clauses containing

x i (resp. xi ). Let c j (resp. cj ), j ∈ {1, . . . , m}, be the first one of them. Then root a path

Q x i j (resp. Q xi j ) of length 3 • (j -1) at x i 1 (resp. xi 1 )
, and add a guard-vertex g x i j adjacent to the endpoint of Q x i j . To the endpoint of Q xi j (i) add a degree-one vertex d xi (a dummy-vertex) and (ii) root a path D xi j of length 3 where the last vertex of the path is a guard vertex g xi j . Repeat the same for the two other clauses with x i (resp. xi ) and

x i 2 , x i 3 (resp. xi 2 , xi 3 ).
To finish the construction, set k = p + n 2 (11n + 7). In what follows, we use Lemma 2 and thus we only consider strategies that protect a vertex adjacent to a burned vertex at each time step. Recall that the budget is set to one in the instance I . Now we show that there is a perfect satisfying assignment for φ if and only if there exists a strategy for I such that at most k vertices in T are burned.

"⇒" : Suppose that there is a perfect satisfying assignment τ for φ . We define the following strategy Φ τ from τ . At each step t from 1 to p + 1, if t is odd then protect

v x t/2 if x t/2 is true, otherwise protect v x t/2 . If t is even, then protect the guard-vertex g t/2 v x1 v x1 g 1 ḡ1 s = u 1 u 2 u 11 u 10 v x6 v x6 g 6 ḡ6 Figure 2: An example of part of a tree constructed from the formula φ = (x 1 ∨ x 3 ∨ x 6 ) ∧ (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 3 ∨ x 4 ∨ x 5 ) ∧ (x 2 ∨ x 4 ∨ x 5 ) ∧ (x 1 ∨ x 4 ∨ x 6 ) ∧ (x 2 ∨ x 6 ∨ x 5
). Guard vertices are represented by a dot within a circle.

if v x t/2 has been protected, otherwise protect ḡ t/2 . At the end of time step p+1, the number of burned vertices is exactly p + n i=1 (3 + 2(ni) + 1) = p + 3n + n 2 . Moreover, the literalvertices that are burned in T correspond to the true literals in φ . Thus, by construction and since τ satisfies φ , the vertices adjacent to a burning vertex are exactly one guardvertex g xa 1 , two dummy vertices d xb , d xc and 3n -1 other vertices where x a ∨ x b ∨ x c is the first clause, a, b, c ∈ {1, . . . , n}. At step p + 2, we must protect the guard vertex g xa 1 . During the steps p + 3 and p + 4, the strategy must protect one vertex lying on the path D xb 1 and D xc 1 , respectively. Thus 3(3n -3) + 5 = 9n -4 more vertices are burned at the end of step p + 4. More generally, from time step p + 3(j -1) + 2 to p + 3(j -1) + 4, for some j ∈ {1, . . . , m}, the strategy Φ τ must protect a guard-vertex g xa j and one vertex of each path D xb j and D xc j , where x a , x b , x c appear in the clause c j , a, b, c ∈ {1, . . . , n}. Thus 9(n -(j -1)) -4 vertices get burned. It follows that the number of burned vertices from step p

+ 2 to p + 3m + 1 is m j=1 [9(n -(j -1)) -4] = 9 2 m(m + 1) -4m.
Putting all together, we arrive at a total of p + 3n + n 2 + 9 2 m(m + 1) -4m = p + n 2 (11n + 7) = k burned vertices. "⇐": Conversely, assume that there is no perfect satisfying assignment for φ . Observe first that any strategy Φ for I protects either the pair v x i and ḡi or the pair v xi and g i for each i ∈ {1, . . . , n}. As a contradiction, suppose that there exists i ∈ {1, . . . , n} such that Φ does not protect v x i and v xi . Then in some time step both v x i and v xi get burned. Hence, it is not possible to protect both g i and ḡi , and at least one will burn implying that more than k vertices would burn, a contradiction. Furthermore, v x i and v xi cannot be both protected, otherwise we would have protected a vertex not adjacent to a burned vertex at some step. Now consider the situation at the end of step p+1. By the previous observation, the literal-vertices that are burned in T can be interpreted as being the literals in φ set to true. As previously, the number of burned vertices so far is exactly p + n i=1 (3 + 2(ni) + 1) = p + 3n + n 2 . Let n g and n d be the number of guard-vertices and dummy-vertices adjacent to a burned vertex, respectively. As it follows from the previous construction, we know that n g = 3n d with 0 ≤ n g ≤ 3 and 0 ≤ n d ≤ 3. We have the following possible cases:

(1) n g > 1. In this case, a guard-vertex gets burned, and hence more than k vertices would burn.

( ). Thus 3 dummy-vertices are burned. Notice that at step p + 5, we end up with a similar situation as in step p + 2. Now consider an assignment for φ . Since φ is not perfect satisfiable, φ is not 1-perfect satisfiable as well. There are two possibilities:

• There exists a clause c j in φ with more than one true literal. Thus, we end up with case (1), and there is no strategy for I such that at most k vertices are burned.

• There is a clause c j in φ with only false literals. This corresponds to case (3), and the number of burned vertices would be at least 1 + p + n 2 (11n + 7) (at least one extra dummy-vertex gets burned) giving us a total of at least k + 1 burned vertices. Hence there is no strategy for I where at most k vertices are burned.

It remains to prove that the pathwidth of T is at most three. To see this, observe that any subtree rooted at v x i or v xi has pathwidth two. Let P x i and P xi be the paths of the path-decompositions of these subtrees, respectively. We construct the path-decomposition for T as follows. For every i ∈ {1, . . . , n -1}, define the node B i = {u 2i-1 , u 2i , u 2i+1 }. Extend all nodes of the paths P x i and P xi to P x i and P xi by adding the vertex u 2i-1 inside it. Finally, connect the paths P x 1 , P x1 and the node B 1 to form a path and continue in this way with

P x 2 , P x2 , B 2 , P x 3 , P x3 , B 3 , . . . , B n-1 , P xn , P xn .
Finally, we consider the case where b > 1. We start from the above reduction and alter the tree T as follows. Let w 1 be the vertex s (corresponding also to u 1 ). Add a path {w 1 w 2 , w 2 w 3 , . . . , w 5n w 5n+1 } to T together with b -1 guard-vertices added to each w i . First, one can easily check that the pathwidth remains unchanged, since the added component has pathwidth two and is only connected to the root s. Second, it can be seen that at each time step, only one firefighter can be placed "freely", as the other b -1 firefighters must protect b -1 guard-vertices. It follows that we end up with a similar proof as above. This completes the proof.

As a side result, we also obtain the following.

Proposition 4 For any budget b ≥ 1, the Firefighter problem is NP-complete even on line graphs.

Proof : We use a polynomial-time reduction from the Firefighter problem on trees. Consider an instance I = (T, s, b, k) of Firefighter that consists of a tree T = (V, E) and the root s. Let v i,j be the j th vertex at level i of the tree T . We construct an instance I = (G, s , b, k) of Firefighter in which a line graph G is defined as follows: add a vertex v and adjacent it to the root s, let G be the line graph of such tree. Denote by e i,j the unique edge that connects v i,j to its parent and by s the edge vs, the edges e i,j and s correspond to the vertices in G.

As follows from the construction, there is a one-to-one correspondence between the vertices 'v i,j ' in T and 'e i,j ' in G. Therefore, given a strategy Φ for I we can define a corresponding strategy Φ' for I , and vice versa. Clearly, a vertex e i,j in G is protected (resp. saved, resp. burned) by Φ if and only if the corresponding vertex v i,j in T is protected (resp. saved, resp. burned) by Φ'. Hence, there exists a strategy in I such that at most k vertices are burned if and only if there exists a strategy in I such that at most k vertices are burned. The rest follows from Theorem 3.

Path-like graphs of bounded degree

As previously shown, for any fixed budget b ≥ 1, the Firefighter problem is NP-complete on trees of bounded degree b+3 [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF][START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] and on trees of bounded pathwidth three (Theorem 3). It is thus natural to explore the complexity of the problem when both the maximum degree and the pathwidth of the input graph are bounded.

First we introduce some definitions. Let L = (v 1 , . . . , v n ) be a linear layout of a graph G such that for every i ∈ {1, . . . , n -1}, there are at most k + 1 edges between {v 1 , . . . , v i } and {v i+1 , . . . , v n }. A vertex-interval I of L is any ordered vertex subset (v i , . . . , v i+k ) of L for some i, k > 0. Denote by (I) (resp. r(I)) the leftmost (resp. rightmost) vertex in I.

Lemma 5 Let G = (V, E) be a graph of cutwidth cw and F ⊆ V be a set of initially burned vertices. Then there exists a protection strategy such that the statements ( 1) and ( 2

) hold after 2 • cw •|F | steps of propagation:

(1) The number of burned vertices is at most

(2 • cw •|F |) 2•cw •|F | .
(2) There is a set of disjoint vertex-intervals I such that for every I ∈ I, the vertices (I), r(I) are burned and every vertex v outside I which is adjacent to a vertex in I is protected. (2) Initially suppose that F contains only one vertex s ∈ F . Denote by F the set of burned vertices after 2 • cw steps of propagation without protecting any vertices. Define the vertex-interval I s such that l(I s ) and r(I s ) are the leftmost and the rightmost burned vertices from F , respectively. By the definition the number of edges with one vertex in I s and the other one in V \ I s is less or equal to 2 • cw. Thus, we can define the strategy that consists of protecting one vertex v ∈ V \ I s adjacent to a vertex in I s in each step t = 1, . . . , 2 • cw. Observe that those vertices are not burned before they are protected, otherwise they would have been included in I s .

Proof

If |F | > 1, we repeat the previous ideas in the sequence of the steps from t = 1, . . . , 2 • cw •|F |. In each step t we consider one by one all vertices which started to burn in step t -1 of the propagation and if it is necessary to make a modification of the vertex-intervals to ensure that all of them are disjoint: if any two vertex-intervals intersect each other, we replace them by a vertex-interval corresponding to the union of these two vertex-internals which obviously has the required properties. Theorem 6 Let G = (V, E) be a graph of cutwidth cw and F ⊆ V be a set of initially burned vertices. Then there exists a protection strategy such that the total number of burned vertices is bounded by q(cw, F ), where

q(cw, F ) = ((2 cw) cw • |F |) ↑↑ 2 cw if cw > 0, |F | otherwise.
Proof : We will prove the statement by induction on the cutwidth. The theorem is obviously true when the cutwidth is 0, since the graph does not contain any edge. Suppose now that the statement is true for any graph of cutwidth at most c, c ≥ 0. We show that it also holds for graphs of cutwidth (c + 1). Let H = (V, E) be a graph of cutwidth (c + 1) and F ⊆ V be a set of burned vertices. We apply the strategy defined in Lemma 5 for the initial 2 • (c + 1) • |F | steps of propagation. After the application of this strategy, the number of burned vertices so far is at most

|F | = (2 • (c + 1) • |F |) 2•(c+1)•|F | . Furthermore, every vertex v ∈ I∈I I (defined in Lemma 5
) is either protected or saved. Hence we only need to protect the vertices in the graph H induced by the vertices I∈I I. Observe that we can safely remove every edge uv from H for which u and v are burned. Indeed, such a burned edge cannot have any influence during the subsequent steps of propagation. As it follows from the definition of a vertexinterval, either there is a path from (I) to r(I) or the vertex-interval is the union of several overlapping vertex-intervals. In both cases after removing all the burned edges from H , the cutwidth of H decreases by 1. Hence we can apply the induction step on H , which has cutwidth c, together with the set F of the burned vertices. To summarise, we can define the valid strategy for H as follows: First apply the strategy defined in Lemma 5 for the initial 2 • (c + 1) • |F | steps on H and then apply the strategy given by induction from this theorem for the subgraph H of H. The total number of burned vertices in H using this new strategy is at most

q(c, F ) = (2c) c • |F | ↑↑ 2 c = 2 c • c c • (2 • (c + 1) • |F |) 2•(c+1)•|F | ↑↑ 2 c ≤ 2 c • (c + 1) c • (2 • (c + 1) • |F |) 2 c+1 •(c+1) c+1 •|F | ↑↑ 2 c ≤ (2 c+1 • (c + 1) c+1 • |F |) 2 c+1 •(c+1) c+1 •|F | ↑↑ 2 c ≤ 2 c+1 • (c + 1) c+1 • |F | ↑↑ 2 c+1 = (2 • (c + 1)) c+1 • |F | ↑↑ 2 c+1 = q(c + 1, F )
This concludes the proof.

Remark 7

Notice that Theorem 6 is still valid even if the number of firefighters available at each step is not the same (for example if there are b 1 firefighters at time step one, b 2 firefighters during the second time step, etc.).

Using the fact that cw(G) ≤ pw(G) • Δ(G) [START_REF] Chung | Graphs with small bandwidth and cutwidth[END_REF] for every graph G, we can easily deduce the following corollary.

Corollary 8 Let G = (V, E) be a graph of pathwidth pw and maximum degree Δ. Let F ⊆ V be a set of initially burned vertices. There exists a protection strategy such that the total number of burned vertices is bounded by q(pw, Δ, F ), where

q(pw, Δ, F ) = (2 pw •Δ) pw •Δ • |F | ↑↑ 2 pw •Δ if pw •Δ > 0 |F | otherwise
We are now in position to give the main result of this section.

Theorem 9

The Firefighter problem is fixed-parameter tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph.

Proof : Let I = (G, s, b, k) be an instance of Firefighter where G has maximum degree Δ and pathwidth pw. First we claim that the problem can be solved by a f (k, Δ) • n O(1) -time algorithm denoted by B further. To see this observe that whenever b ≥ Δ then one can protect all the vertices in N (s) at step one. If b < Δ we simply apply the

f (k, b) • n O(1)
-time procedure from [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF], so the claim follows. Now consider the following algorithm denoted by A. For each value k = 1, . . . , k, execute B on I = (G, s, b, k ): If B returns "yes" then A halts and returns "yes". If B has returned the answer "no" for all k = 1, . . . , k then A returns "no".

Using Corollary 8 we know that whenever k ≥ q(pw, Δ, {s}) = f (pw, Δ) the algorithm B necessarily returns "yes" and A stops. It follows that B is called at most f (pw, Δ) times. The overall running time is then bounded by (1) for some function f . This completes the proof.

O(f (pw, Δ) • f (k, Δ) • n O(1) ) = O(f (pw, Δ) • f (f (pw, Δ), Δ) • n O(1) ) = f (pw, Δ) • n O
Since for any graph G, we have that pw(G) ≤ cw(G) and Δ(G) ≤ 2 • cw(G) [START_REF] Korach | Tree-width, path-width, and cutwidth[END_REF] and cw(G) ≤ bw(G)(bw(G)+1) 2 [START_REF] Bodlaender | Classes of graphs with bounded tree-width[END_REF], we easily deduce the following theorem.

Theorem 10

The Firefighter problem is fixed-parameter tractable with respect to the parameter "cutwidth" and to the parameter "bandwidth".

Firefighting on dense graphs

As trees are rather sparse graphs, it seems natural to ask for the tractability of the problem when the graphs are essentially made up of cliques. In the following we show that even if a graph can be partitioned into two cliques (also known as a co-bipartite graph), the problem turns out to be NP-complete. Notice that the problem is trivial for cliques.

Theorem 11

The Firefighter problem is NP-complete and W [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF]-hard for the parameter k even on co-bipartite graphs.

Proof : We construct a polynomial-time reduction from the Clique problem on regular graphs which has been proved to be W [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF]-hard [6, Th. 2.1]. This proof is based on the one presented in [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF]. We use a different construction, but the proof of correctness remains essentially the same. Let (G = (V, E), k) be an instance of Clique where G is a Δ-regular graph of size n. We construct the instance (G , s, b, k ) of Firefighter from (G, k) as follows. We start with the construction of G .

• Add a new vertex s adjacent to all vertices of G.

• Set b = max{n -k, kΔ -k 2 } and k = k + 1. • Create two cliques C 1 and C 2 of b -(n -k) + k and b -(kΔ -k 2 )
+ k vertices, respectively. We later refer to these cliques as guard-cliques.

• Make s adjacent to any b -(n -k) vertices of C 1 . • Choose a subset S of b -(kΔ -k
2 ) vertices of C 2 and make every vertex of V adjacent to every vertex in S.

• Remove every edge uv ∈ E and add an edge-vertex e uv adjacent to u and v. We denote by F the set of all edge-vertices.

• Finally, add edges to make V and

F ∪ C 1 ∪ C 2 cliques.
Observe that the graph G can be partitioned into two cliques {s} ∪ V and

F ∪ C 1 ∪ C 2 .
It is clear that if at most k vertices can be burned in G then some vertices of both guard-cliques must be saved. As a consequence, at step one, there are only nk firefighters that can be placed freely because of the guard-clique C 1 .

We claim that (G, k) is a yes-instance of Clique if and only if (G , s, k , b) is a yes-instance of Firefighter.

"⇒": Suppose that we have a clique C ⊆ V of size k and consider the following strategy. At step one, the strategy uses the n-k remaining firefighters to protect all the original vertices V in G except those in the clique C. At step two, all k vertices of C are burned. Since those vertices are adjacent to b -(kΔ -k 2 ) vertices of the guard-clique C 2 , it remains exactly kΔ -k 2 possible vertices to protect. Observe that there are exactly kΔ -k 2 edge-vertices adjacent to the vertices in the clique C. Hence, there is enough firefighters to protect all of them and then no more than k + 1 = k vertices are burned at the end of the process.

"⇐": Conversely, suppose that there is no clique of size k in G. At step one, any valid strategy has to place the nk remaining firefighters on vertices that are not edge-vertices; otherwise at least k + 2 > k vertices will burn. At step two, since there is no clique of size k, there will be at least kΔ -k 2 + 1 edge-vertices adjacent to the k burned vertices. For the same reason as before, there remains kΔ-k 2 firefighters which is not enough to protect these edge-vertices. Therefore, given any valid strategy there will be at least k + 2 > k burned vertices.

We note that if the budget b is fixed, then one can solve the problem in polynomial time on co-bipartite graphs. To see this, observe that there are at most 3 propagation steps in such a graph. Hence the total number of protected vertices is bounded by a constant, which implies that the problem is polynomial-time solvable [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF].

As a final result we show that the Firefighter problem is fixed-parameter tractable with respect to the parameter cluster vertex deletion number, that is the minimum number of vertices that have to be deleted to obtain a disjoint union of complete graphs.

Recall that in Theorem 3 we prove NP-completeness of the Firefighter problem on trees on pathwidth three. Whenever a problem is NP-hard on graphs of bounded treewidth or pathwidth, it is a common approach to ask for the parameterized complexity of the problem with respect to the more general parameter as vertex cover. However, the class of graphs of a small vertex cover is rather limited and therefore it is natural to look for the parameters that generalise it. Among them the cluster vertex deletion number appears to be a suitable intermediate parameterisation between vertex cover and cliquewidth [START_REF] Doucha | Cluster vertex deletion: A parameterization between vertex cover and clique-width[END_REF].

Theorem 12

The Firefighter problem is fixed-parameter tractable with respect to the parameter "cluster vertex deletion".

Proof : Let (G = (V, E), s, b, k) be an instance of the Firefighter problem with |V | = n and let be the cluster vertex deletion number of G. Let L be a minimum cluster vertex deletion set in G that can be found in time O(2 • 3 log + n 3 ) as it follows from [START_REF] Hüffner | Fixed-parameter algorithms for cluster vertex deletion[END_REF].

It is easy to observe that in every three steps at least one new vertex from L gets burned. Hence all non-protected vertices in G are necessarily burned after 3 steps. Since the number of propagation steps can be at most 3 , at most 3 b vertices can be protected in G.

Let Obviously, case (a) is independent from the strategy used for the vertices in the clique C. In case (b), the non-protected vertices in C can only be saved if all neighbours of the burned vertices from L are protected in C. This follows from an easy observation: if a vertex v ∈ L with a non-protected neighbour in C starts burning, then no strategy can save non-protected vertices in C from burning, all such vertices get burned in the next step. Therefore the only way to save non-protected vertices in C is to protect all neighbours of v in C. Due to the fact that at most 3 b vertices can be protected, if v has more than 3 b neighbours in C, only protected vertices in C can be saved. Therefore if v has more than 3 b neighbours in C, the exact number of neighbours in C doesn't make any difference for any strategy, because all non-protected vertices in C will get burned. Based on this observation we define an equivalence relation on the set [L ].

Fix a set L = {v 1 , . . . , v q } ⊆ L, q ≥ 1 and define an equivalence relation ν on In the following we show that if there is a strategy with at most k burned vertices then we can find it in time which exponentially depends only on and b. We discuss different options which 3 b vertices should be protected in a way that covers all possible strategies that could potentially lead to burning at most k vertices. The rest follows from a simple linear check whether there exists a valid protection strategy which protect these vertices, see e.g. [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF] and whether at most k vertices get burned.

[L ]: C 1 , C 2 ∈ [L ] are equivalent if and only if for each vertex v i ∈ L , 1 ≤ i ≤ q one of the options (i)-(ii) holds: (i) each of the neighbour sets N C 1 (v i ), N C 2 (v i ) has more than 3 b vertices or, (ii) |N C 1 (v i )| = |N C 2 (v i )| ≤ 3 b and for each 1 ≤ j ≤ q (i = j) with |N C 1 (v j )| ≤ 3 b (hence also |N C 2 (v j )| ≤ 3 b) there is the same amount of vertices in the intersection of the neighbourhoods |N C 1 (v i ) ∩ N C 1 (v j )| = |N C 2 (v i ) ∩ N C 2 (v j )|.
Suppose that a set L 1 ⊆ L of vertices of size 1 , 1 ≤ 1 ≤ , is protected. Then Now suppose that we can protect 2 ≤ 2 vertices inside the equivalence class [L ν ] for a fixed L ⊆ L and a fixed neighbour set of L in the cliques. As it was already discussed above, for all strategies maximising the number of saved vertices in the equivalence class [L ν ] it is enough to focus on (at most) 3 b chosen cliques from seq([L ν ]), hence the number of cliques we need to consider depends only on and b. Now a brute-force algorithm can generate all options how these 2 vertices can protect the whole neighbour sets of the vertices from L s in at most 3 b cliques from seq([L ν ]), taking into account also their order. If there is not enough vertices to protect a whole neighbour set, then it makes no difference which vertices are protected. Such an algorithm runs in exponential time in b, , but not n. Hence the problem is fixed-parameter tractable with respect to the parameter "cluster vertex deletion".

Conclusion

The main result of this paper is that the Firefighter problem is NP-complete even on trees of pathwidth three but fixed-parameter tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph. The combination of these two results with the NP-completeness of the problem on trees of bounded degree [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF] indicates that the complexity of the problem depends heavily on the degree and the pathwidth of the graph. We left as an open question whether the problem is polynomial-time solvable on graphs of pathwidth two.

  and positive integers b and k. Question: Is there a strategy for an instance (G, s, b, k) with respect to budget b such that at most k vertices are burned if a fire breaks out at s? When dealing with trees, we use the following observation which is a straightforward adaptation of the one by MacGillivray and Wang for the case b > 1 [23, Section 4.1].

: ( 1 )

 1 Notice that after 2 • cw •|F | steps of propagation there are at most (|F | • Δ(G)) 2•cw •|F | burned vertices regardless of any strategy. Since we have Δ(G) ≤ 2 • cw(G) [22], the result follows.

After 2 •

 2 cw •|F | steps of propagation we can define the set I of at most |F | disjoint vertex-intervals such that the left and rightmost vertices of each interval are burned and due to the properties of the graph, there are at most 2 • cw •|F | vertices in V \ I which are adjacent to a vertex in an interval I ∈ I which can be protected in 2 • cw •|F | steps. Now we show the key combinatorial characterization of the number of burned vertices in a graph of bounded cutwidth. To make the formulas easier to read, we use the Knuth's tetration operator ↑↑ defined as x ↑↑ n = x x . . . x n times .

  C be a set of disjoint cliques (of various sizes) in the graph G[V \ L]. Define an equivalence relation on C: C 1 , C 2 ∈ C are equivalent if and only if C 1 , C 2 have the same set L of neighbours in L. The cliques C 1 , C 2 are called L -dependent. For any L ⊆ L let [L ] be a set of all L -dependent cliques. Obviously, there are at most 2 equivalence classes that define a partition of C. The non-protected vertices in a clique C ∈ [L ], for L ⊆ L, can be saved: (a) either by protecting some vertices outside the clique C or (b) by protecting some vertices in C.

  The equivalence relation ν defines a partition on the set [L ], let [L ν ] be an equivalence class of the set [L ]. Each equivalence class [L ν ] can contain any number of ν-equivalent cliques of various sizes. Due to the restriction 3 b on size of the neighbour sets, the number of equivalence classes [L ν ] of the set [L ] exponentially depends on and b only. Any protection strategy can only protect 3 b vertices, therefore any strategy can protect vertices in at most 3 b cliques in each [L ν ] class. In the following we show that in each class [L ν ] it is enough to focus only on the clique from seq([L ν ]), where seq([L ν ]) are at most 3 b largest cliques in [L ν ] ordered in size (starting from the largest). Fix an equivalence class [L ν ] of [L ]. In the following we discuss a strategy for [L ν ] that saves the maximum number of vertices in [L ν ] supposing a given amount of vertices in the set [L ν ] can be protected. If we fix a vertex v ∈ L and a clique C ∈ [L ν ] such that |N C (v)| ≤ 3lb, then each clique from [L ν ] contains exactly |N C (v)| neighbours of v due to the definition of the ν-equivalence. This enables us to define the set L s ⊆ L :L s = {v | v ∈ L and |N C (v)| ≤ 3lb for a clique C ∈ [L ν ]}.If a vertex u ∈ L \ L s starts burning then only the protected vertices in [L ν ] can be saved from burning. Therefore if we have to select at most 3 b cliques from [L ν ] without loss of generality we can restrict to the set seq([L ν ]) of cliques. If no vertex in L \ L s gets burned, then protecting suitable neighbour sets of v ∈ L s in a clique C ∈ [L ν ] can save some vertices in C. As | ∪ u∈L s N C (u)| has the same value for all cliques in [L ν ], if we want to save the most vertices in the class [L ν ], the strategy must focus to protect the neighbour sets of L s in the largest cliques from [L ν ]. Due to the assumption on the number of selected cliques we can again only focus on the cliques from seq([L ν ]). To summarise, the graph G has at most 2 equivalence classes [L ] (one for each subset L of L), and each set [L ] can be further partitioned to equivalence classes [L ν ] depending on the number of neighbours of the vertices L in the cliques. Hence, the graph G consists of a minimum cluster deletion set L of size and an exponential number (exponential on and b only) of equivalence classes [L ν ] for any subset L of L. Therefore all cliques from G[V \L] can be partitioned into F ( , b) equivalence classes, where the value of F ( , b) depends exponentially only on and b.

2 = 3

 23 b-1 vertices can be protected in the graph G[V \ L]. Due to the previous discussion, those 2 protected vertices can be split among the F ( , b) equivalence classes in F (l,b)+ 2 -1 2 different way. Hence the number of different cases exponentially depends on and b only.

  ) n g = 1. Let g xa 1 be that guard-vertex and let d xb , d xc be the n d = 3n g = 2 dummyvertices where x a , x b , x c are variables of the first clause. At time step p + 2, we must protect g xa 1 . Furthermore, during the step p + 3 (resp. p + 4), any strategy must protect a vertex lying on the path D xb 1 (resp. D xc 1 ). Indeed, if a strategy does otherwise, then at least one guard-vertex g xb 1 or g xc 1 gets burned. Thus 2 dummy-vertices are burned.

(3) n g = 0. Hence we have exactly n d = 3n g = 3 dummy-vertices d xa , d xb , d xc adjacent to burned vertices. Using a similar argument as before, we know that during the step p + 2 (resp. p + 3, p + 4), a strategy must protect a vertex lying on the path D xa 1 (resp. D xb 1 , D xc 1

were presented at IPEC 2014 [9]. † A major part of this work was done during a three-month visit of the University of Portsmouth supported by the ERASMUS program.