Germano Montemezzani
email: germano.montemezzani@metz.supelec.fr

Mohamed Gorram

Nicolas Fressengeas

Flurin Juvalta

Mojca Jazbinsek

Peter G Ünter

Light deflection and modulation through dynamic evolution of photoinduced waveguides

Keywords:

Light induced waveguides produced by lateral illumination of a photorefractive crystal show a complex dynamic evolution upon removal of the sustaining applied electric field. Using this effect, deflection and modulation of the guided light is realized by taking advantage of the screening and counter-screening of the space charge distribution. The spot separation upon deflection can exceed 10 times the original waveguide width. Numerical simulations of the refractive index evolution and beam propagation show a good agreement with the observations.

Introduction

Waveguides can be induced dynamically in a photoconductive electro-optic material by lateral illumination of the sample surface with a properly shaped control illumination in association with an applied electric field [START_REF] Ph | Fast, reconfigurable light-induced waveguides[END_REF][START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF], or, in alternative, by taking advantage of the photogalvanic response of the sample [START_REF] Zhang | Photo-written waveguides in iron-doped lithium niobate crystal employing binary optical masks[END_REF]. In the former case, the charge redistribution induced by the control illumination leads to the screening of the applied field, which can result in a locally increased refractive index in the illuminated region. The physical mechanism is similar to the one at work for waveguide formation by longitudinally propagating photorefractive bright spatial soliton beams [START_REF] Shih | Circular waveguides induced by two-dimensional bright steady-state photorefractive spatial screening solitons[END_REF]. Past investigations have shown that the steady-state shape of the waveguide reflects essentially the one of the light laterally illuminating the crystal. This is true in the case where the homogeneous conductivity of the crystal approaches the photoconductivity produced by the lateral control light. If this is not true, the waveguide shape can dynamically broaden beyond the width associated with the illumination. This situation is typically found in the absence of a homogeneous background radiation in low-conductivity materials. An example is LiTaO 3 , for which an interesting waveguide-splitting phenomenon was recently discovered [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF]. After the broadening of the waveguide, the removal of the applied field leads to the splitting of the guided light into two lobes outside the area originally occupied by the primary guide. This effect was qualitative explaned in terms of a re-screening of a space-charge distribution created by the initial screening of the applied field (double screening) [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF].

One of the most attractive features of the photorefractive nonlinearity is the possibility for optical steering or modulation of a light beam. Light deflection and modulation via the photorefractive effect has been demonstrated in the past by different techniques, most of which rely on dynamic holography [START_REF] Roosen | Optically generated light beam deflection[END_REF][START_REF] Voit | Optically induced variable light deflection by anisotropic Bragg diffraction in photorefractive KNbO 3[END_REF][START_REF] Fischer | Self Bragg matched beam steering using the double color pumped photorefractive oscillator[END_REF][START_REF] Petrov | Dynamic light beam deflection caused by space charge waves in photorefractive crystals[END_REF][START_REF] Honma | Photorefractive duplex two-wave mixing and all-optical deflection switch[END_REF]. Variable light deflection was obtained by isotropic [START_REF] Roosen | Optically generated light beam deflection[END_REF] or anisotropic diffraction [START_REF] Voit | Optically induced variable light deflection by anisotropic Bragg diffraction in photorefractive KNbO 3[END_REF] at a photorefractive Bragg grating tuned by a change of the recording wavelength. In alternative, a self Bragg matched configuration based on a double color pumped oscillator was also demonstrated [START_REF] Fischer | Self Bragg matched beam steering using the double color pumped photorefractive oscillator[END_REF]. Deflection of the reflected light was observed in sillenite crystals as a result of space-charge waves [START_REF] Petrov | Dynamic light beam deflection caused by space charge waves in photorefractive crystals[END_REF]. A photorefractive all-optical deflection switch was proposed in Ref. [START_REF] Honma | Photorefractive duplex two-wave mixing and all-optical deflection switch[END_REF] by simultaneous interference of two pairs of waves and control of their relative phases (duplex two-wave mixing). Non-holographic beam deflection was demonstrated in He + -implanted strontium barium niobate planar waveguides through the influence of a self-focused pump beam on a weaker probe beam [START_REF] Kip | All-optical beam deflection and switching in strontium-barium-niobate waveguides[END_REF]. In this case the effect was attributed to a combination of thermal and photorefractive effect. The lateral motion at constant velocity of a self-focused beam across a photorefractive crystal was also shown to give rise to strong beam deflection as a result of the inertia of the refractive index change dynamics [START_REF] She | Laser beam deflection in a photorefractive crystal induced by lateral beam movement[END_REF].

In this work we study the above mentioned waveguide splitting process in detail using the two low conductivity photorefractive crystals Sr x Ba 1-x Nb 2 O 6 (SBN) and LiTaO 3 . Upon removal of the electric field used to sustain the generation of the dynamic photoinduced waveguide, the light originally propagating in the waveguide is expelled from this region. We show that the double screening phenomenon mentioned above leads to a novel type of dynamic light deflection that may be controlled by adjusting different parameters. Among these the homogeneous background conductivity and the value of the electric field used during the waveguide recording step are the most important. Together with the shape of the lateral illumination, the background conductivity defines the initial conditions for the splitting process (the initial refractive index profile). The applied field controls the refractive index contrast and, together with the photorefractive response time, has a direct influence on the speed at which the light "expulsion" takes place. The experimental observations are qualitatively confirmed by numerical simulations of the beam propagation based on a simplified model for the dynamic evolution of the refractive index distribution. This model can explain the exceptionally large light "expulsion" distance observed in SBN. For this crystal the waveguide recording light is only weakly absorbed and the light reflected from the back surface of the crystal contributes in the definition of the shape of the refractive index distribution. Finally, it is shown that, using a periodically modulated applied electric field, a periodic switching of the output positions of the guided beam can be obtained under constant optical illumination. This new deflection-type switching is electrically controlled and requires the shaped control light merely as a kind of catalyst.

Experimental technique

Light induced waveguides were formed using a set-up similar to the one given in Ref. [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF] except for the absence of the homogeneous background illumination. Fig. 1 gives a simplified scheme of the set-up. The control illumination defines the region and shape of the primary waveguide through the combination of the mask and the imaging optics. The probe wave guided in this guide is observed by the CCD camera at the output face of the crystal. The experiments presented in this work were performed with the electro-optic crystal strontium barium niobate (Sr x Ba 1-x Nb 2 O 6 , x=0.61) weakly doped with 0.02 mol% Ce, and, for comparison, with near stoichiometric LiTaO 3 with a Mg doping of 0.7 mol%. The dimensions of the crystals were a × b × c = 10 × 5 × 5 mm 3 and a × b × c = 10 × 4 × 3 mm 3 , for SBN and LiTaO 3 , respectively. The controlling light defining the waveguide shape was produced by transmission through a straight slit imaged onto the crystal and was at the wavelength λ = 514 nm for SBN and at λ = 257 nm for LiTaO 3 . The former wavelength is moderately absorbed in SBN (with absorption constant α = 0.26 cm -1 ), while the latter is strongly absorbed in LiTaO 3 (α ≈ 690 cm -1 [START_REF] Mosimann | Determination of the absorption constant in the interband region by photocurrent measurements[END_REF]). An electric field was applied for both materials along the c-axis of the crystal in order to induce the waveguides in combination with the lateral control illumination. The direction of the field was such as to reduce the refractive index, what is generally known as the focusing case. The probe light was in both cases at λ = 633 nm and was polarized parallel to the crystal c-axis. Its propagation direction was along the longest direction for both crystals and its intensity was low, such that this wave was not influencing the waveguide formation. We concentrate in this work exclusively on the behavior observed upon removal or modulation of the electric field after a light induced waveguide was already formed by the process described in Refs. [START_REF] Ph | Fast, reconfigurable light-induced waveguides[END_REF][START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF] and reached steady-state. The applied electric field is therefore the only quantity that is varied during our measurements, i.e., we kept constant illumination conditions of the controlling light and constant coupling conditions for the red probe wave.

Beam splitting and deflection upon field removal

Figure 2 shows an example of the observed dynamics of the guided light exiting the SBN nonlinear crystal (back surface of the crystal imaged to a CCD camera). After the applied electric field is removed at the beginning of the movie the light splits into two lobes. The corresponding deflection angle varies with time and reaches a maximum before relaxing towards the center. In its final stage, after the end of the movie, the condition for natural diffraction is reached (absence of a waveguide). In this particular case the width of the one-dimensionally-guided wave before removal of the electric field was 16 µm (full-width at half maximum (FWHM) at the output crystal surface). Figure 3 shows the position of the "center of mass" of the two lobes as a function of time. All measurements were taken after a waveguide was recorded during the same time and at the same intensity of the controlling light. The only difference between the three curves is the value of the electric field E 0 applied during waveguide recording. The initial fast displacement speed becomes gradually slower before inverting its direction; the system relaxes then towards the conditions were no waveguides longer exist. The maximum beam displacement is larger when the field E 0 was larger. In the case of SBN shown here, the total maximum separation be- tween the two lobes is about 235 µm for a field of E 0 = 4 kV/cm. Note that this displacement largely exceeds the width of the original projected waveguide (25 µm), as well as the width of the naturally diffracting probe wave at the output of the crystal in absence of a waveguide (FWHM≈ 57 µm). Similar experiments performed in LiTaO 3 give generally smaller displacements of the light spots. As an example, Fig. 4 shows the near field image of the output surface of the LiTaO 3 crystal for the moment of maximum lobe distance. At the brighter spot position the separation is ≈ 92 µm, which is only slightly wider than the width of the naturally diffracted probe beam. It can be noticed that in this case the observed spots are slightly oblique. The spot distance increases to ≈ 105 µm closer to the surface illuminated by the UV control light and diminishes to ≈ 77 µm by moving down by about 70 µm. The reason for the appearance of these oblique spots will be discussed later. We observe the exceptionally large light "expulsion" distance in SBN even though the guided light is still relatively well confined at the moment where the field is removed (see Fig. 2). This is different than the situation generally encountered in LiTaO 3 , where, in absence of a background illumination, the probe light is no longer well guided at steady-state prior to field removal [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF]. A more complex refractive index structure seems therefore to be responsible for our observations in SBN. We will discuss these aspects in detail in the next section.

Time [s]

Modeling of beam propagation upon field removal

SBN

In order to elucidate better the above anomalous waveguide splitting behavior, we have performed numerical simulations of the probe beam propagation by the beam propagation method Fig. 4. Snapshot of waveguide splitting observed at the output surface of a LiTaO 3 crystal for the moment of maximum lobe separation. The electric field applied during recording of the primary waveguide was 5.5 kV/cm and the primary waveguide width was 20 µm. The UV control illumination comes from the top. [START_REF] Okamoto | Fundamentals of optical waveguides[END_REF][START_REF]Nonlinear fiber optics[END_REF]. In our model the one-dimensional refractive index profile is assumed to be invariant along the propagation direction z, but varies in time. Just after the removal of the electric field, the refractive index profile is assumed to possess the distribution

∆n(x) = ∆n 0 I(x) I(x) + I D , (1)
which applies to the case where the conventional photorefractive effect is at work. Here ∆n 0 is the refractive index change amplitude proportional to the applied electric field according to ∆n 0 = n 3 rE 0 /2, where n is the average refractive index, r is the active effective electrooptic coefficient and E 0 is the field applied during waveguide recording. The quantity I(x) is the spatially dependent intensity of the control light generating the waveguide. I D is the dark intensity [START_REF] Zozulya | Nonstationary self-focusing in photorefractive media[END_REF], that is the equivalent intensity producing the same density of mobile carriers than the one giving rise to the homogeneous component (average) conductivity of the crystal. Note that the dark intensity can be related to a combination of the dark conductivity and the photoconductivity due to a homogeneous background irradiation of the crystal, if the latter exists (see Ref. [START_REF] Ryf | Launching one-transverse-dimension photorefractive solitons in KNbO 3 crystals[END_REF] for a detailed discussion). In the following the quantities I(x) and I D will be normalized in such a way that I = 1 corresponds to the intensity of the controlling light on the crystal in the center of a perfectly imaged slit. Expression (1) corresponds to the refractive index distribution due to steady-state screening of the applied field after formation of the primary waveguide, shifted up by the value ∆n 0 as a result of the removal of the field E 0 . It was shown earlier, that a sufficiently high internal space-charge field opposite to the spontaneous polarization can induce ferroelectric domain reversal leading to the fixing of spatial soliton waveguides in SBN:75 crystals [START_REF] Klotz | Fixing the photorefractive soliton[END_REF]. In our SBN:61 crystal, this kind of waveguide fixing was not observed for the range of parameters and for the experimental procedure used in our investigations. Therefore we can safely neglect the effect of domain reversal in the description of the dynamic evolution of our photoinduced waveguides. In this framework, the relaxation of the refractive index distribution upon removal of the applied electric field can be represented in the simplest approximation as

∆n(x,t) = ∆n 0 I(x) I(x) + I D exp [-t (I(x) + I D )]. (2)
Here the dimensionless time t has been normalized to the value of the photorefractive response time τ PR for a normalized intensity equal to 1; τ PR depends principally on the conductivity and on the dielectric properties of the crystal [START_REF] Biaggio | Recording speed and determination of basic materials properties[END_REF]. The physical model underlying Eqs. ( 1) and ( 2) completely neglects all charge carrier diffusion effects. It assumes a fully local response dynamics, for which the local relaxation time is inversely proportional to the local total intensity [START_REF] Fressengeas | Temporal behavior of bidimensional photorefractive bright spatial solitons[END_REF]. Despite for the simplifying assumptions, this model maintains the most essential physical features and, as seen below, has the merit to reproduce the experimental observations in a satisfactory way.

A crucial aspect for the implementation of the model calculations is the choice of the light intensity distribution I(x). In a first step we have performed several simulations by associating I(x) solely with the control illumination directly incident on the region of the photoinduced waveguide (the green light propagating from bottom-left to top-right in Fig. 1). In the case of SBN we were never able to reproduce the observed behavior sufficiently well using a physically sound set of parameters. It appears therefore evident that the directly incident wave alone cannot lead to the strong repulsion observed. Our choice is therefore to consider an incoherent superposition of two components, I(x) = I 1 (x) + I 2 (x). The first, I 1 (x), is the control light directly incident from outside. This is the wave discussed above that is intended to produce the narrow primary waveguide. We take the simplifying assumption that the slit defining the waveguide is perfectly imaged at some plane inside the crystal and that the waveguide is being probed very close to this plane, in the Fresnel diffraction regime of the imaged slit. The normalized intensity I 1 (x) can then be expressed as

I 1 (x) = 1 2 [C(X 2 ) -C(X 1 )] 2 + [S(X 2 ) -S(X 1 )] 2 , (3)
where C(X) and S(X) are the Fresnel cosine and sine integrals, respectively. The integration limits are

X 2 = 2/(λ ′ d 1 )(x + a) and X 1 = 2/(λ ′ d 1 )(x -a)
, where 2a is the width of the imaged slit on the crystal, λ ′ = λ /n is the light wavelength in the medium, and d 1 is the distance between the waveguide probing depth and the depth of ideal imaging. The second component, I 2 (x), consists of the same light after propagating inside the crystal to the other lateral surface and being reflected back towards the region of the waveguide. In most cases this reflected light is already in the Fraunhofer diffraction regime. The normalized intensity I 2 (x) can be calculated as well using Eq. ( 3), by replacing the distance d 1 with the total path distance d 2 from the ideal plane of perfect imaging to the back lateral surface, and back to the waveguide. In addition, the intensity I 2 (x) of the back reflected light has to be further normalized by a factor As seen below, the refractive index contrast between the central primary guide and the plateau is nevertheless sufficient to guide the probe wave. For larger values of I D (blue dotted line in Fig. 5(b)) one obtains a stronger and better confined initial central waveguide. In fact, if I D exceeds the intensity level of the back reflected control light (which is about 3% at its maximum in our case), the plateau can be allmost completely eliminated. This is the concept used earlier for recording photoinduced waveguides with background illumination [START_REF] Ph | Fast, reconfigurable light-induced waveguides[END_REF][START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF], which experimentally leads to a much less dramatic dynamics upon field removal. On the other hand, for small values of I D (green dashed line in Fig. 5(b)), the formation of the central initial waveguide over the plateau is prevented and the probe light would no longer be guided before the removal of the applied field.

K = 1 -n 1 + n 2 exp(-αd 2 ), (4)
With the knowledge of the intensities I 1 (x) and I 2 (x) and of the initial distribution ∆n(x,t = 0), we can calculate the evolution of the refractive index profile of the waveguide using Eq. ( 2). This z-independent profile can then be used to calculate the propagation of the red probe wave at any time by the beam propagation method [START_REF] Okamoto | Fundamentals of optical waveguides[END_REF][START_REF]Nonlinear fiber optics[END_REF]. As an example, Fig. 6 shows the calculated dynamics for SBN upon removal of the applied field. The temporal evolution of the probe beam propagation is calculated for a set of parameters corresponding to those used experimentally. The maximum refractive index change ∆n 0 = 3.5 × 10 -4 used in the simulation can be induced by a field E 0 = 2.4 kV/cm (corresponding to the intermediate field in Fig. 3) via the electrooptic coefficient r 333 = 235 pm/V of SBN (x = 0.61) [START_REF] Ducharme | Electrooptic and piezoelectric measurements in photorefractive barium titanate and strontium barium niobate[END_REF].

Figure 6 shows the temporal evolution of the probe wave propagation, of the refractive index profile and of the probe wave output intensity. At the time t = 0 the refractive index profile corresponds to the one given by the solid line in Fig. 5(b), the index contrast between the central region and the plateau is enough to guide the probe wave, in agreement with the experiments. The following simulated time evolution shows that the probe light is rapidly expelled from the initial central waveguide, it reaches the maximum distance for a time of the order of 5 times the photorefractive response time τ PR , before slowly relaxing back to a straight propagation. The calculated dynamics of the waveguide splitting process is in good qualitative agreement with the observed one (see Fig. 2 and Fig. 3). The simulated spot separation distances are consistent with those observed experimentally. We recall that the simulations are calculated under simplified ideal conditions. The strong effect of the border of the refractive index change profile associated to the central lobe of the diffracting back reflected control light is a consequence of this simplication. In the experimental situation, any scattering stray light, as well as multiple reflections, contribute to smooth the refractive index contrast at the border of the central lobe.

Our observations of Fig. 3 show that the probe light splits faster and further apart if the field that is applied during the primary waveguide recording is larger. Figure 7 shows a snapshot of the initial splitting (t = 0.3) of the probe wave for three values of ∆n 0 corresponding to the three values of the field in Fig. 3. The stronger initial spatial splitting for the higher fields can be easily recognized, in agreement with the experimental observations. It has to be noted, that for materials with short diffusion lengths, such as our SBN crystal, the photorefractive response time is a decreasing function of the electric field [START_REF] Biaggio | Recording speed and determination of basic materials properties[END_REF]. Therefore, the same normalized time corresponds to an earlier "real" time for the case of a large field than for the case of a low field. This effect contributes to accelerate further the dynamics for the larger fields with respect to what appears from Fig. 7.

Propagation distance [mm]

Position [µm]

LiTaO 3

In the case of LiTaO 3 the control light is strongly absorbed and induces direct band-to-band phototransitions. For such interband processes the quadratic recombination of carriers leads to a photoconductivity which increases only with the square root of the light intensity [START_REF] Montemezzani | Interband photorefractive effects: Theory and experiments in KNbO 3[END_REF]. This has an effect on the screening of the applied electric field. By assuming that the square root dependence is valid over the whole range of relevant intensities, Eqs. ( 1) and ( 2) have to be modified, and Eq. ( 2) is replaced by ∆n(x,t) = ∆n 0 I(x)

I(x) + √ I D exp -t I(x) + √ I D . (5)
Here the same intensity normalization as above is used and the role of I D is the same as in the case of SBN. Due to the large absorption constant (≈ 690 cm -1 [START_REF] Mosimann | Determination of the absorption constant in the interband region by photocurrent measurements[END_REF]), the back reflected control wave I 2 (x) does not play any role in the case of LiTaO 3 . Nevertheless, in the absence of a background illumination a significant widening of the primary waveguide during recording (with field on) is observed, as was discussed in [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF]. This widening is due to control light surrounding the ideal imaged slit defining the waveguide (stray light). A combination of diffraction effects (described in first approximation by the function I 1 (x) of Eq. ( 3)) and of scattering effects due to bulk defects or surface imperfections (more difficult to describe mathematically) is expected to contribute to the stray light producing the widening. Even though the intensity level of the scattering might be very small, it can lead to quite strong widening because of the very low levels of the dark intensity I D proper of LiTaO 3 under UV illumination. The quantity I D can be estimated by considering the depth until which a holographic grating can be recorded by the UV light. This depth corresponds roughly to the position where I/I D = 1 and is of the order of 250 µm [START_REF] Juvalta | Deep UV light induced, fast reconfigurable and fixed waveguides in Mg doped LiTaO 3[END_REF] for crystals similar to the one used in our measurements. Using the above absorption constant we can then estimate a ratio of the order of I/I D = 10 5 at the depth of 80-90 µm of our waveguides. The main reason for the very small value of I D is the high quantum efficiency connected with the interband phototransitions. Below, we will discuss some simulations of the probe beam propagation in LiTaO 3 by considering the refractive index evolution given by Eq. ( 5). For simplicity we neglect the effect of scattering and limit the description of the stray light to the diffractive component by using the expression (3) for the control light intensity, always with a non vanishing value for the distance d 1 .

Figure 8(a) shows the calculated propagation of the probe wave in the stationary state just before the applied field is removed. By considering the electro-optic response of LiTaO 3 [START_REF] Juvalta | Electro-optical properties of near-stoichiometric and congruent lithium tantalate at ultraviolet wavelengths[END_REF], the refractive index amplitude ∆n 0 used for the simulations corresponds to an applied field of 5.5 kV/cm. The wave is only badly guided due to the fact that the waveguide has suffered a significant widening, as seen by the refractive index distribution in Fig. 8(c), which applies to the same situation. Fig. 8(b) shows the same propagation but for a normalized time t = 5 after removing the applied electric field, which corresponds roughly to the moment of maximum separation. Figure 8(d) shows the refractive index distribution at the same time. As in the case of SBN, we observe the splitting of the propagating wave into two lobes. However, the calculated separation distance between the lobes is smaller than in SBN, which is in agreement with the observations in the two crystals (compare Fig. 2 and Fig. 4) and with the model simulations for SBN (Fig. 6).

As discussed earlier, the near field experimental observations in LiTaO 3 (Fig. 4) show that the two lobes are slightly tilted with a larger separation closer to the entrance surface of the control light. Due to the large absorption, a change in depth is connected to a change of the normalized dark intensity I D . We discuss the lobe tilt with the help of Fig. 8(e I D = 8.9x10 -7 Fig. 8. Model calculations for the case of LiTaO 3 using Eqs. ( 3) and ( 5) with the parameters ∆n 0 = 8.8 × 10 -5 , 2a = 20µm, n = 2.72 and a probe beam input waist of 15 µm. ever, our simulations have shown that, for the range of intensity-to-dark-intensity ratio in which we operate experimentally, the change of the parameter d 1 has only a very small influence on the spot obliquity with respect to the influence of the normalized I D . Indeed the simulations of Fig. 8(e) correctly predict a larger spot separation for the top diagram (see dashed green helping line) that corresponds to the layer closer to the surface. This larger separation is due to the stronger widening occurring for the larger values of the ratio I/I D . The calculations predict a decrease of the separation by about 25-30 µm for a depth increase of 70 µm, which is in quite good agreement with the observations of Fig. 4, the absolute value of the spot separation is matched within roughly 20% between experiments and simulations. It is worth noticing that, if we perform the simulations using Eq. ( 2) instead as with Eq. ( 5), we obtain a much stronger dependence of the spot separation on the normalized value of I D . The spot obliquity predicted by Eq. ( 2) is nearly doubled, what prevents to match the experimental data. This proves the necessity to take into account the square root dependence of the photoconductivity on the light intensity in the model.

Modulation of the transmitted light by waveguide anti-waveguide alternation

Since the removal of the electric field prevents the probe light to remain guided in its original photo-induced waveguide, we can use this effect for a novel light modulation technique. The application of a periodic high-voltage to the crystal leads to a waveguide and an anti-waveguide appearing cyclically at the place illuminated by the shaped control light. The modulation occurs through the coupling of the spatial position of the output beam to the electric field, without changing any of the illumination conditions. Figure 9 shows an example of this modulation as obtained in SBN under a periodic applied field of triangular shape. Note that in the experiment of Fig. 9 we have deliberately slightly misaligned the incidence direction of the probe wave with respect to the axis of the waveguide. In this way, upon removal of the field, the light is expelled only on one side of the waveguide. In the example given in Fig. 9 , when considering the conditions separated by half a voltage cycle, the output position of the probe beam shifts by roughly 90 µm. When repeating the same kind of experiments with LiTaO 3 similar results are obtained, however the observed shift is of the order of 40 µm in this case. In order to better characterize the dynamics of the effect, we have inserted a small pinhole in the image plane of the crystal's output surface and detected the transmission through this pinhole by a photodiode. Figure 10 shows an example of this time dependence for the case of LiTaO 3 and three different frequencies of the applied field. The diameter of the measuring pinhole was one half the nominal width of the photoinduced waveguide. The intensity of the incident UV controlling light at the surface of the crystal was 1.1 W/cm 2 . Considering that the waveguide was probed at an average depth of ≈ 90µm, the local UV intensity in the probed region was ≈ 2 mW/cm 2 . The dynamics of Fig. 10 is following the particular form of the voltage delivered by the high voltage power supply being used. Nevertheless, at the two higher frequencies, a slight delay between the maximum of the applied voltage and the maximum of the transmitted intensity can be recognized. In these conditions, the field can lead to an increase of the waveguide strength even at the beginning of its decreasing half period. When compared to the period T of the applied field, at the above intensity the resulting retardation between the red and blue curve is roughly 0.15 × T for T = 100 ms, 0.04 × T for T = 335 ms, while it becomes nearly irrelevant at lower frequencies. As can be expected due to a slower dynamics, this retardation increases if the controlling light intensity is reduced. For instance, for a 40 times lower intensity we get a phase retardation of 0.35 × T at T = 100 ms. The maximum modulation amplitude of the transmitted probe light is found for the above experimental conditions in LiTaO 3 when the applied field period is in the range of 200-350 ms.

µm

For similar experiments performed using SBN we obtain essentially the same kind of results as those depicted in Fig. 10. Here the optimum modulation amplitude is found for an applied electric field period of the order of 1 second (incident controlling light intensity = 90 mW/cm 2 ). At this intensity the retardation discussed above goes from 0.2 × T at T = 400 ms down to 0.002 × T at T = 10 s. It should be noted that in SBN, due to the much lower absorption of the controlling light, the observed dynamics is much less dependent on the probing depth below the surface as in the case of LiTaO 3 .

Conclusions

The evolution of light induced one-dimensional waveguides when the sustaining electric field is switched off leads to a novel kind of dynamic light deflection. We have studied this effect in detail using SBN and LiTaO 3 crystals. Simulations of the beam propagation in the split waveguide on the base of a simple model lead to a good agreement with the experimental observations. In the case of SBN the spot separation can exceed the original waveguide width by 10 times. It is found that the control light back reflected from the second lateral surface is responsible for the additional waveguide widening, which leads to this large deflection distance. In LiTaO 3 the primary waveguide widening is due solely to stray light and gives smaller deflection distances. In this material the strong absorption constant leads to oblique spots after waveguide splitting which have been successfully modeled. Application of a modulated electric field leads to the modulation of the transmitted probe light as a result of a waveguide anti-waveguide alternation. This novel modulation method has been demonstrated for low frequencies of the applied field. Faster speeds are expected by increasing the local intensity of the controlling light. The use of materials with higher photosensitivity, such as Sn 2 P 2 S 6 or reduced KNbO 3 , is also expected to lead to faster modulation speeds in a regime that uses the conventional photorefractive effect, which allows to obtain a waveguide dynamics being virtually independent from the observation depth.

Fig. 1 .

 1 Fig. 1. Simplified scheme of the experimental set-up. L1, L2: spherical lenses; CL1, CL2: cylindrical lenses; ND: neutral density filter. A voltage U is applied to the photorefractive crystal.

Fig. 2 .

 2 Fig. 2. (1.2 MB) Waveguide splitting and relaxation upon removal of the applied electric field (E 0 = 4 kV/cm) in the SBN crystal. The initial photoinduced waveguide was recorded to steady state using 514 nm light. The local intensity was 125 mW/cm 2 in the 25 µm wide imaged slit on the crystal lateral surface. The lateral illumination is maintained after removal of the applied field. The movie is in real time, the width of the imaged area is 410 µm.

Fig. 3 .

 3 Fig.3. Position of the "center of mass" of the expelled light lobes as a function of time. The initial photoinduced waveguides were recorded in SBN during 10 seconds to steady-state. The local intensity was 375 mW/cm 2 in the 25 µm wide imaged slit. The curves differ by the field E 0 applied during waveguide recording and removed at time t = 0. Red solid line: E 0 = 4 kV/cm, blue dotted line: E 0 = 2.4 kV/cm, green dashed line: E 0 = 1.6 kV/cm.

  that takes into account the Fresnel reflection and absorption of the controlling light (absorption constant = α). The light distribution I(x) = I 1 (x) + I 2 (x) is depicted in Fig.5(a) for a set of parameters proper to our crystal sample and experiments. The corresponding initial refractive index distributions according to Eq. (1) are shown in the same figure for three values of the normalized dark intensity I D . The value I D = 0.005 is consistent with the observed ratio between the formation time and the dark lifetime of the photoinduced structures in our crystal. The refractive index distribution of Fig.5(b)shows that in this case the initial primary waveguide sits on a wider plateau of increased refractive index induced by the back reflected control light.

Fig. 5 .

 5 Fig. 5. (a) Light intensity I = I 1 + I 2 for the parameters 2a = 25µm, d 1 = 10µm, d 2 = 9.5 mm, n = 2.33, α = 0.26 cm -1 ; (b) Refractive index distribution just after removal of the applied field for I D = 0.005 (red solid curve), I D = 0.1 (blue dotted curve), and I D = 0.0001 (green dashed curve).

Fig. 6 .

 6 Fig. 6. (1.5 MB) Simulated time evolution of the waveguide splitting phenomenon after removing the sustaining applied electric field at the time t = 0. The left-hand side shows the propagation of the probe beam in the SBN crystal containing the splitted photoinduced waveguide with the given color scale for its intensity. The top-right diagram shows the evolution of the refractive index profile according to Eq. (2). The bottom-right diagram shows the profile of the probe beam intensity on the output surface of the crystal. Parameters: ∆n 0 = 3.5 × 10 -4 , I D = 0.005, input waist of probe beam = 18 µm. All other parameters as in Fig.5. The time is normalized to the photorefractive response time. The temporal distance between frames is not constant.

Fig. 7 .

 7 Fig. 7. Initial splitting of the waveguide at the normalized time t = 0.3 for three values of ∆n 0 . (a) ∆n 0 = 6 × 10 -4 (E 0 ≈4 kV/cm); (b) ∆n 0 = 3.5 × 10 -4 (E 0 ≈2.4 kV/cm); ∆n 0 = 2.4 × 10 -4 (E 0 ≈1.6 kV/cm). The other parameters are as in Fig. 6.

3 I D = 10 - 5 I

 3105 ), where we have calculated the output intensity profile of the probe beam for three different values of I D , corresponding to three depths mutually separated by 35 µm. Together with I D , we have changed also the value of the imaging mismatch d 1 , increasing it from 10 µm for the top diagram in Fig.8(e), to 45 µm for the middle one, and to 80 µm for the bottom one. In general, larger values of d 1 lead to wider intensity distributions that may lead to bigger spot separations. How-D = 1.1x10-4

  Fig.8. Model calculations for the case of LiTaO 3 using Eqs. (3) and (5) with the parameters ∆n 0 = 8.8 × 10 -5 , 2a = 20µm, n = 2.72 and a probe beam input waist of 15 µm. (a) Probe beam propagation in the primary waveguide widened to steady-state at t = 0 for I D = 10 -5 and d 1 = 45 µm. (b) Same as (a) but for the time t = 5 after splitting of the waveguide. (c) and (d) Refractive index profiles for case (a) and (b), respectively. (e) Output probe beam intensity profile at three depths for t = 5. The central diagram corresponds to the case (b). The upper diagram to a position 35 µm closer to the surface (I D = 8.9×10 -7 , d 1 = 10 µm). The lower diagram to a position 35 µm deeper (I D = 1.1 × 10 -4 , d 1 = 80 µm). The dashed green line is a guide for the eye evidencing the relation with the spot obliquity of Fig. 4.

Fig. 9 .

 9 Fig. 9. (1.2 MB) Modulation of the output position of the probe beam under a periodic electric field. A triangularly shaped electric field with amplitude 2 kV/cm and frequency 1 Hz is applied to the crystals. The resulting waveguide-antiwaveguide alternation results in the periodically varying output position of the probe wave. The two frames shown above are separated by half a period, the corresponding displacement between the two positions is about 90 µm. SBN crystal, controlling wave intensity = 0.4 W/cm 2 . The width of the imaged area in the multimedia file is 480 µm.

Fig. 10 .

 10 Fig. 10. Waveguide modulation dynamics for LiTaO 3 as measured by transmission of the probe wave through a pinhole (red thick line). The modulated applied field is shown by the thin blue line. a) 0.3 Hz modulation, b) 5 Hz, c) 10 Hz.

Acknowledgements

This work was performed in the framework of the PAI bilateral program Germaine de Staël between France and Switzerland. We are very grateful to Dr. K. Kitamura (NIMS, Tsukuba, Japan) for the LiTaO 3 crystals. F. J., M. J. and P. G. also acknowledge partial support by the Swiss National Science Foundation.


Guillaume Ducoffe

FASTER APPROXIMATION ALGORITHMS FOR COMPUTING SHORTEST CYCLES ON WEIGHTED GRAPHS *

Keywords: Girth, Weighted Graphs, Approximation Algorithms AMS subject classifications. 05C85, 68Q25, 68W25, 68R10

Given an n-vertex m-edge graph G with non-negative edge-weights, a shortest cycle is one minimizing the sum of the weights on its edges. The girth of G is the weight of a shortest cycle. We obtain several new approximation algorithms for computing the girth of weighted graphs:

• For any graph G with polynomially bounded integer weights, we present a deterministic algorithm that computes, in Õ(n 5/3 + m)-time 1 , a cycle of weight at most twice the girth of G. This matches the approximation factor of the best known subquadratic-time approximation algorithm for the girth of unweighted graphs. • Then, we turn our algorithm into a deterministic (2 + ε)-approximation for graphs with arbitrary non-negative edge-weights, at the price of a slightly worse running-time in Õ(n 5/3 polylog(1/ε) + m). For that, we introduce a generic method in order to obtain a polynomial-factor approximation of the girth in subquadratic time, that may be of independent interest. • Finally, if we assume that the adjacency lists are sorted then we can get rid off the dependency in the number m of edges. Namely, we can transform our algorithms into an Õ(n 5/3 )-time randomized 4-approximation for graphs with non-negative edge-weights. This can be derandomized, thereby leading to an Õ(n 5/3 )-time deterministic 4-approximation for graphs with polynomially bounded integer weights, and an Õ(n 5/3 polylog(1/ε))-time deterministic (4 + ε)-approximation for graphs with non-negative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs.

1. Introduction. The exciting program of "Hardness in P" aims at proving (under plausible complexity theoretic conjectures) the exact time-complexity of fundamental, polynomial-time solvable problems in computer science. In this paper, we consider the Girth problem on edge-weighted undirected graphs, for which almost all what is known in terms of finer-grained complexity only holds for dense graphs (m = Ω(n 2 )). We recall that the girth of a given graph G is the minimum weight of a cycle in G -with the weight of a cycle being defined as the sum of the weights on its edges (see Sec. 2 for any undefined terminology in this introduction). For dense graphs this parameter can be computed in time O(n 3 ), and Vassilevska Williams and Williams [START_REF] Vassilevska Williams | Subcubic equivalences between path, matrix, and triangle problems[END_REF] proved a bunch of combinatorial subcubic equivalences between Girth and other path and matrix problems. In particular, for every ε > 0, there cannot exist any combinatorial (4/3 -ε)-approximation algorithm for Girth that runs in truly subcubic time unless there exists a truly subcubic combinatorial algorithm for multiplying two Boolean matrices. Roditty and Tov completed this above hardness result with an Õ(n 2 /ε)-time (4/3 + ε)-approximation algorithm [START_REF] Roditty | Approximating the girth[END_REF], thereby essentially completing the picture of what can be done combinatorially in subcubic time.

However, the story does not end here for at least two reasons. A first simple but important observation is that as the graphs considered get sparser, the complexity for computing their girth falls down to O(n2 ). In fact, when the edge-weights are integers bounded by some constant M , there is a non-combinatorial algorithm for computing the girth of any n-vertex graph G in time Õ(M n ω ) where ω stands for the exponent of square matrix multiplication over a ring [START_REF] Roditty | Minimum weight cycles and triangles: Equivalences and algorithms[END_REF]. It is believed that ω = 2 [START_REF] Robinson | Toward an optimal algorithm for matrix multiplication[END_REF], and if true, that would imply we can compute the exact value of the girth in quasi quadratic time -at least when edge-weights are bounded. So far, all the approximation algorithms for Girth on weighted graphs run in Ω(n 2 )-time [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF][START_REF] Roditty | Approximating the girth[END_REF]. This leads us to the following, natural research question:

Does there exist a subquadratic approximation algorithm for Girth on weighted graphs? In this paper, we answer to this above question in the affirmative.

1.1. Our contributions. We present new approximation algorithms for the girth of graphs with non-negative real edge-weights. These are the first algorithms to break the quadratic barrier for this problem -at the price of a slightly worse approximation factor compared to the state of the art [START_REF] Roditty | Approximating the girth[END_REF] -see Sec. 1.2 on the Related work for more details.

In what follows, we ignore the cost of arithmetic operations (for graphs with bounded integer edge-weights, this can only change the final running time by a factor polylogM ; for graphs with real edge-weights, this is essentially equivalent to consider the real RAM model).

Our first result is obtained for graphs with bounded integer edge-weights. Theorem 1.1.

For every G = (V, E, w) with edge-weights in {1, . . . , M }, we can compute a deterministic 2-approximation for Girth in time Õ(n 5/3 polylogM + m).

Our starting point for Theorem 1.1 is a previous 2-approximation algorithm from Lingas and Lundell [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF], that runs in quadratic time. Specifically, these two authors introduced an Õ(n log M )-time procedure that takes as entry a specified vertex of the graph and needs to be applied to every vertex in order to obtain the desired 2approximation of the girth. Inspired by the techniques used for approximate distance oracles [START_REF] Thorup | Approximate distance oracles[END_REF] we informally modify their algorithm as follows. We only apply their procedure to the vertices in a random subset S: where each vertex is present with equal probability n -1/3 (we can derandomize our approach by using known techniques from the litterature [START_REF] Roditty | Deterministic constructions of approximate distance oracles and spanners[END_REF]). Furthermore, for the vertices not in S, we rather apply a modified version of their procedure that is restricted to a small subgraph -induced by some ball of expected size O(n 1/3 ). A careful analysis shows this is a 2-approximation.

The reason why this above approach works is that, when we run the procedure of Lingas and Lundell at some arbitrary vertex s, it will always detect a short cycle if there is one passing close to s (but not necessarily passing through s itself). This nice property has been noticed and exploited for related algorithms on unweighted graphs [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF] 2 . However, we think we are the first to prove such a property in the weighted case. We note that one of the two algorithms proposed by Roditty and Tov in [START_REF] Roditty | Approximating the girth[END_REF] also satisfies such a property. We did not find a way to exploit their algorithm in order to improve our approximation factor.

Our approach for graphs with bounded integer edge-weights (see Sec. 3.2) is the cornerstone of all our other results in the paper. We considerably refine this approach so that it also applies to graphs with arbitrary non-negative edge-weights.

Theorem 1.2.

For every ε > 0 and G = (V, E, w) with non-negative edgeweights, we can compute a deterministic (2 + ε)-approximation for Girth in time Õ(n 5/3 polylog1/ε + m).

We note that in [START_REF] Roditty | Approximating the girth[END_REF], Roditty and Tov introduced a nice technique -that we partly reuse in this paper -in order to transpose their results for bounded integer-weights to arbitrary weights. However, we face several new difficulties, not encountered in [START_REF] Roditty | Approximating the girth[END_REF], due to the need to perform all the intermediate operations in subquadratic time. As a side contribution of this work, we present an intricate modification of our approach for graphs with bounded integer edge-weights that we use in order to approximate the girth of graphs with arbitrary non-negative edge-weights up to a polynomial-factor. This subquadratic-time routine could be useful to anyone improving our result for the graphs with integer-weights in order to generalize their results to the graphs with non-negative real weights.

Our algorithms are subquadratic in the size of the graph, but they may be quadratic in its order n if there are m = Θ(n 2 ) edges. By a folklore application of Moore bounds, any unweighted graph with O(n 1+ 1 ) edges has girth at most 2 , and so, we can always output a constant upper-bound on the girth of moderately dense graphs. It implies that the dependency on m can always be removed in the running-time of approximation algorithms for the girth of unweighted graphs.

However, we can prove by using elementary arguments that any approximation algorithm for the girth on weighted graphs must run in Ω(m)-time. Specifically, given G = (V, E, w) with positive integer weights, add a fresh new vertex u / ∈ V and the edges vu, v ∈ V with (unit) weight w uv = 1. Then, the girth of this new graph G is exactly 2 + w min where w min denotes the minimum edge-weight in G. Since any constant-factor approximation algorithm for computing w min essentially requires time Ω(m), so does any constant-factor approximation algorithm for the girth of weighted graphs.

We study what happens if we have sorted adjacency lists 3 . Theorem 1.3. Let G = (V, E, w) have sorted adjacency lists.

1. If all edge-weights are in {1, . . . , M } then, we can compute a deterministic 4-approximation for Girth in time Õ(n 5/3 polylogM ). 2. If all edge-weights are non-negative then, we can compute a randomized 4approximation for Girth in time Õ(n 5/3 ). For every ε > 0, we can also compute a deterministic (4+ε)-approximation for Girth in time Õ(n 5/3 polylog1/ε). We observe that even assuming sorted adjacency lists, it is not clear whether the algorithm of Theorem 1.1 can be implemented to run in time Õ(n 5/3 polylogM ). Indeed, this algorithm requires to build several induced subgraphs in time roughly proportional to their size, that requires a different preprocessing on the adjacency lists. We prove that we do not need to construct these induced subgraphs entirely in order to derive a constant-factor approximation of the girth. Similarly, for graphs with non-negative edge-weights we cannot use our polynomial-factor approximation algorithm for the girth directly, as it needs to enumerate all edges in the graph. We overcome this difficulty through the help of a classical density result for the C 4 -free unweighted graphs [START_REF] Brown | On graphs that do not contain a Thomsen graph[END_REF].

Related work.

Approximation algorithms for the girth. Itai and Rodeh were the first to study the Girth problem for unweighted graphs [START_REF] Itai | Finding a minimum circuit in a graph[END_REF]. Among other results, they showed how to compute an additive +1-approximation of the girth in time O(n 2 ). This was later completed by Lingas and Lundell [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF], who proposed a randomized quasi 2-approximation algorithm for this problem that runs in time O(n 3/2 √ log n). In [START_REF]Subquadratic time approximation algorithms for the girth[END_REF], Roditty and Vassilevska Williams presented the first deterministic approximation algorithm for the girth of unweighted graphs. Specifically, they obtained a 2-approximation algorithm in time Õ(n 5/3 ), and they conjectured that there does not exist any subquadratic (2 -ε)-approximation for Girth. We obtain the same approximation factor for weighted graphs, and we almost match their running time up to polylog factors and to an additional term in Õ(m). It would be interesting to know whether in our case (if the adjacency lists are sorted), this dependency on m can be removed while preserving the approximation factor 2.

Recently, new subquadratic-time approximation algorithms were proposed for Girth in unweighted graphs (see [START_REF] Dahlgaard | New subquadratic approximation algorithms for the girth[END_REF]), showing various trade-offs between the running time and the best achievable approximation factor. It is open whether one can achieve a constant-factor approximation for the girth in, say, Õ(n 1+o(1) )-time.

Much less is known about the girth of weighted graphs. The first known subcubic approximation was the one of Lingas and Lundell [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF], that only applies to graphs with bounded integer edge-weights. Their work somewhat generalizes the algorithm of Itai and Rodeh for unweighted graphs. The approximation factor was later improved to 4/3 by Roditty and Tov, still for the graphs with bounded integer weights, and to 4/3 + ε for the graphs with arbitrary weights [START_REF] Roditty | Approximating the girth[END_REF]. Our algorithms in this paper are faster than these two previous algorithms, but they use the latter as a routine to be applied on several subgraphs of sublinear size. Therefore, the approximation factors that we obtain cannot outperform those obtained in [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF][START_REF] Roditty | Approximating the girth[END_REF].

Since the preliminary version of this work was published, a randomized constantfactor approximation algorithm for the girth of directed weighted graphs was obtained in [START_REF] Chechik | Constant girth approximation for directed graphs in subquadratic time[END_REF] (see also [START_REF] Pachocki | Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners[END_REF] for a previous logarithmic approximation). For undirected graphs, we obtain a better approximation ratio than in [START_REF] Chechik | Constant girth approximation for directed graphs in subquadratic time[END_REF]. Furthermore, our algorithms are deterministic.

Approximate distances. Finally, approximation algorithms for the girth are tightly related to the computation of approximate distances in weighted graphs. In a seminal paper [START_REF] Thorup | Approximate distance oracles[END_REF], Thorup and Zwick showed that we can compute in expected time O(mn 1/k ) an approximate distance oracle: that can answer any distance query in time O(k) with a multiplicative stretch at most 2k -1. This has been improved in several follow-ups [START_REF] Baswana | Approximate distance oracles for unweighted graphs in expected o (n 2) time[END_REF]5,[START_REF] Patrascu | Distance oracles beyond the thorup-zwick bound[END_REF][START_REF] Roditty | Deterministic constructions of approximate distance oracles and spanners[END_REF][START_REF] Wulff-Nilsen | Approximate distance oracles with improved preprocessing time[END_REF].

However, the construction of most oracles already takes (super)quadratic time for moderately dense graphs. A key observation is that we do not need to construct these oracles entirely if we just want to approximate the girth. This allows us to avoid a great deal of distance computations, and so, to lower the running time.

1.3. Organization of the paper. We start gathering in Section 2 some known results from the literature that we will use for our algorithm.

Then, in Section 3, we give some new insights on the algorithm of Lingas and Lundell [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF] before presenting our main result for graphs with bounded integer edgeweights. Our algorithm is then generalized to graphs with arbitrary weights. Finally, we remove the dependency on the number of edges in the time complexity of our algorithms (assuming sorted adjacency lists, and at the price of a larger approximation factor than 2).

We conclude this paper with some open perspectives (Section 6).

Results of this paper were partially presented at the ICALP'19 conference [START_REF] Ducoffe | Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs[END_REF].

2.

Preliminaries. Graphs in this study are finite, simple (hence, without any loop nor multiple edges), connected and edge-weighted. Specifically, we denote a weighted graph by a triple G = (V, E, w) where w : E → R + is the edge-weight function of G. The weight of a subgraph H ⊆ G, denoted w(H) := e∈E(H) w e , is the sum of the weights on its edges. The girth of G is the minimum weight of a cycle in G. The distance dist G (u, v) between any two vertices u, v ∈ V is the minimum weight of an uv-path in G. By extension, for every v ∈ V and S ⊆ V we define dist G (v, S) := min u∈S dist G (u, v). -We will sometimes omit the subscript if no ambiguity on the graph G can occur. -For any v ∈ V and r ≥ 0, we also define the ball y). We refer to [START_REF] Bondy | Graph theory[END_REF] for any undefined graph terminology. For every

B G (v, r) := {u ∈ V | dist G (u, v) ≤ r}. Finally, an r-nearest set for v is any r-set N r (v) such that, for any x ∈ N r (v) and y / ∈ N r (v), we have dist G (v, x) ≤ dist G (v,
v ∈ V , let N G (v) = {u ∈ V | uv ∈ E} be the (open) neighbourhood of vertex v and let d v = |N G (v)| be its degree. Let Q v = {vu | u ∈ N G (v)
} be totally ordered. We call it a sorted adjacency list if edges incident to v are ordered by increasing weight, i.e., Q v = (vu 1 , vu 2 , . . . , vu dv ) and w vui ≤ w vui+1 for every i < d v . However, we call it an ordered adjacency list if, given some fixed total ordering ≺ over V the neighbours of v are ordered according to ≺ (i.e., u i ≺ u i+1 for every i < d v ). Throughout the rest of the paper we will assume that each vertex has access to two copies of its adjacency list: one being sorted and the other being ordered. The former can always be ensured up to an Õ(m)-time preprocessing.

2.1. The Hitting Set method. We gather many well-known facts in the literature, that can be found, e.g., in [START_REF] Roditty | Deterministic constructions of approximate distance oracles and spanners[END_REF][START_REF] Thorup | Approximate distance oracles[END_REF][START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF][START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF]. All these facts are combined in order to prove the following useful result for our algorithms:

Proposition 2.1. For any graph G = (V, E, w) with sorted adjacency lists, in Õ(n 5/3 )-time we can compute a set S ⊆ V , and the open balls B S (v) := {u ∈ V | dist(v, u) < dist(v, S)} for every v ∈ V , such that the following two properties hold true:

1. |S| = Õ(n 2/3 ); 2. and for every v ∈ V we have |B S (v)| = O(n 1/3 ). It is well-known that a set S as requested by Proposition 2.1 can be constructed randomly as follows: every vertex in V is added in S with equal probability n -1/3 [START_REF] Thorup | Approximate distance oracles[END_REF]. This construction was derandomized in [START_REF] Roditty | Deterministic constructions of approximate distance oracles and spanners[END_REF][START_REF] Thorup | Approximate distance oracles[END_REF][START_REF] Aingworth | Fast estimation of diameter and shortest paths (without matrix multiplication)[END_REF][START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF].

We will use the following two lemmata: Lemma 2.2 ( [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF]). For every G = (V, E, w), v ∈ V and r ≥ 0, we can compute an r-nearest set for v in time O(r 2 ) (assuming sorted adjacency lists). Furthermore, all the vertices in this set can be labeled with their distance to v within the same amount of time.

Lemma 2.3 ([1]

). Given n sets of size r over a universe of size s, a set S of size O(s/r log n) hitting all n sets in at least one element can be found deterministically in time O(s + nr).

Proof of Proposition 2.1. Set r = n 1/3 . We compute an r-nearest set N r (v) for every vertex v ∈ V , that can be done in total time O(n • n 2/3 ) = O(n 5/3 ) by Lemma 2.2. By Lemma 2.3 (applied for s = n) we can compute in time O(n+n•n 1/3 ) = O(n 4/3 ) a set S of size Õ(n 2/3 ) that intersects all the nearest sets N r (v). Since, for every v ∈ V , we have B S (v) ⊆ N r (v) by construction, we can compute this ball in time O(r) simply by scanning the r-nearest set, and so, we can compute all the balls

B S (v), v ∈ V in total time O(nr) = O(n 4/3 ).
In what follows we will not only need the balls B S (v) for every vertex v, but also the subgraphs these balls induce in G. Next, we prove that all these subgraphs can be obtained almost for free.

Lemma 2.4 (folklore). For every G = (V, E, w) and

U ⊆ V we can compute the subgraph G[U ] induced by U in time Õ(|U | 2 ) (assuming ordered adjacency lists).
Proof. For every x, y ∈ U we search whether yx is present in the adjacency list of y. Since the adjacency lists are ordered, this can be done in time O(log n) by using a dichotomic search.

3. Case of graphs with bounded integer weights. This section is devoted to the proof of Theorem 1.1. We start presenting some new properties of a previous approximation algorithm for the girth of weighted graphs (Section 3.1) as we will need to use them in our own algorithm. Then, we prove our main result for graphs with bounded integer weights in Section 3.2.

Reporting a close short cycle.

We propose a deeper analysis of an existing approximation algorithm for Girth on weighted graphs [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]. Roughly, this algorithm applies a same procedure to every vertex of the graph. In order to derive the approximation factor of their algorithm, the authors in [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF] were considering a run that takes as entry some vertex on a shortest cycle. This is in contrast with the classical algorithm from Itai and Rodeh on unweighted graphs [START_REF] Itai | Finding a minimum circuit in a graph[END_REF], that also offers provable guarantees on the length of the output assuming there is a shortest cycle passing close to the source (but not necessarily passing by this vertex); see [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]Lemma 2]. We revisit the analysis of the algorithm in [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF] for weighted graphs, and we prove that this algorithm also satisfies such a "closeness property".

The HBD-algorithm from [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]. Given G = (V, E, w), s ∈ V and t ≥ 0, the algorithm HBD(G, s, t) is a relaxed version of Dijkstra's single-source shortest-path algorithm. We are only interested in computing the ball of radius t around s, and so, we stop if there are no more unvisited vertices at a distance ≤ t from s. Furthermore, whenever we visit a vertex u ∈ B G (s, t), we only relax edges e = {u, v} such that dist(s, u) + w e ≤ t. Then, a cycle is detected if we already inferred that dist(s, v) ≤ t (i.e., using another neighbour of v than u). Overall, the algorithm stops as soon as it encounters a cycle, or all the vertices in B G (s, t) were visited. Assuming sorted adjacency lists, this algorithm runs in Õ(n)-time [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]. Here, an easy but important observation to be made is that, if HBD(G, s, t) detects a cycle, then this is also the case for HBD(G, s, t ), for every t ≥ t. We will use this observation implicitly throughout the rest of the paper.

Lemma 3.1 ( [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]). If HBD(G, s, t) detects a cycle, then its weight is ≤ 2t. We now complete the analysis of the HBD-algorithm in order to derive a generalization of [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF]Lemma 2] to weighted graphs. Assuming no cycle has been detected, we first gain more insights on the structure of the ball of radius t centered at s. Lemma 3.2. If HBD(G, s, t) does not detect a cycle then, for any v ∈ B G (s, t), there exists a unique sv-path of weight ≤ t.

Proof. Since we did not detect a cycle, we relaxed the edges of all the paths of weight ≤ t between s and the other vertices of G. The result now follows, since the (a) HBD(G, s, t)

1: for all v ∈ V do 2: d(v) ← ∞ 3: π(v) ← N IL 4: d(s) ← 0; Q ← {s} 5: while Q = ∅ do 6: u ← Extract-min(Q) 7: Controlled-Relax(u, t) (b) Controlled-Relax(u, t) 1: Qu ← sorted adj. list 2: uv ← Extract-min(Qu) 3: while d(u) + wuv ≤ t do 4: RelaxOrStop(u, v) 5: uv ← Extract-min(Qu) (c) RelaxOrStop(u, v) 1: if d(v) = ∞ then 2:
return a cycle and stop 3: else 4:

d(v) ← d(u) + wuv 5: Q ← Q ∪ {v}
edges that we relaxed during the algorithm induce a spanning tree of B G (s, t).

Based on Lemma 3.2, we state some bounds on the weight of the cycle detected using HBD. In particular, Corollary 3.4 will play a key role in the analysis of our algorithms.

Corollary 3.3. Given G = (V, E, w), let s ∈ V and let C be a cycle. The minimum t 0 such that HBD(G, s, t 0 ) detects a cycle satisfies t 0 ≤ dist(s, C) + w(C).

Proof. Fix x, y ∈ V (C) and partition the cycle C into the two xy-paths P 1 , P 2 . By the contrapositive of Lemma 3.2, a cycle is detected if t ≥ min{dist(s, x), dist(s, y)} + max{w(P 1 ), w(P 2 )}. Indeed, in this situation there exist two different paths of length ≤ t between s and one of x or y. In particular, set dist(s, x) = dist(s, C) and let y ∈ V (C) \ {x} be arbitrary. We have

t 0 ≤ dist(s, C) + max{w(P 1 ), w(P 2 )} ≤ dist(s, C) + w(C). Corollary 3.4. Given G = (V, E, w), let s ∈ V and let C be a cycle. Assume the existence of a vertex x ∈ V (C) such that max v∈V (C) dist C (x, v) ≥ dist G (s, x) > 0.
Then, the minimum t 0 such that HBD(G, s, t 0 ) detects a cycle satisfies t 0 ≤ w(C).

s x u y v z Proof. Let B x = {v ∈ V (C) | dist C (x, v) < dist G (x, s)}. Since we assume that we have max v∈V (C) dist C (x, v) ≥ dist G (x, s), B x = V (C). Hence there exist uy, vz ∈ E(C) distinct such that u, v ∈ B x but y, z / ∈ B x . W.l.o.g. dist C (x, y) ≤ dist C (x, z
). We can bipartition E(C) in two edge-disjoint xy-paths P 1 and P 2 , with P 1 being the xy-subpath passing by vz (and so, P 2 is the other xy-subpath passing by uy). Note that it implies dist C (x, y) = w(P 2 ) ≤ w(C)/2. Then, by Lemma 3.2 we have t 0 ≤ dist G (s, x) + max{w(P 1 ), w(P 2 )} = dist G (s, x) + w(P 1 ) ≤ dist C (x, y) + w(P 1 ) = w(P 2 ) + w(P 1 ) = w(C).

Subquadratic-time approximation.

We are now ready to present the main result in this section:

Theorem 1.1. For every G = (V, E, w) with edge-weights in {1, . . . , M }, we can compute a deterministic 2-approximation for Girth in time Õ(n 5/3 polylogM + m).

Proof. We analyse the following Subquadratic-Approx algorithm:

The algorithm starts precomputing a set S ⊆ V and the open balls (B S (v)) v∈V as described in Proposition 2.1. This takes time Õ(n 5/3 ), plus an additional preprocessing time in Õ(m) for sorting the adjacency lists. Then, we process the vertices in S and those in V \ S separately: For every s ∈ S, we compute the smallest t s ∈ [3; M n] such that HBD(G, s, t s ) detects a cycle by using a dichotomic search (procedure

G. DUCOFFE (a) Approx-Girth(G, s, M ) 1: Find the minimum t ∈ [3; M • |V (G)|]
such that: HBD(G, s, t) detects a cycle.

2: Let Cs be the shortest cycle we so computed. 3: return Cs. Let G v be induced by BS(v).

7:

Cv ← Approx-Girth(G v , v, M ) 8: 9: return a shortest cycle in {Cv | v ∈ V }.
Approx-Girth(G, s, M )). We store the cycle C s outputted by HBD(G, s, t s ). Since each test we perform during the dichotomic search consists in a call to the HBD-algorithm, this takes time Õ(n log M ) per vertex in S, and so, Õ(n|S| log M ) = Õ(n for ordering the adjacency lists. We apply the same procedure as for the vertices in S but, we restrict ourselves to the ball B S (v). That is, we call Approx-Girth(G v , v, M ), and we denote by C v the cycle outputted by this algorithm (in the case G v is not acyclic). Since we restrict ourselves to a subgraph of order O(n 1/3 ), this algorithm takes total time Õ(n

• (n 2/3 + n 1/3 log M )) = Õ(n 5/3 log M ). Let C ∈ {C v | v ∈ V } be of minimum weight.
We claim that w(C) is a 2approximation of the girth of G, that will end proving the theorem. In order to prove this claim, we apply the following case analysis to some arbitrary shortest cycle

C 0 of G. If V (C 0 ) ∩ S = ∅ then,
) ≤ 2w(C 0 ) if V (C 0 ) ∩ S = ∅.
From now on we assume V (C 0 ) ∩ S = ∅. Let v ∈ V (C 0 ) be arbitrary. There are two subcases:

• If V (C 0 ) ⊆ B S (v) then, C 0 is also a cycle in G v . Moreover by Corollary 3.3 applied for dist(v, C 0 ) = 0, the smallest t v such that HBD(G v , v, t v ) detects a cycle satisfies t v ≤ w(C 0 ). By Lemma 3.1, w(C) ≤ w(C v ) ≤ 2w(C 0 ). • Otherwise V (C 0 ) ⊆ B S (v)
. This implies that we have:

max u∈V (C0) dist C0 (u, v) ≥ max u∈V (C0) dist G (u, v) ≥ dist G (v, S) > 0.
Furthermore, let s ∈ S minimize dist G (s, v). Then, by Corollary 3.4, the smallest t s such that HBD(G, s, t s ) detects a cycle satisfies t s ≤ w(C 0 ). As a result, by Lemma 3.1:

w(C) ≤ w(C s ) ≤ 2w(C 0 ).
Summarizing, w(C) ≤ 2w(C 0 ) in all the cases. 4. Generalization to unbounded weights. This section is devoted to the proof of Theorem 1.2. We divide it into two parts. In Section 4.1 we present a polynomial-factor approximation of the girth in subquadratic time. This part is new compared to [START_REF] Roditty | Approximating the girth[END_REF] and the techniques used are interesting in their own right. Then, based on a clever technique from [START_REF] Roditty | Approximating the girth[END_REF], we end up refining this rough estimate of the girth until we obtain a constant-factor approximation (Section 4.2).

Throughout this section, we will use the main result of Roditty and Tov as a subroutine:

Theorem 4.1 ([16]).

For every G = (V, E, w) with arbitrary non-negative edge-weights, we can compute a (4/3 + ε)-approximation for Girth in time Õ(n 2 /ε).

4.1.

A polynomial-factor approximation. For simplicity, we first reduce the general case of graphs with non-negative weights to the subcase of graphs with positive weights. The proof is quite similar, but simpler, to the one of Proposition 4.3.

Lemma 4.2. Assume there exists an T (n, m)-time α-approximation algorithm for Girth for graphs with positive edge-weights, where T (n, m) = Ω(m). Then, there also exists an O(T (n, m))-time α-approximation algorithm for Girth for graphs with non-negative edge-weights.

Proof. Let G = (V, E, w) with non-negative real edge-weights, and let E 0 = {e ∈ E | w e = 0}. If the (unweighted) graph G 0 := (V, E 0 ) contains a cycle C, then w(C) = 0 is minimized and we can output C. Otherwise, G 0 is a forest, and let V 1 , V 2 , . . . , V p be its connected components. We consider the following three cases:

1. First we scan all the edges in E \ E 0 in order to find, for any component V i , the minimum weight of an edge with its two ends in V i (if any). It takes time O(m). Furthermore, note that given e ∈ E \ E 0 with its two ends in V i , there is a cycle of weight exactly w e . Let C 0 be the minimum-weight cycle we so computed during this step. 2. In the same way, we can easily find a cycle C 1 of minimum weight that only intersects two components: for that, we scan all the edges in E \ E 0 in order to find, for any two distinct V i , V j , the at most two edges of minimum-weight with one end in V i and the other end in V j . It takes time O(m). 3. We are now left with approximating the short cycles that intersect at least three components of G 0 . For that, let G be obtained from G by contracting each component V j into one vertex; for every distinct V i , V j , if there exists an edge e ∈ E ∩ (V i × V j ) then, we choose e minimizing w e and we set w vivj = w e in G . We observe that if there exists a shortest cycle C of G that intersects at least three components V j then, C ∩ V i is either empty or induces a path in G 0 [V i ] for every i (otherwise, there would be two vertices in V i that are connected in C by two subpaths of positive weight, and so, we could obtain a cycle of smaller weight than C by replacing any of these subpaths with any path in G 0 [V i ]). In particular, it corresponds to C a cycle C in G such that w(C ) ≤ w(C). Conversely, to any cycle C in G, it corresponds a cycle C in G such that w(C) ≤ w(C ) (obtained by uncontracting the connected components of G 0 ). Let C 2 be a cycle of weight at most α times the girth of G , and let C 2 be a corresponding cycle in G. Then, by outputting a cycle among C 0 , C 1 , C 2 that is of minimum weight, one obtains an α-approximation for the girth of G.

We now obtain an approximation of the girth that only depends on the order of the graph. We stress that for weighted graphs, this is already a non-trivial task.

Proposition 4.3. For every G = (V, E, w) with arbitrary positive edge-weights, we can compute an Õ(n 2/3 )-approximation for Girth in time Õ(n 5/3 + m).

Proof. Let S be as in Proposition 2.1. We show a significantly more elaborate method that uses S in order to approximate the girth. We divide this method into five main steps.

Step 1: check the small balls. For every v / ∈ S, let G v be the subgraph induced by the open ball B S (v). As before, we first estimate the girth of G v . Since this subgraph has order O(n 1/3 ), by Theorem 4.1 we can compute a constant-factor approximation for its girth in time Õ(n 2/3 ) (say, a 2-approximation). Overall, this step takes total time Õ(n 5/3 ). Furthermore, after completing this step the following property (also used in Theorem 1.1) becomes true:

Claim 1. Let C v be a shortest cycle passing through v. If w(C v ) < 2 • dist(v, S) then, we computed a cycle of weight ≤ 2w(C v ). Proof. This is trivial if v ∈ S. Otherwise, V (C v ) ⊆ B G (v, w(C v )/2) ⊆ B S (v) = V (G v )
, and so, we outputted a cycle of weight ≤ 2w(C v ) for the subgraph G v .

Step 2: partitioning into (shortest path) subtrees. Intuitively, what we try to do next is to approximate the weight of a shortest cycle passing close to S. The difference with Theorem 1.1 is that we cannot use directly the algorithm of Roditty and Tov for that. Indeed, their algorithm has some global steps (e.g., the approximate computation of the girth of some sparse spanner) that we currently do not know how to do in subquadratic time. So, we need to find some new techniques. Specifically, we partition the vertex-set V into shortest-path subtrees (T s ) s∈S such that, for every s ∈ S and v ∈ V (T s ) we have dist(v, s) = dist(v, S). As noted, e.g., in [START_REF] Thorup | Approximate distance oracles[END_REF], a simple way to do that is to add a dummy vertex x S / ∈ V , edges sx S for every s ∈ S with weight 0, then to compute a shortest-path tree rooted at x S in time Õ(m). See Fig. 3 for an example. In what follows, we show how to use this tree structure in order to compute short cycles. Fig. 3: An example of Step 2. The two vertices in S are drawn as rectangles.

Step 3: finding short cycles in a subtree. Let s ∈ S be fixed. Informally, we try to estimate the weight of a shortest cycle in V (T s ). Note that every such a cycle has an edge that is not contained in T s . So, we consider all the edges e = uv such that u, v ∈ V (T s ) but e / ∈ E(T s ). Adding this edge in T s closes a cycle. Let C e,s be an (unknown) shortest cycle passing by e and contained in V (T s ). We output dist(s, u) + w e + dist(v, s) as a rough estimate of w(C e,s ). Indeed, the latter is a straightforward upper-bound on w(C e,s ), and this bound is reached if s ∈ {u, v}. Overall, this step takes total time O(m).

Claim 2. Let C * s be a shortest cycle contained in V (T s ). After Steps 1-3, we computed a cycle of weight ≤ 2w(C * s ). Proof. Let e = uv ∈ E(C * s ) \ E(T s ). We also define C u , C v shortest cycles passing by u and v, respectively. By Claim 1, either we computed at Step 1 a cycle of

weight ≤ 2w(C u ) ≤ 2w(C * s ) (a cycle of weight ≤ 2w(C v )) ≤ 2w(C * s ), resp.), or we know for sure that w(C * s ) ≥ w(C u ) ≥ 2dist(u, S) = 2dist(u, s) (w(C * s ) ≥ w(C v ) ≥ 2dist(v, S) = 2dist(v, s), resp.). In the latter case, dist(s, u) + w e + dist(v, s) ≤ w(C * s )/2 + w e + w(C * s )/2 ≤ 2w(C * s ) is a 2-approximation of w(C * s ).
Step 4: finding short cycles in two subtrees. We now want to estimate the weight of a shortest cycle in V (T s ) ∪ V (T s ), for some distinct s, s ∈ S. We only need to consider the case where this cycle must contain two edges e, e with an end in V (T s ) and the other end in V (T s ) (all other cases have already been considered at Step 3).

1. We scan all the edges e = uv ∈ E such that u and v are not in a same subtree. Let s u , s v ∈ S such that u ∈ V (T su ), v ∈ V (T sv ). We set (e) = dist(s u , u) + w e + dist(v, s v ). 2. Group all these above edges with their two ends in the same two subtrees.

It takes time

O(m + |S|) = O(m + n 2/3 )
V (T s ) ∪ V (T s ). After Steps 1-4, we computed a cycle of weight ≤ 3w(C * s,s ). Proof. If either V (C * s,s ) ⊆ V (T s ) or V (C * s,s ) ⊆ V (T s ) then, we are done by Claim 2. Otherwise, let e = uv , e = vu ∈ E(s, s ) ∩ E(C * s,s ) such that u, v ∈ V (T s ) and u , v ∈ V (T s ).
Choosing the uv-path in T s and the u v -path in T s , one obtains that w(C * s,s ) ≤ (e) + (e ). Furthermore, let C u be a shortest cycle passing by u. By Claim 1, either we computed at Step 1 a cycle of weight ≤ 2w(C u ) ≤ 2w(C * s,s ), or we know for sure that w(C * s,s ) ≥ w(C u ) ≥ 2dist(u, S) = 2dist(u, s). We obtain similar results for v, u , v . As a result, and unless we found a better estimate of the girth during Step 1, we have (e) + (e ) ≤ 2w(C * s,s ) + w e + w e ≤ 3w(C * s,s ).

Step 5: the general case. We end up defining a weighted graph H S = (S, E S , w S ), where E S = {ss | E(s, s ) = ∅}, and for every ss ∈ E S :

w S ss = min e∈E(s,s ) (e) = min uv∈E(s,s ) dist(s, u) + w uv + dist(v, s ).
Roughly, w S ss is the smallest weight of an ss -path with one edge in E(s, s ). We can construct H S simply by scanning all the sets E(s, s ) (computed during Step 4). Overall, since the sets E(s, s ) partition the edges of G, this takes total time O(m+|S|) = O(m+n 2/3 ). Furthermore, by Theorem 4.1 we can compute a constantfactor approximation of the girth of H S in time Õ(|S| 2 ) = Õ(n 4/3 ). The graph H S is not a subgraph of G. However, given a cycle C H for H S , we can compute a cycle C * H of G as follows. For every s ∈ V (C H ) let s , s ∈ V (C H ) be its two neighbours. By construction, there exist e = uv ∈ E(s , s) and e = xy ∈ E(s, s ) such that the edges ss and ss in H S have weights dist(s , u) + w e + dist(v, s) and dist(s, x) + w e + dist(y, s ), respectively. -We may assume the edges e, e to be stored in H S so that s , s will choose the same common edge with s. -Then, we replace s by the vx-path in T s . It is important to notice that, by construction, we have w(C * H ) ≤ w(C H ). In particular, we can apply this above transformation to the (approximately shortest) cycle of H S that has been outputted by the algorithm of Roditty and Tov (Theorem 4.1).

Overall, let C min be a shortest cycle computed by the algorithm above (i.e., after Steps 1-5). In order to finish the proof, we need to show that w(C min ) is an Õ(n 2/3 )approximation of the girth of G. By Claims 2 and 3, this is the case if there exists a shortest cycle intersecting at most two subtrees T s , s ∈ S. From now on assume that any shortest cycle C 0 of G intersects at least three subtrees T s . We refer to Fig. 4 for an illustration of our proof. Write C 0 = (v 0 , v 1 , . . . , v p-1 , v 0 ) and assume w.l.o.g. v 0 , v p-1 are not contained into the same subtree T s . We partition the v i 's into the maximal subpaths P 0 , P 1 , . . . , P q-1 , q ≤ p that are contained into the vertex-set of a same subtree T s (in particular, v 0 ∈ V (P 0 ) and v p-1 ∈ V (P q-1 )). Furthermore for every j ∈ {0, 1, . . . , q -1} let s j ∈ S be such V (P j ) ⊆ V (T sj ), and let i j be the largest index such that v ij ∈ V (P j ). For instance, i q-1 = p -1 by construction. Since P 0 = P q and q ≥ 3 by the hypothesis, there exist distinct indices j 1 , j 2 such that s j1 = s j2+1 and for every j ∈ {j 1 , j 1 + 1, . . . , j 2 } the s j 's are pairwise different (indices are taken modulo q). ... Then, two cases may arise:

v s 0 0 s 1 s 2 s q-1 v i v i +1 v i v p-1 0 0 1 v i +1 1 v i2 v i +1 q-2
• Case j 2 = j 1 + 1. We have:

e j1 := v ij 1 v ij 1 +1 , e j2 := v ij 2 +1 v ij 2 ∈ E(s j1 , s j2 ). Furthermore, C 0 goes by v ij 1 (by v ij 1 +1 , v ij 2 +1 , v ij 2 ,
respectively), and so, by Claim 1, either we computed a short cycle of weight ≤ 2w(C 0 ) during Step 1, or we have:

w(C 0 ) ≥ 2•max{dist(s j1 , v ij 1 ), dist(s j1 , v ij 2 +1 ), dist(s j2 , v ij 1 +1 ), dist(s j2 , v ij 2 )}.
In the latter case, there exists a cycle of weight:

≤ dist(s j1 , v ij 1 ) + w ej 1 + dist(s j2 , v ij 1 +1 ) + dist(s j2 , v ij 2 ) + w ej 2 + dist(s j1 , v ij 2 +1 ) ≤ 3w(C 0 ) that is fully contained in V (T sj 1 ) ∪ V (T sj 2 )
. By Claim 3, we so computed a cycle of weight ≤ 9w(C 0 ) at Step 4.

• From now on let us assume j 2 = j 1 + 1. For every j we have e j := v ij v ij +1 ∈ E(s j , s j+1 ), and so, the edge s j s j+1 ∈ E S has weight no more than dist(s j , v ij )+ w ej +dist(v ij +1 , s j+1 ) in H S (indices are taken modulo q for the s j 's and modulo p for the v i 's). Furthermore, C 0 goes by v ij (by v ij +1 , respectively), and so, by Claim 1, either we computed a short cycle of weight ≤ 2w(C 0 ) during

Step 1, or we have w(C 0 ) ≥ 2 • max{dist(s j , v ij ), dist(s j+1 , v ij +1 } for every j.

In the latter case, (s j1 , s j1+1 , . . . , s j2 , s j2+1 = s j1 ) is a cycle in H S of weight:

≤ w(C 0 ) + j2 j=j1 (dist(v ij-1+1 , s j ) + dist(s j , v ij )) ≤ w(C 0 )(1 + (j 2 -j 1 + 1)) ≤ w(C 0 )|S| = Õ(n 2/3 • w(C 0 )).
Then, let C H be a cycle of H S such that w(C H ) = Õ(n 2/3 • w(C 0 )) (obtained by applying the algorithm of Roditty and Tov to H S ). As explained above, we can derive from

C H a cycle C * H of G such that w(C * H ) ≤ w(C H ) = Õ(n 2/3 • w(C 0 )).
Summarizing, we obtain an Õ(n 2/3 )-approximation of the girth by outputting a shortest cycle computed during Steps 1,3,4,5.

4.2.

Improving the approximation factor. Then, we combine Proposition 4.3 with the approach taken in Theorem 1.1:

Theorem 1.2.

For every ε > 0 and G = (V, E, w) with non-negative edgeweights, we can compute a deterministic (2 + ε)-approximation for Girth in time Õ(n 5/3 polylog1/ε + m).

Proof. We may assume that all weights are positive by Lemma 4.2. Let g * be the Õ(n 2/3 )-approximation that we computed by using Proposition 4.3. There exists some (known) constant c such that the girth of G is somewhere between g * /(cn 2/3 log n) and g * . Let i min , i max be the smallest nonnegative integers such that g * /(cn 2/3 log n) ≤ (1 + ε/2) imin and in the same way g * ≤ (1 + ε/2) imax . We have:

i max -i min = O log 1+ε/2 g * g * /(cn 2/3 log n) = O(log n/ log (1 + ε/2)) = O(log n/ε).
Let S be as in Proposition 2.1. For every v ∈ V \ S, we compute a 2-approximation of a shortest cycle in G v : the subgraph of G induced by the ball B S (v) 4 . By Theorem 4.1, it can be done in time Õ(n 2/3 ) for each v, and so, this takes total time Õ(n 5/3 ). Let T = {(1 + ε/2) i | i min ≤ i ≤ i max }. For every s ∈ S, we compute the smallest t ∈ T such that HBD(G, s, t) detects a cycle (if any). It can be done in time Õ(|S|n log |T |) = Õ(n 5/3 log 1/ε) by using a dichotomic search. Finally, let g min be the value computed by the above algorithm (with a corresponding cycle). In order to conclude we prove, with a similar case analysis as for Theorem 1.1, that the girth of G is at least g min /(2 + ε). Specifically, let us consider a shortest cycle C 0 . There are several cases:

• Assume that C 0 passes by some s ∈ S. Let i 0 be the smallest index such that w(C 0 ) ≤ (1 + ε/2) i0 . Since we have g * /(cn 2/3 log n) ≤ w(C 0 ) ≤ g * , i 0 ∈ {i min , i min + 1, . . . , i max }. Furthermore, by Corollary 3.3 applied for dist(s, C 0 ) = 0, HBD(G, s, (1 + ε/2) i0 ) detects a cycle. By Lemma 3.1, we so deduce that

g min ≤ 2(1 + ε/2) i0 ≤ 2(1 + ε/2)w(C 0 ) ≤ (2 + ε)w(C 0 ). • Otherwise, let v ∈ V \ S be contained into C 0 . We may assume that V (C 0 ) ⊆ B S (v), since otherwise C 0 is a cycle in G v
, and so, we can already conclude that g min ≤ 2w(C 0 ). In particular, we have:

max u∈V (C0) dist C0 (u, v) ≥ max u∈V (C0) dist G (u, v) ≥ dist G (v, S) > 0.
Let s ∈ S be such that dist G (v, s) = dist G (v, S). By Corollary 3.4, this implies that the smallest t s such that HBD(G, s, t s ) detects a cycle satisfies t s ≤ w(C 0 ). Therefore, we can choose as above the smallest index i 0 such that w(C 0 ) ≤ (1 + ε/2) i0 . As already noticed i 0 ∈ {i min , i min + 1, . . . , i max }, and by Corollary 3.4 we know that HBD(G, s, (1 + ε/2) i0 ) detects a cycle.

In this situation, we can conclude by Lemma 3.1 that g min ≤ 2(1 + ε/2) i0 ≤ 2(1 + ε/2)w(C 0 ) ≤ (2 + ε)w(C 0 ). Overall, the above proves as claimed g min ≤ (2 + ε)w(C 0 ).

5.

A subquadratic algorithm for dense graphs. A drawback of the algorithms in Theorems 1.1 and 1.2 is that their time complexity also depends on the number m of edges. It implies that for dense graphs with m = Θ(n 2 ) edges we do not achieve any improvement on the running time compared to [START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF][START_REF] Roditty | Approximating the girth[END_REF]. The main result of this section is that assuming sorted adjacency lists, the dependency on m can always be discarded (Theorem 1.3).

A weaker result.

We start with a sparsification lemma: Proposition 5.1. For every G = (V, E, w) with non-negative edge-weights and sorted adjacency lists, we can compute:

1. a randomized 4-approximation for Girth in expected time Õ(n 5/3 ); 2. and, for every ε > 0, a deterministic (8+ε)-approximation for Girth in time Õ(n 5/3 polylog1/ε). Roughly, we can prove Theorem 1.3 by combining this above Proposition 5.1 with a natural modification of the algorithm presented in Section 3.2.

We will need the following well-known result in graph theory: Theorem 5.2 ([4]). Every unweighted graph with order n and m ≥ 1 2 + o(1) n 3/2 edges contains a cycle of length four.

Proof of Proposition 5.1. If G has m = Õ(n 5/3 ) edges then, we can simply apply Theorem 1.2 for ε = 2 (the latter can be easily verified by scanning the adjacency lists until we read the end of it or we reach the desired upper-bound). From now on assume this is not the case and let H be induced by the 1 2 + o(1) n 3/2 edges of minimum weight in G. We claim that H can be constructed in time Õ(n 3/2 ) by using a priority queue Q. Indeed, initially we set E(H) = ∅ and for every v ∈ V we start inserting in Q the edge of minimum-weight that is incident to v. This way, we ensure that a minimum-weight edge of G \ E(H) is present in Q (recall that initially, E(H) = ∅, and so, G = G \ E(H)). Then, in order to preserve this above invariant, each time a minimum-weight edge uv is extracted from Q and added in H we insert in Q the remaining edge of minimum weight in Q u and the one in Q v (if any). -Note that in doing so, a same edge can be added in Q twice, but this has no consequence on the algorithm. -We now apply Theorem 1.2 for ε = ε/4 to H, and we so obtain a cycle C that is a (2 + ε/4)-approximation of the girth of H. We claim that w(C) is also a (8 + ε)-approximation of the girth of G. In order to prove this claim, we need to consider two different cases:

• Assume there exists a shortest cycle C 0 of G such that E(C 0 ) ⊆ E(H). By Theorem 1.2, w(C) ≤ (2 + ε/4)w(C 0 ) < (8 + ε)w(C 0 ). • Otherwise, any shortest cycle C 0 of G has at least one edge that is not contained in H. Since edges are added by increasing weights, this implies that every shortest cycle contains an edge of weight at least w max , where w max denotes the maximum-weight of an edge in H. In particular, the girth of G is at least w max . Furthermore, since H has enough edges by construction, by Theorem 5.2 it contains a cycle of four vertices; the latter has weight at most 4w max . As a result, w(C) ≤ (2 + ε/4) • 4w max = (8 + ε)w max ≤ (8 + ε)w(C 0 ). The above proves the claim, and so, the deterministic version of the result. In order to obtain a randomized 4-approximation, it suffices to pick ε ≤ 2 and to output any cycle C of H with four vertices (then, we output any of C, C that has minimum weight). Up to some constant multiplicative increase of the number of edges to add in H, this can be done by using a randomized algorithm of Yuster and Zwick that runs in expected linear time [START_REF] Yuster | Finding even cycles even faster[END_REF]Theorem 2.9]. Note that this is the only source of randomness in the algorithm.

We recall that any unweighted graph with O(n 1+ 1 ) edges contains a cycle of length at most 2 . We could use this density result instead of Theorem 5.2. In doing so, we could use a much sparser subgraph H in the proof of Proposition 5.1. However, our algorithm would still run in time Õ(n 5/3 ) because the bottleneck is our call to the algorithm of Theorem 1.2.

The algorithm.

We combine Proposition 5.1 with the approach taken in Theorem 1.2, as follows:

Theorem 1.3. Let G = (V, E, w) have sorted adjacency lists.

1. If all edge-weights are in {1, . . . , M } then, we can compute a deterministic 4-approximation for Girth in time Õ(n 5/3 polylogM ). 2. If all edge-weights are non-negative then, we can compute a randomized 4approximation for Girth in time Õ(n 5/3 ). For every ε > 0, we can also compute a deterministic (4+ε)-approximation for Girth in time Õ(n 5/3 polylog1/ε). Proof. It suffices to prove the result for graphs with non-negative edge-weights and ε > 0 arbitrary. To see that, let us consider any graph G with all edge-weights in {1, 2, . . . , M }. If we take G as the input of our deterministic algorithm for graphs with non-negative edge-weights, setting ε = 1 M (n+1) , then, the cycle C of G that is outputted by the algorithm has total integer weight strictly upper-bounded by 1/ε. In particular, w(C) is in fact a 4-approximation of the girth of G. Thus, from now on we will only consider the more general case of graphs G with non-negative edge-weights.

Let ε > 0 be fixed. The randomized version of the theorem was proved in Proposition 5.1. For proving the deterministic version, we start computing a c-approximation g * of the girth of G, for some universal constant c > 4. By Proposition 5.1, it can be done in time Õ(n 5/3 ). Observe that the girth of G is somewhere between g * /c and g * . Now, define η = ε/6. Let i min , i max be the smallest nonnegative integers such that g * /c ≤ (1 + η) imin and in the same way 5g * ≤ (1 + η) imax . We have i max -i min = O(1/ log (1 + η)) = O(1/ε). Furthermore, let

T = {(1 + η) i | i min ≤ i ≤ i max }.
The remaining of the algorithm is essentially the same as for Theorem 1.2, except that we avoid the costly computation of the induced subgraphs G v . Specifically, our processing of the vertices in the set S (given by Proposition 2.1) remains unchanged. However, for every v ∈ V \ S, we compute the smallest t ∈ T such that t < dist G (v, S) and HBD(G, s, t) detects a cycle (if any). In doing so, we can only visit the vertices in B S (v), and so, the total running time for processing v is upper-bounded by Õ(|B S (v)|polylogM ), that is in Õ(n 1/3 polylogM ). Overall, this algorithm runs in total time Õ(n 5/3 log T ), that is in Õ(n 5/3 log 1/ε).

Let C ∈ {C v | v ∈ V } be of minimum weight amongst all the cycles computed by the algorithm. We claim that w(C) is a (4 + ε)-approximation of the girth of G. In order to prove this claim, let C 0 be a shortest cycle of G. There are two cases.

• Assume there exists a vertex s ∈ V (C 0 ) ∩ S. Then, w(C) ≤ w(C s ) ≤ 2(1 + η)w(C 0 ) < (4 + ε)w(C 0 ) (this is a similar proof as for Theorem 1.2). • Thus, from now on we assume V (C 0 ) ∩ S = ∅. Let v ∈ V (C 0 ) be arbitrary.

-Assume first w(C 0 ) < dist G (v, S)/(1 + η). By Corollary 3.3 applied for dist G (v, C 0 ) = 0, the smallest t v such that HBD(G, v, t v ) detects a cycle satisfies t v ≤ w(C 0 ). In particular, the smallest t v ∈ T such that HBD(G, v, t v ) detects a cycle satisfies t v ≤ (1 + η)w(C 0 ) < dist G (v, S). By Lemma 3.1, w(C) ≤ w(C v ) ≤ 2(1 + η)w(C 0 ) < (4 + ε)w(C 0 ). -Otherwise w(C 0 ) ≥ dist G (v, S)/(1 + η). Let s ∈ S minimize dist G (s, v).

Then, by Corollary 3.3, the smallest t s such that HBD(G, s, t s ) detects a cycle satisfies:

t s ≤ dist G (s, v) + w(C 0 ) = dist G (v, S) + w(C 0 ) ≤ (2 + η)w(C 0 ).
In particular, the smallest t s ∈ T such that HBD(G, s, t s ) detects a cycle satisfies:

t s ≤ (1 + η)t s ≤ (2 + 2η + η 2 )w(C 0 ) ≤ (2 + 3η)w(C 0 ).
As a result, by Lemma 3.1 w(C) ≤ w(C s ) ≤ (4 + 6η)w(C 0 ) ≤ (4 + ε)w(C 0 ). Summarizing, w(C) ≤ (4 + ε)w(C 0 ) in all the cases.

6. Open problems. The most pressing question is whether we can achieve a 4/3-approximation for the girth in subquadratic time. If it is not the case then, what is the best approximation factor we can get in subquadratic time? We note that in [START_REF]Subquadratic time approximation algorithms for the girth[END_REF], Roditty and Vassilevska Williams conjectured that we cannot achieve a (2 -ε)-approximation already for unweighted graphs 5 . If their conjecture is true then, this would imply our algorithm is essentially optimal (at least for the non-dense graphs with O(n 2-ε ) edges). However, for the dense graphs with sorted adjacency lists, we left open whether a better approximation-factor than 4 can be obtained in o(n 2 )-time. Finally, another interesting question is whether a constant-approximation for the girth can be computed in quasi linear time. We recall that this is wide open even for unweighted graphs [START_REF] Dahlgaard | New subquadratic approximation algorithms for the girth[END_REF].

( b ) 1 : 2 : 3 : 4 : 5 :

 b12345 Subquadratic-Approx(G, M ) Let S and (BS(v))v∈V be as in Prop. 2.1. for all s ∈ S do Cs ← Approx-Girth(G, s, M ) for all v / ∈ S do 6:

Fig. 4 :

 4 Fig. 4: Step 5 of Proposition 4.3.

  5/3 log M ) in total. We now consider the vertices v ∈ V \ S sequentially. Let G v be the subgraph of G induced by the open ball B S (v). By Lemma 2.4, this subgraph can be computed in time Õ(|B S (v)| 2 ) = Õ(n 2/3 ) -assuming a preprocessing of the graph in time O(m)

  by using, say, a linear-time sorting algorithm. 3. Finally, for every distinct s, s ∈ S, let E(s, s ) contain all the edges with one end in T s and the other end in T

s . If |E(s, s )| ≥ 2 then, we pick e, e minimizing (•) and we output (e) + (e ). Overall, since the sets E(s, s ) partition the edges of G, this last phase also takes time O(m). Claim 3. Let s, s ∈ S be distinct and let C * s,s be a shortest cycle contained in

There is a subtle difference between our approach for weighted graphs and the one formerly applied to unweighted graphs. Indeed, we need to consider all edges in the subgraphs that are induced by some small balls in the graph, that might include some large-weight edges not on any shortestpath in G. For unweighted graphs[START_REF] Lingas | Efficient approximation algorithms for shortest cycles in undirected graphs[END_REF][START_REF] Roditty | Minimum weight cycles and triangles: Equivalences and algorithms[END_REF], they mostly consider edges on some shortest-paths in G between a pre-defined vertex and the other vertices in the ball.

Throughout this paper, we call an adjacency list sorted if it is sorted by edge-weight, and ordered if it is sorted by neighbour index. See also Sec. 2.

In fact, this is already done in the proof of Proposition 4.3, but we restate it here for completeness of the method.

Acknowledgements. This work was supported by a grant of Romanian Ministry of Research and Innovation CCCDI-UEFISCDI. project no. 17PCCDI/2018.