J Aumont

BLIND MD-MC COMPONENT SEPARATION FOR POLARIZED OBSERVATIONS OF THE CMB WITH THE EM ALGORITHM

We present the PolEMICA 1 (Polarized Expectation-Maximization Independent Component Analysis) algorithm which is an extension to polarization of the SMICA 2 temperature component separation method. This algorithm allows us to estimate blindly in harmonic space multiple physical components from multi-detectors polarized sky maps. Assuming a linear noisy mixture of components we are able to reconstruct jointly the electromagnetic spectra of the components for each mode T , E and B, as well as the temperature and polarization spatial power spectra, T T , EE, BB, T E, T B and EB for each of the physical components and for the noise on each of the detectors. This has been tested using full sky simulations of the Planck satellite polarized channels for a 14-months nominal mission assuming a simple linear sky model including CMB, and optionally Galactic synchrotron and dust emissions.

Introduction

Mapping the Cosmic Microwave Background (CMB) polarization is one of the major challenges of future missions in observational cosmology. CMB polarization is linear and therefore can be described by the first three Stokes parameters I, Q and U which are generally combined to produce three fields (modes), T , E and B. The polarization of the CMB photons carries extra physical informations that are not accessible by the study of the temperature anisotropies. Therefore its measurement helps breaking down the degeneracies on cosmological parameters as encounter with temperature anisotropies measurements only. Furthermore, the study of the CMB polarization is also a fundamental tool to estimate the energy scale of inflation.

However, CMB polarization is several orders of magnitude weaker than the temperature signal and therefore, its detection needs an efficient separation between the CMB and the astrophysical foregrounds which are expected to be significantly polarized.

A direct subtraction of these foreground contributions on the CMB data will require an accurate knowledge of their spatial distributions and of their electromagnetic spectra. But these latter are not yet well characterized in polarization.

To try to overcome the above limitations, a great amount of work has been dedicated to design and implement algorithms for component separation which can discriminate between CMB and foregrounds. We present here the PolEMICA (Polarized Expectation-Maximization Independent Component Analysis) algorithm which is an extension of the Spectral Matching Independent Component Analysis (SMICA) 2 which has been developed to consider both a fully blind analysis for which no prior is assumed and a semi-blind analysis incorporating previous physical knowledge on the astrophysical components. This extension allows to estimate jointly the temperature and polarization parameters from a set of multi-frequencies I, Q and U sky maps.

Model of the microwave and sub-mm sky

To perform the separation between CMB and the astrophysical foregrounds, the diversity of the electromagnetic spectra and of the spatial spectra of the different components is generally used. Observations from a multi-band instrument, for the Stokes parameters I, Q and U , can be modeled as a linear combination of multiple physical components leading to what is called a Multi-Detectors Multi-Components (MD-MC) modeling.

Assuming an experiment with n ν detector-bands at frequencies ν i and n c physical components in the data, working in the spherical harmonics space, we can model the observed sky for X = {T, E, B}, for each frequency band and for each {ℓ, m}

y ν,X ℓm = nc c=1 A ν,X c s c,X ℓm + n ν,X ℓm (1)
where y ν,X ℓm is a vector of size (3

•n ν •n ℓ •n m ) containing the observed data, s c,X ℓm is a (3•n c •n ℓ •n m ) vector describing each component template and n ν,X
ℓm is a vector of the same size than y ν,X ℓm accounting for the noise. A ν,X c is the mixing matrix containing the electromagnetic behaviour of each component and is of size (3

• n ν ) × (3 • n c )
The aim of the component separation algorithm presented in here is to extract A ν,X c , s c,X ℓm and n ν,X ℓm from the y ν,X ℓm sky observations.

A MD-MC component separation method for polarization

To reduce the number of unknown parameters in the model described by equation ( 1), it is interesting to rewrite this equation in terms of the temperature and polarization auto and cross power spectra and to bin them over ℓ ranges.

R y (b) = AR s (b)A T + R n (b) (2)
where R y (b) and

R n (b) are (n ν • 3) × (n ν • 3) matrices and R s (b) is a (n c • 3) × (n c • 3) matrix.
We assume that the physical components in the data are statistically independent and uncorrelated and that the noise is uncorrelated between channels. To estimate the above parameters from the data we have extended to the case of polarized data the spectral matching algorithm developed in SMICA 2 for temperature only. The key issue of this method is to estimate these parameters, or some of them (for a semi-blind analysis), by finding the best match between the model density matrix, R y (b), computed for the set of estimated parameters and the data density matrix Ry (b) obtained from the multi-channel data. The likelihood function is a reasonnable measure of this mismatch. We have extended this method to jointly deal with the temperature and polarization power spectra and also to estimate the T E, T B and EB cross power spectra 1 .

The maximization of the likelihood function is achieved via the Expectation-Maximization algorithm (EM) 3 . This algorithm will process iteratively from an initial value of the parameters following a sequence of parameter updates called 'EM steps'. By construction each EM step improves the spectral fit by maximizing the likelihood. For a more detailed review of the spectral matching EM algorithm used here, see 2 .

Following the MD-MC model discussed above and given an observational setup, we construct, using the HEALPix pixelization scheme 5 and in CMB temperature units, fake I, Q and U maps of the sky at each of the instrumental frequency bands. For these maps we consider three main physical components in the sky emission: CMB, thermal dust and synchrotron. Instrumental noise is modeled as white noise.

The CMB component map is randomly generated from the polarized CMB angular power spectra for a set of given cosmological parameters. In the following we have used H 0 = 71 km • s -1 • Mpc -1 , Ω b = 0.044, Ω m = 0.27, Ω Λ = 0.73 and τ = 0.17 that are the values of the cosmological concordance model according to the WMAP 1 year results 7 .

For the diffuse Galactic synchrotron emission we use the template maps in temperature and in polarization provided by 4 . Here we have chosen to use a constant spectral index equal to the mean of the spectral index map, α = -2.77, so that the simple linear model of the data holds.

In the case of the thermal dust we dispose of few observational data of the polarized diffuse emission and to date no template for this is available. Thus, we have considered a power-law model, renormalized to mimic at large angular scales the T E cross power spectrum measured by Archeops at 353 GHz 6 . I, Q and U full-sky maps are generated randomly from these power spectra. We extrapolate them to each of the frequency of interest by assuming a grey body with an emissivity of 2.

Noise maps for each channel are generated from white noise realizations normalized to the nominal level of instrumental noise for that channel.

We have performed sets of simulations of the expected Planck satellite data to intensively test the algorithm presented above. We present here results from 300 realizations considering full-sky maps at the LFI and HFI polarized channels, 30, 40 and 70 GHz for LFI and 100, 143, 217 and 353 GHz for HFI for a nominal 14-month survey. We have simulated maps at n side = 512 which permits the reconstruction of the angular power spectra up to ℓ ≃ 1500. The reconstructed spectra will be averaged over bins of size 20 in ℓ.

Results

We have applied the PolEMICA component separation algorithm to the simulations presented above. From them, we have computed the data density matrix R y and applied the algorithm. We simultaneously estimate the R s , R n and A matrices, with no priors, for temperature and polarization. To ensure the reliability of the results we have performed 10000 EM iterations and checked, for each simulation, the convergence of the EM algorithm.

We present in figure 1 the reconstructed CMB power spectra. We can see that for the T T , T E, T B and EB spectra, we are able to reconstruct the C ℓ over the full range of ℓ values that are accessible at this pixelization resolution (ℓ max ∼ 1500). The EE spectrum is recovered accurately up to ℓ ≃ 1200. For smaller angular scales, a bias appears. This bias is a pixelization problem that would occur at a larger ℓ if the resolution was higher. The BB spectrum is reconstructed up to ℓ ≃ 70. For larger ℓ, the reconstructed spectrum is residual noise arising from the fact that the convergence of the EM algorithm is slow and therefore we have not properly converged. This bias appears in our separation when the signal over noise ratio is below 10 -2 and does not affect the reconstruction of the other parameters. Even if we were able to avoid this effect, the recovered BB spectrum would be compatible with zero for ℓ > 70 thanks to the size of the error bars.

The power spectra from our input synchrotron and dust emissions are recovered with efficiency up to ℓ ≃ 1500 for T T , EE, BB, T E, T B and EB 1 . Power spectra of the noise in

temperature and in polarization are also fully reconstructed 1 . The mixing matrix A elements corresponding to CMB and dust emission are recovered efficiently, for temperature and polarization. For the synchrotron emission, mixing matrix elements corresponding to polarization are well recovered and those corresponding to temperature are biased at intermediate frequency values 1 . This bias is due tu a slight mixing up between synchrotron and CMB in temperature. It does not happen in polarization where the synchrotron dominates the CMB. This bias can be avoided by the adjunction of priors in the separation, like for example assuming an equal electromagnetic spectrum in temperature and polarization for each component 1 To evaluate the impact of foregrounds in the determination of the CMB temperature and polarization power spectra we have compared the results of the presented analysis to those on simulations that contain only CMB and noise. In the presence of foregrounds, the error bars on the reconstruction of the CMB power spectra are increased by at least a factor of two both in temperature and in polarization 1 . Therefore, although the foreground contribution in the data can be removed, it significantly reduces the precision to which the CMB polarization signal can be extracted from the data.


R Zamoum

M Lavagna

A Crépieux

Nonsymmetrized noise in a quantum dot: Interpretation in terms of energy transfer and coherent superposition of scattering paths

We calculate the nonsymmetrized current noise in a quantum dot connected to two reservoirs by using the non-equilibrium Green function technique. We show that both the current auto-correlator (inside a single reservoir) and the current cross-correlator (between the two reservoirs) are expressed in terms of transmission amplitude and coefficient through the barriers. We identify the different energy-transfer processes involved in each contribution to the auto-correlator, and we highlight the fact that when there are several physical processes, the contribution results from a coherent superposition of scattering paths. Varying the gate and bias voltages, we discuss the profile of the differential Fano factor in light of recent experiments, and we identify the conditions for having a distinct value for the auto-correlator in the left and right reservoirs.

I. INTRODUCTION

Since the beginning of the 2000s, it has been known that to characterize finite-frequency current fluctuations in quantum conductors, one has to measure and calculate the nonsymmetrized noise, which corresponds to the emission noise at positive frequency and to the absorption noise at negative frequency 1,2 . This is related to the fact that the current operators do not commute for quantum systems 3,4 . In taking the symmetrized noise, one mixes the emission and absorption parts and the relevant information is lost. Despite the growing interest in nonsymmetrized finite-frequency (NSFF) noise in quantum systems both experimentally [5][6][7][8][9][10][11][12][13] and theoretically [14][15][START_REF] Martin | Les Houches Session LXXXI[END_REF][START_REF] Creux | [END_REF][18][19][20][21][22][23][24][25][26][27][28][29] , there is no clear and direct interpretation of the physical processes that contribute to the noise, even for non-interacting systems. Here we show that it makes sense to interpret each contribution to the NSFF auto-correlators in terms of the energy-transfer process, following the ideas developed by several authors. Indeed, it has been shown that the frequency at which the NSFF noise is evaluated corresponds to the energy provided or absorbed by the detector 14 or by the electromagnetic environment, and that current fluctuations produce radiation of photons/plasmons in a phase-coherent conductor [30][31][32][33][34][35][36][37][38][39][40][41][42] . To address this issue from a theoretical point of view, one can use either the scattering theory [43][44][START_REF] Sh | Electronic Noise and Fluctuations in Solids[END_REF][START_REF] Nazarov | Quantum Transport: Introduction to Nanoscience[END_REF] or the non-equilibrium Green function (NEGF) technique [START_REF] Jauho | [END_REF][START_REF] Haug | Quantum Kinetics in Transport and Optics of Semiconductors[END_REF] . Whereas the former method applies to non-interacting systems, the latter can be extended to interacting ones. However, the NEGF technique has been used so far only for the calculation of symmetrized noise 49 .

In this article, we present two methods to derive the noise spectrum for a quantum dot (QD) connected to two reservoirs. The first method is based on the NEGF technique and allows us to express the NSFF auto-correlators and cross-correlators in terms of the transmission amplitude and transmission coefficient through the barriers. The second method is based on a detailed analysis of all the different physical processes that contribute to the auto-correlators by emitting energy in one reservoir, paying attention to considering the coherent superposition of scattering paths when more than one process is involved. The cross-correlators cannot be obtained within the second method, but we check that for the autocorrelators the two methods lead to the same expressions. We benchmark our results with the known results existing in the literature in some given limits, notably in the non-interacting limit when the scattering theory can be used, and we discuss the charge fluctuations in the QD.

The paper is organized as follows: in Sec. II, we present the system, the model, and the details of the NSFF noise calculation within the NEGF technique, and we discuss the results. In Sec. III, we present a new method for the determination of the NSFF auto-correlators based on a careful analysis of the various scattering processes that lead to energy transfer. For an Anderson-type transmission amplitude, we identify in Sec. IV the conditions to get distinct auto-correlators in the left and right reservoirs, and we discuss the differential Fano factor profile. We conclude in Sec. V.

II. NONSYMMETRIZED NOISE

We consider a QD connected to two reservoirs described by the non-interacting single-level Anderson

Hamiltonian H = H L + H R + H T + H D , where H α = ∑ k∈α ε k c † k c k is the Hamiltonian of the left (α = L) and right (α = R) reservoirs, H T = ∑ α=L,R ∑ k∈α (V k c † k d + h.c.
) is the transfer Hamiltonian, and

H D = ε 0 d † d is the Hamiltonian of the QD. c † k (d †
) and c k (d) are the creation and annihilation operators of one electron in the reservoirs (QD). The quantities ε 0 , ε k and V k are respectively the QD energy level, the energy of an electron with momentum k in the reservoir and the transfer matrix element between the corresponding states. The spin degree of freedom can be included without any complication.

The objective is to calculate the NSFF noise defined as

S αβ (ω) = ∫ ∞ -∞ S αβ (t, 0)e -iωt dt , ( 1
)
where S αβ (t, 0) = ⟨∆ Îα (t)∆ Îβ (0)⟩ is the current correlator and ∆ Îα (t) = Îα (t) -⟨ Îα ⟩ with Îα , the current operator from the α reservoir to the central region through the α barrier given by: Îα = (ei/ )

∑ k∈α ( V k c † k d -V * k d † c k
) , and ⟨ Îα ⟩ its average value.

A. Noise calculation using the NEGF technique

Following Haug and Jauho [START_REF] Haug | Quantum Kinetics in Transport and Optics of Semiconductors[END_REF] , we first substitute the expression of the current operator in the correlator and obtain 50

S αβ (t, t ′ ) = e 2 2 ∑ k∈α,k ′ ∈β [ V k V k ′ G cd,> 1 (t, t ′ ) -V k V * k ′ G cd,> 2 (t, t ′ ) -V * k V k ′ G cd,> 3 (t, t ′ ) +V * k V * k ′ G cd,> 4 (t, t ′ ) ] -⟨ Îα ⟩⟨ Îβ ⟩ , (2)
where G cd,> i (t, t ′ ), with i = 1-4, are the greater components of the two-particle Green functions mixing c k and d operators defined as

G cd,> 1 (t, t ′ ) = -⟨c † k (t)d(t)c † k ′ (t ′ )d(t ′ )⟩ , ( 3
)
G cd,> 2 (t, t ′ ) = -⟨c † k (t)d(t)d † (t ′ )c k ′ (t ′ )⟩ , ( 4
)
G cd,> 3 (t, t ′ ) = -⟨d † (t)c k (t)c † k ′ (t ′ )d(t ′ )⟩ , ( 5
)
G cd,> 4 (t, t ′ ) = -⟨d † (t)c k (t)d † (t ′ )c k ′ (t ′ )⟩ . ( 6
)
We introduce G cd i (τ, τ ′ ) with τ > τ ′ , the contourordered (along the Keldysh contour C 51 ) counterparts of G cd,> i (t, t ′ ), as well as S αβ (τ, τ ′ ), the contour-ordered counterpart of S αβ (t, t ′ ). We then derive and solve the equations of motion for G cd i (τ, τ ′ ) in order to express them in terms of: (i) the contour-ordered oneparticle Green function for the disconnected reservoirs defined as

g k (τ, τ ′ ) = -i⟨T C c k (τ )c † k ′ (τ ′ )⟩ 0
, where T C is the contour-ordering operator, (ii) the contour-ordered one-particle Green function for the QD connected to the reservoirs, G(τ, τ ′ ) = -i⟨T C d(τ )d † (τ ′ )⟩, and (iii) the contour-ordered two-particle Green functions for the QD,

G (2) i (τ, τ ′ , τ 1 , τ 2 ), defined as G (2) 1 (τ, τ ′ , τ 1 , τ 2 ) = -⟨T C d(τ )d(τ ′ )d † (τ 1 )d † (τ 2 )⟩ , (7) G (2) 2 (τ, τ ′ , τ 1 , τ 2 ) = -⟨T C d(τ )d † (τ ′ )d(τ 1 )d † (τ 2 )⟩ , (8) G (2) 3 (τ, τ ′ , τ 1 , τ 2 ) = -⟨T C d † (τ )d(τ ′ )d(τ 1 )d † (τ 2 )⟩ , (9) G (2) 4 (τ, τ ′ , τ 1 , τ 2 ) = -⟨T C d † (τ )d † (τ ′ )d(τ 1 )d(τ 2 )⟩ . (10)
After a series of manipulations, we get

S αβ (τ, τ ′ ) = δ αβ Sα (τ, τ ′ ) + e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × dτ 1 dτ 2 [ -g k (τ 1 , τ )g k ′ (τ 2 , τ ′ )G (2) 1 (τ, τ ′ , τ 1 , τ 2 ) +g k (τ 2 , τ )g k ′ (τ ′ , τ 1 )G (2) 2 (τ, τ ′ , τ 1 , τ 2 ) -g k (τ, τ 1 )g k ′ (τ 2 , τ ′ )G (2) 3 (τ, τ ′ , τ 1 , τ 2 ) -g k (τ, τ 1 )g k ′ (τ ′ , τ 2 )G (2) 4 (τ, τ ′ , τ 1 , τ 2 ) ] -⟨ Îα ⟩⟨ Îβ ⟩ , ( 11
)
where Sα (τ,

τ ′ ) = (e 2 / 2 ) ∑ k∈α |V k | 2 [ g k (τ ′ , τ )G(τ, τ ′ ) + g k (τ, τ ′ )G(τ ′ , τ ) ] .
To go further, one needs to write and solve the equation of motion for the two-particle Green functions for the QD, which is an ambitious task. However, for a non-interacting system, the QD two-particle Green functions can be decouple into a product of two QD one-particle Green functions. We get

S αβ (τ, τ ′ ) = δ αβ Sα (τ, τ ′ ) + e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × dτ 1 dτ 2 [ -g k (τ 1 , τ )g k ′ (τ 2 , τ ′ )G(τ, τ 2 )G(τ ′ , τ 1 ) +g k (τ 2 , τ )g k ′ (τ ′ , τ 1 )G(τ, τ ′ )G(τ 1 , τ 2 ) +g k (τ, τ 1 )g k ′ (τ 2 , τ ′ )G(τ ′ , τ )G(τ 1 , τ 2 ) -g k (τ, τ 1 )g k ′ (τ ′ , τ 2 )G(τ 2 , τ )G(τ 1 , τ ′ ) ] . ( 12
)
The different terms appearing on the right-hand side of Eq. ( 12) correspond to the connected part of the noise (the last four terms being the ones where the two integrals over τ 1 and τ 2 are intertwined). The last term -⟨ Îα ⟩⟨ Îβ ⟩ appearing on the right-hand side of Eq. ( 11) is no longer present since it is exactly canceled by the disconnected part of the noise (in which the two integrals over τ 1 and τ 2 can be done separately).

Next, we perform an analytical continuation of Eq. ( 12), we substitute the one-particle Green functions for the reservoirs and the QD by their expressions given in Ref. 48 and we make a Fourier transform, assuming that all the Green functions are time translation invariant (see Appendix A for the details of the calculations). Moreover, the coupling strength between the QD and the reservoirs, Γ α (ε) = 2π|V α (ε)| 2 ρ α (ε), with ρ α (ε) the density of states in the reservoir α and V α (ε) = V k∈α , is assumed to be energy independent (exact in the wide band limit). In addition, we consider symmetric coupling 52 , i.e., Γ L = Γ R = Γ .

B. Results and discussion

Within these assumptions, we obtain the following expression for the NSFF noise

S αβ (ω) = e 2 h ∑ γδ ∫ ∞ -∞ dεM γδ αβ (ε, ω)f e γ (ε)f h δ (ε -ω) , ( 13
)
where

f e γ (ε) is the Fermi-Dirac distribution function, f h δ (ε) = 1 -f e δ (ε)
, and where the matrix elements M γδ αβ (ε, ω) are listed in Table I. They are expressed in terms of the transmission amplitude t(ε) = iΓG r (ε), with G r (ε) the QD retarded Green function, and of the transmission coefficient T (ε) = t(ε)t * (ε) through the barriers. The NSFF noise is composed of four contributions, each of which is given by the integral over the energy ε of the matrix elements M γδ αβ (ε, ω) weighted by the product of the electron distribution function f e γ (ε) and hole distribution function f h δ (ε -hω). When α = β, Eq. ( 13) gives the expressions of the NSFF auto-correlators S LL (ω) and S RR (ω); when α ̸ = β, it gives the expressions for the NSFF cross-correlators S LR (ω) and S RL (ω). The calculations presented here apply for a non-interacting QD. However, Eq. ( 13) holds even in the presence of Coulomb interactions in the QD provided that the QD two-particles Green function can be decoupled into a product of two QD one-particle Green functions as discussed above (equivalent to neglecting the vertex corrections). The effects of the interactions will then be entirely contained in the transmission amplitude t(ε) and the coefficient T (ε).

Since S αβ (ω) = S * βα (ω), the sum of S αβ (ω) over the indexes α, β of the two reservoirs, is a real quantity equal to

∑ αβ S αβ (ω) = e 2 h ∫ ∞ -∞ dε|t(ε -ω) -t(ε)| 2 × ∑ γδ f e γ (ε)f h δ (ε -ω) . ( 14
)
The above double sum is related to the charge fluctuations 21,44,53 in the QD as shown in Appendix B. Indeed, for an Anderson-type transmission amplitude, i.e., t(ε) = iΓ/(ε -ε 0 + iΓ), Eq. ( 14) leads to

∑ αβ S αβ (ω) = ω 2 S Q (ω), with S Q (ω) = ∫ dte -iωt ⟨∆ Q(t)∆ Q(0)
⟩, the noise associated with the fluctuations of the charge Q = ed † d in the QD. At zerofrequency or for an energy-independent transmission amplitude, ∑ αβ S αβ (ω) vanishes. This sum is non-zero only when t(ε) acquires an energy dependence, as it is the case for example when the system is coupled to an electromagnetic environment 54 .

It is important to stress that our result for S LL (ω) differs from the expression of the NSFF noise given in Ref. 46 in which the term |t(ε) -t(ε -ω)| 2 is absent. However, when we symmetrize Eq. ( 13) with respect to the frequency, we get an expression that coincides exactly with the result obtained by Büttiker using scattering theory 43 in which the emblematic term |t(ε) -t(ε -ω)| 2 is also present. Moreover, at zero temperature, our result coincides with the expressions obtained by Hammer and Belzig in Ref. 24, and at equilibrium, the fluctuation-dissipation theorem holds since we get S(ω) = 2 ωN (ω)G(ω), with N (ω), the Bose-Einstein distribution function and G(ω), the ac-conductance (the reservoir indexes can be removed in that limit). This confirms the validity of our calculations. We have also checked that by using scattering theory (non-interacting limit), we get an expression for the NSFF noise in terms of the matrix elements M γδ αβ (ε, ω), identical to that obtained in Eq. ( 13) using the NEGF technique.

M γδ αβ (ε, ω) γ = δ = L γ = δ = R γ = L, δ = R γ = R, δ = L α = L T (ε)T (ε -ω) T (ε)T (ε -ω) T (ε -ω)[1 -T (ε)] T (ε)[1 -T (ε -ω)] β = L +|t(ε) -t(ε -ω)| 2 α = R T (ε)T (ε -ω) T (ε)T (ε -ω) T (ε)[1 -T (ε -ω)] T (ε -ω)[1 -T (ε)] β = R +|t(ε) -t(ε -ω)| 2 α = L t(ε)t * (ε -ω) t * (ε)t(ε -ω) t(ε)t(ε -ω)[1 -t * (ε)] t * (ε)t * (ε -ω)[1 -t(ε)] β = R ×[(1 -t * (ε))(1 -t(ε -ω)) -1] ×[(1 -t(ε))(1 -t * (ε -ω)) -1] ×[1 -t * (ε -ω)] ×[1 -t(ε -ω)] α = R t * (ε)t(ε -ω) t(ε)t * (ε -ω) t * (ε)t * (ε -ω)[1 -t(ε)] t(ε)t(ε -ω)[1 -t * (ε)] β = L ×[(1 -t(ε))(1 -t * (ε -ω)) -1] ×[(1 -t * (ε))(1 -t(ε -ω)) -1] ×[1 -t(ε -ω)] ×[1 -t * (ε -ω)]

III. COHERENT SUPERPOSITION OF SCATTERING PATHS

Let us now proceed on to the second method that we develop to calculate the NSFF auto-correlators, i.e., S LL (ω) and S RR (ω), which correspond at positive frequency to the emission noises in the left and right reservoir, respectively 1,2 . It consists in identifying the physical processes involved in the generation of current noises. For this, one must go back to the definition of the noise given above, stating that it is the Fourier transform of a two-particle correlator, say, for instance, S LL (t, 0) = ⟨∆ ÎL (t)∆ ÎL (0)⟩ for the auto-correlator in the left reservoir. From this and due to charge and energy conservation, one can see that S LL (ω) corresponds to the transition probability from an initial state formed by creating a pair of one electron with energy ε and one hole with energy ε -ω in either the left or the right reservoir, to a final state where the electron-hole pair is located in the left reservoir and then recombines emitting energy ω on the left reservoir side. Fig. 1 illustrates all the possible processes along which the system transits from such an initial state to that final state. Note that in order to contribute to the noise, the physical process must allow either the electron or the hole of the electron-hole pair to experience an excursion into the QD.

We first discuss the contributions to S LL (ω) when one starts from an initial state with an electron-hole pair located in the left reservoir, i.e., proportional to f e L (ε)f h L (ε -ω). In this case, there exist three distinct processes allowing the electron or the hole to experience an excursion into the QD: in the first process, illustrated in Fig. 1(a 1 ), the hole of the initial electron-hole pair is reflected by the left barrier while its electron partner moves back and forth between the left reservoir and the QD before emitting energy ω by recombining with its hole partner in the left reservoir. The corresponding transition probability amplitude is

t 1 (ε, ω) = t(ε)r * (ε -ω).
In the second process, illustrated in Fig. 1(a 2 ), the hole of the electron-hole pair moves back and forth between the left reservoir and the QD while its electron partner is reflected by the left barrier before emitting energy ω by recombining with the hole present in the left reservoir. Its amplitude reads t 2 (ε, ω) = r(ε)t * (ε -ω). Finally in the third process, illustrated in Fig. 1(a 3 ), both the hole and the electron of the electron-hole pair move back and forth between the left reservoir and the QD before emitting energy ω by recombining together. Its amplitude is t 3 (ε, ω) = t(ε)t * (ε -ω). These three processes lead to the following contribution to the noise:

t 1 (ε, ω) + t 2 (ε, ω) + t 3 (ε, ω)
2 corresponding to the coherent superposition of the three transmission processes in question. The amplitudes rather than the probabilities have to be summed over the different processes since the wave function of the system is anti-symmetric under exchange of particles due to the Pauli principle. As a result, the processes in which electrons or holes are either transmitted or reflected are not distinguishable [START_REF] Martin | Les Houches Session LXXXI[END_REF]44 . We have checked that |t 1 (ε, ω) + t 2 (ε, ω) + t 3 (ε, ω)| 2 is identical to M LL LL (ε, ω) = T (ε)T (ε-ω)+|t(ε)-t(ε-ω)| 2 using the relations: r(ε) = 1 -t(ε) and t(ε) + t * (ε) = 2T (ε). These latter two relations hold for the non-interacting singleimpurity model with symmetric barriers. The former relation arises from the matrix relation Ŝ(ε) = 1t(ε) connecting the Ŝ matrix and the scattering matrix, whereas the latter relation corresponds to the generalized optical theorem [START_REF] Newton | Scattering Theory of Waves and Particles[END_REF] resulting from the unitarity property of the Ŝ matrix -holding when only elastic scattering of electrons occurs, as is the case here -providing that the former relation is satisfied.

The physical processes involved in the three other contributions to the noise S LL (ω) can be identified in the same way. For the contribution proportional to f e R (ε)f h R (ε -ω), one has to start from an initial state in which both the electron and the hole of the pair are in the right reservoir. There is a single process as illustrated in Fig. 1(b). Both the electron and the hole have to move across the entire structure from the right to the left reservoir through the QD before recombining to emit energy ω in the left reservoir. The latter process leads to the following contribution to the noise:

|t(ε)t * (ε -ω)| 2 , which is identical to M RR LL (ε, ω) = T (ε)T (ε -ω).
The same analysis can be carried out for the last two contributions proportional to f e L (ε)f h R (ε-ω) and f e R (ε)f h L (ε-ω) leading to the identification of processes (c) and (d) of Fig. 1 and to the expressions of M LR LL (ε, ω) and M RL LL (ε, ω).

Note that these processes describe the contributions to S LL (ω) up to any order in the coupling strength Γ. In the weak-coupling limit, the processes (a 1 ), (a 2 ), (c), and (d) are of order Γ 2 , whereas the processes (a 3 ) and (b) are of order Γ 4 . Similar physical processes can be found to explain the contributions to S RR (ω). It is not possible, however, to find such a simple picture for the NSFF crosscorrelators S LR (ω) and S RL (ω) since they are not real, and thus they are nonobservable quantities 14 .

IV. OUT-OF-EQUILIBRIUM NOISE SPECTRUM AND FANO FACTOR

To illustrate our results, we use the following exact form for the dot electron Green function in the noninteracting Anderson single-impurity model, G r (ε) = (ε -ε 0 + iΓ) -1 . This expression leads to a Lorentziantype expression for the transmission amplitude t(ε) = iΓ/(ε -ε 0 + iΓ), where we recall that Γ is the coupling strength between the QD and the reservoirs and ε 0 is the QD energy level. The auto-correlator and the cross-correlator spectrum, as well as the Fano factor defined as the ratio between the zero-frequency noise and the current, are quantities that are well discussed in the literature 14,21,24 . Here, we choose to focus on the following features: the conditions to observe distinct autocorrelators in the left and right reservoirs, and the profile of the differential Fano factor.

A. NSFF noise in left and right reservoirs

From Table I, we see that the expressions for the autocorrelators in the left and the right reservoirs are distinct. For example, in the zero-temperature limit and at positive frequency and positive bias voltage, the autocorrelators are given by

S LL (ω) = e 2 h ∫ µ L µR+ ω dεT (ε -ω) [ 1 -T (ε) ] , (15)
and

S RR (ω) = e 2 h ∫ µL µR+ ω dεT (ε) [ 1 -T (ε -ω) ] , (16)
which are non-equal when the frequency is non-zero and when the transmission coefficient is energy-dependent. Such a difference between the left and right autocorrelators is also reported in Refs. [28,39]. Its origin is the distinct energy of the carriers contributing to S LL (ω)

or to S RR (ω) when transferred through the junction (ε -ω versus ε). There is an additional condition that appears when one plots the noise spectrum: the potential profile through the junction has to be non symmetric in the sense that the dot energy should not stand in the middle of the potential barrier, i.e. ε 0 ̸ = (µ L + µ R )/2. Indeed, in Fig. 2 (in which we take ε 0 = 0), we see that when µ L + µ R ̸ = 0, the auto-correlators in the left and right reservoirs are different (compare orange, red and purple lines) and that it is only when µ L + µ R = 0, that these two quantities coincide (compare black lines). Thus, S LL (ω) differs from S RR (ω) provided that the following three conditions are fulfilled: non-zero frequency, energy dependent transmission and non-symmetric potential profile. As expected in the zero temperature limit, the emission noises S LL (ω) and S RR (ω) (at positive frequency) drop to zero for frequency higher than voltage: the system can not supply energy larger than the energy provided to it (here the voltage). The absorption noise (at negative frequency) has no such limitation. We observe that for ω < -eV , S LL (ω) and S RR (ω) converge to the same value (equal to e 2 Γ/ ), even when the above conditions meet. Finally, S LL (ω) and S RR (ω) differ from each other in the interval ω ∈ [-eV, 0[ ∪ ]0, eV ] provided that T (ε) is energy-dependent and ε 0 ̸ = (µ L + µ R )/2. In any other situations, the auto-correlators in the left and right reservoirs coincide.

B. Differential Fano factor

The differential Fano factor was introduced in recent experimental works 10 and defined as

F (V S , ω) = [dS LL /dV ] VS /[ed⟨ ÎL ⟩/dV ] V S -ω/e
. It corresponds to the ratio of the derivative of the noise with bias voltage at V = V S , to the differential conductance at V = V S -ω/e, where ω is the frequency at which the noise is measured. We plot F (V S , ω) in Fig. 3 as a function of gate energy ε 0 and bias voltage V S at two values of the frequency, ω 1 /Γ = 0.1 and ω 2 /Γ = 1. In agreement with the fact that the system cannot emit energy larger than the supplied energy eV S , we observe that F (V S , ω) is strongly reduced for bias voltages V S smaller than the frequency in absolute value (see the black horizontal band in both graphs of Fig. 3). At low frequency (Fig. 3(a)), F (V S , ω) is always smaller than 1, meaning that the noise is sub-Poissonian. At higher frequency (Fig. 3(b)), F (V S , ω) takes values higher than 1 in some regions, meaning that the noise is super-Poissonian with an upper limit for F (V S , ω) equal to 2, in agreement with Ref. 24. Such an increase of F (V S , ω) with increasing frequency has been measured in a carbon nanotube QD when placed in the Kondo regime 10 . Even if the analysis carried out here is not intended to describe the Kondo effect, it is worth noticing that this increase of F (V S , ω) with increasing frequency constitutes a general trend. At both low and high frequencies, F (V S , ω) is reduced in the bands surrounding the first bisectors, ε 0 = ±eV S /2 in the case of a symmetric profile of the chemical potentials on either sides of the QD, i. e. µ L,R = ±eV S /2. These bands correspond to a maximal conductance with a transmission close to 1. The results reported in the two graphs show similarities with what has been observed experimentally in Ref. 10 with a characteristic pattern composed of six areas of the non-zero differential Fano factor separated by narrow bands in which the differential Fano factor is strongly reduced. Experimentally in the presence of the Kondo effect, the bands surrounding the bisectors are no longer straight but become curved due to the effect of the interactions.

V. CONCLUSION

In summary, we have derived the expression of the NSFF noises in a single-level QD connected to reservoirs using the NEGF technique. Both the auto-and crosscorrelators are expressed in terms of the transmission amplitude t(ε) and coefficient T (ε). We have identified the physical processes at the origin of the contributions to the auto-correlators. We have shown that when the electronhole pair is initially present in the reservoir emitting the energy, the contributions to the noise can be interpreted in terms of a coherent superposition of three distinct processes. On the contrary, when the electron and/or the hole of the pair is initially in the non-emitting reservoir, only one type of physical process exists and contributes to the noise. We have also shown that for a non-interacting QD, the differential Fano factor as a function of gate and bias voltages presents interesting features reminiscent of the experimental measurements. The methods presented and tested here could be extended to treat many situations involving Coulomb interactions and other transmission amplitudes and coefficients, such as multiple channel systems, QDs with multiple energy levels, or quantum point contacts embedded in an electromagnetic environment.

αβ (τ, τ ′ ) = e 2 2 ∑ k∈α |V k | 2 [ g k (τ ′ , τ )G(τ, τ ′ ) +g k (τ, τ ′ )G(τ ′ , τ ) ] δ αβ , (A1) C (2) αβ (τ, τ ′ ) = - e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dτ 1 dτ 2 ×G(τ, τ 2 )g k ′ (τ 2 , τ ′ )G(τ ′ , τ 1 )g k (τ 1 , τ ) , (A2) C (3) αβ (τ, τ ′ ) = e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dτ 1 dτ 2 ×G(τ, τ ′ )g k ′ (τ ′ , τ 1 )G(τ 1 , τ 2 )g k (τ 2 , τ ) , (A3) C (4) αβ (τ, τ ′ ) = e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dτ 1 dτ 2 ×g k (τ, τ 1 )G(τ 1 , τ 2 )g k ′ (τ 2 , τ ′ )G(τ ′ , τ ) , (A4) C (5) αβ (τ, τ ′ ) = - e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dτ 1 dτ 2 ×g k (τ, τ 1 )G(τ 1 , τ ′ )g k ′ (τ ′ , τ 2 )G(τ 2 , τ ) . (A5)
Performing the analytical continuation 48 of the previous equations, we obtain S αβ (t, t

′ ) = ∑ 5 i=1 C (i) αβ (t, t ′ ) with C (1) αβ (t, t ′ ) = e 2 2 ∑ k∈α |V k | 2 [ g < k (t ′ , t)G > (t, t ′ ) +g > k (t, t ′ )G < (t ′ , t) ] δ αβ , (A6) C (2) αβ (t, t ′ ) = - e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dt 1 dt 2 × [ G r (t ′ , t 1 )g < k (t 1 , t) + G < (t ′ , t 1 )g a k (t 1 , t) ] × [ G > (t, t 2 )g a k ′ (t 2 , t ′ ) + G r (t, t 2 )g > k ′ (t 2 , t ′ ) ] , (A7) C (3) αβ (t, t ′ ) = e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 G > (t, t ′ ) dt 1 dt 2 × [ g r k ′ (t ′ , t 1 )G r (t 1 , t 2 )g < k (t 2 , t) +g r k ′ (t ′ , t 1 )G < (t 1 , t 2 )g a k (t 2 , t) +g < k ′ (t ′ , t 1 )G a (t 1 , t 2 )g a k (t 2 , t) ] , (A8) C (4) αβ (t, t ′ ) = e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 G < (t ′ , t) dt 1 dt 2 × [ g > k (t, t 1 )G a (t 1 , t 2 )g a k ′ (t 2 , t ′ ) +g r k (t, t 1 )G > (t 1 , t 2 )g a k ′ (t 2 , t ′ ) +g r k (t, t 1 )G r (t 1 , t 2 )g > k ′ (t 2 , t ′ ) ] , (A9) C (5) αβ (t, t ′ ) = - e 2 2 ∑ k∈α,k ′ ∈β |V k V k ′ | 2 dt 1 dt 2 × [ g > k (t, t 1 )G a (t 1 , t ′ ) + g r k (t, t 1 )G > (t 1 , t ′ ) ] × [ g r k ′ (t ′ , t 2 )G < (t 2 , t ′ ) + g < k ′ (t ′ , t 2 )G a (t 2 , t ′ ) ] . (A10)
Considering the Fourier transform of the Green functions in the latter expressions in the case of a time translation invariance (steady state), we get

S αβ (ω) = ∑ 5 i=1 C (i) αβ (ω) with C (1) αβ (ω) = e 2 h ∑ k∈α |V k | 2 ∫ ∞ -∞ dε [ g < k (ε)G > (ε -ω) +g > k (ε -ω)G < (ε) ] δ αβ , (A11) C (2) αβ (ω) = - e 2 h ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × ∫ ∞ -∞ dε [ G r (ε)g < k (ε)G r (ε -ω)g > k ′ (ε -ω) +G r (ε)g < k (ε)G > (ε -ω)g a k ′ (ε -ω) +G < (ε)g a k (ε)G r (ε -ω)g > k ′ (ε -ω) +G < (ε)g a k (ε)G > (ε -ω)g a k ′ (ε -ω) ] , (A12) C (3) αβ (ω) = e 2 h ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × ∫ ∞ -∞ dε [ G > (ε -ω)g r k ′ (ε)G r (ε)g < k (ε) +G > (ε -ω)g r k ′ (ε)G < (ε)g a k (ε) +G > (ε -ω)g < k ′ (ε)G a (ε)g a k (ε) ] , (A13) C (4) αβ (ω) = e 2 h ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × ∫ ∞ -∞ dε [ G < (ε)g > k (ε -ω)G a (ε -ω)g a k ′ (ε -ω) +G < (ε)g r k (ε -ω)G > (ε -ω)g a k ′ (ε -ω) +G < (ε)g r k (ε -ω)G r (ε -ω)g > k ′ (ε -ω) ] , (A14) C (5) αβ (ω) = - e 2 h ∑ k∈α,k ′ ∈β |V k V k ′ | 2 × ∫ ∞ -∞ dε [ G a (ε -ω)g > k (ε -ω)G < (ε)g r k ′ (ε) +G a (ε -ω)g > k (ε -ω)G a (ε)g < k ′ (ε) +G > (ε -ω)g r k (ε -ω)G < (ε)g r k ′ (ε) +G > (ε -ω)g r k (ε -ω)G a (ε)g < k ′ (ε) ] . (A15)
In the expressions of each contribution C (i) αβ (ω) to the noise, we report the bar Green functions of the reservoir

g < k∈α (ε) = 2iπf e α (ε)δ(ε -ε k ) , (A16) g > k∈α (ε) = -2iπf h α (ε)δ(ε -ε k ) , (A17) g r k∈α (ε) = [ε -ε k + i0 + ] -1 , (A18) g a k∈α (ε) = [ε -ε k -i0 + ] -1 , ( A19
)
where f e α (ε) is the Fermi-Dirac distribution function associated with the reservoir α, and f h α (ε) = 1 -f e α (ε). In the wide-band approximation limit, where Γ α (ε) = 2πρ α (ε)|V (ε)| 2 is independent of energy, we obtain the following expression for the NSFF noise

S αβ (ω) = e 2 h Γ α δ αβ ∫ ∞ -∞ dε [ -if h α (ε -ω)G < (ε) +if e α (ε) [ G r (ε -ω) -G a (ε -ω) + G < (ε -ω) ] ] + e 2 h Γ α Γ β ∫ ∞ -∞ dε [ G < (ε)G > (ε -ω) -f e α (ε)f h β (ε -ω)G r (ε)G r (ε -ω) -f e β (ε)f h α (ε -ω)G a (ε)G a (ε -ω) + [ f e α (ε)G r (ε) -f e β (ε)G a (ε) ] G > (ε -ω) + [ f h α (ε -ω)G a (ε -ω) -f h β (ε -ω)G r (ε -ω) ] G < (ε) ] . ( A20
)
For a non-interacting QD, we have 48

G r (ε) -G a (ε) = -iG r (ε) [ Γ L + Γ R ] G a (ε) , (A21) G < (ε) = iG r (ε) [ Γ L f e L (ε) + Γ R f e R (ε) ] G a (ε) . (A22)
Using iΓG r (ε) = t(ε) and G > (ε) = G r (ε) -G a (ε) + G < (ε), and considering symmetrical barriers, Γ L = Γ R = Γ, we get

G r (ε) -G a (ε) = - 2it(ε)t * (ε) Γ , (A23) G < (ε) = it(ε)t * (ε) Γ [ f e L (ε) + f e R (ε) ] , (A24) G > (ε) = - it(ε)t * (ε) Γ [ f h L (ε) + f h R (ε) ] . (A25)
Incorporating the latter expressions into Eq. (A20), we get Eq. ( 13) with matrix elements M γδ αβ (ε, ω) given in Table 1.

APPENDIX B: CHARGE NOISE

The charge noise is defined as the Fourier transform of the charge fluctuations on the QD

S Q (ω) = ∫ ∞ -∞ dte -iωt ⟨∆ Q(t)∆ Q(0)⟩ , ( B1
)
where ∆ Q(t) = Q(t) -⟨ Q⟩, with Q(t) = e N (t) = ed † (t)d(t). Performing the decoupling of the QD twoparticles Green function, we get ⟨∆ Q(t)∆ Q(0)⟩ = ⟨d † (t)d(0)⟩⟨d(t)d † (0)⟩ , (B2) which leads to

S Q (ω) = e 2 ∫ ∞ -∞ dte -iωt G < (0, t)G > (t, 0) = e 2 h ∫ ∞ -∞ dεG < (ε)G > (ε -ω) . ( B3
)
Using Eqs. (A24) and (A25) and introducing the transmission amplitude t(ε) = iΓG r (ε), we finally obtain

S Q (ω) = e 2 hΓ 2 ∫ ∞ -∞ dεT (ε)T (ε -ω) × ∑ γδ f e γ (ε)f h δ (ε -ω) . (B4)
In the case of an Anderson-type transmission amplitude, t(ε) = iΓ/(ε -ε 0 + iΓ), we have

|t(ε) -t(ε -ω)| 2 = ω 2 Γ 2 T (ε)T (ε -ω) , ( B5
)
which leads when one compare Eq. (B4) to Eq. ( 14) to the equality

∑ αβ S αβ (ω) = ω 2 S Q (ω) . (B6)

FIG. 1 :

 1 FIG. 1: Illustration of the processes that contribute to SLL(ω) with the transfer of energy ω (yellow wavy line) in the left reservoir. The green [blue] circle represents an electron [hole] with energy ε [ε -ω]. The solid [dashed] red arrow line represents a transmission process with probability amplitude t(ε) [t * (ε -ω)]. The solid [dashed] black arrow line represents a reflection process with probability amplitude r(ε) [r * (ε -ω)]. The coherent superposition of processes (a1), (a2), and (a3) leads to the M LL LL (ε, ω) contribution, process (b) to the M RR LL (ε, ω) contribution, process (c) to the M LR LL (ε, ω) contribution, and process (d) to the M RL LL (ε, ω) contribution.

FIG. 2 :

 2 FIG.2: Auto-correlators in units of e 2 Γ/ in (a) the left reservoir and (b) the right reservoir at kBT /eV = 0.01, Γ/eV = 0.02 and ε0 = 0 for {µL = eV, µR = 0} (orange lines), {µL = 0.8eV, µR = -0.2eV } (red lines), {µL = 0.6eV, µR = -0.4eV } (purple lines) and {µL = 0.5eV, µR = -0.5eV } (black lines).

FIG. 3 :

 3 FIG. 3: Differential Fano factor F (VS, ω) as a function of gate energy ε0 and bias voltage VS (both normalized by Γ) at kBT /Γ = 0.1 for two values of the frequency : (a) ω1/Γ = 0.1 (low frequency) and (b) ω2/Γ = 1 (high frequency).

  From Eq. (12), we have S αβ (τ, τ ′ ) =

TABLE I :

 I Expressions of the matrix elements M γδ αβ (ε, ω) appearing in Eq. (13).

Acknowledgments

We would like to thank Y.M. Blanter, R. Deblock, M. Guigou, T. Martin, F. Michelini, Y.V. Nazarov and F. Portier for valuable discussions. For financial support, the authors acknowledge the Indo-French Centre for the Promotion of Advanced Research (IFCPAR) under Research Project No.4704-02.

* Also at the Centre National de la Recherche Scientifique (CNRS).


J Bang-Jensen

Frédéric Havet
email: frederic.havet@inria.fr

Anders Yeo
email: andersyeo@gmail.com

The complexity of finding arc-disjoint branching flows

Keywords: disjoint branchings, branching flow, polynomial algorithm, NP-complete

The concept of arc-disjoint flows in networks was recently introduced in [2]. This is a very general framework within which many well-known and important problems can be formulated. In particular, the existence of arc-disjoint branching flows, that is, flows which send one unit of flow from a given source s to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings B + s,1 , B + s,2 from a root s in a digraph D = (V, A) on n vertices corresponds to arc-disjoint branching flows x1, x2 (the arcs carrying flow in xi are those used in B + s,i , i = 1, 2) in the network that we obtain from D by giving all arcs capacity n -1. It is then a natural question to ask how much we can lower the capacities on the arcs and still have, say, two arc-disjoint branching flows from the given root s. We prove that for every fixed integer k ≥ 2 it is

• an NP-complete problem to decide whether a network N = (V, A, u) where uij = k for every arc ij has two arc-disjoint branching flows rooted at s.

• a polynomial problem to decide whether a network N = (V, A, u) on n vertices and uij = n -k for every arc ij has two arc-disjoint branching flows rooted at s.

The algorithm for the later result generalizes the polynomial algorithm, due to Lovász, for deciding whether a given input digraph has two arc-disjoint out-branchings rooted at a given vertex.

Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every > 0 and for every k(n) with (log (n)) 1+ ≤ k(n) ≤ n 2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n -k(n).

Introduction

Notation follows [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. We denote the vertex set and arc set of a digraph D by V (D) and A(D), respectively and write D = (V, A) where V = V (D) and A = A(D). Unless otherwise specified, the numbers n and m will always be used to denote the number of vertices, repectively arcs in the digraph in question. The digraphs may have parallel arcs but no loops. Paths and cycles are always directed unless otherwise specified. We will use the notation [k] for the set of integers {1, 2, . . . , k}.

An (s, t)-path in a digraph D is a directed path from the vertex s to the vertex t. The underlying graph of a digraph D, denoted U G(D), is obtained from D by suppressing the orientation of each arc. A digraph D is connected if U G(D) is a connected graph. When xy is an arc of D we say that x dominates y. For a digraph D = (V, A) the out-degree, d + D (x) (resp. the in-degree, d - D (x)) of a vertex x ∈ V is the number of arcs of the kind xy (resp. yx) in A, where we count parallel arcs. When X ⊆ V we shall also write d + X (v) to denote the number of arcs vx with x ∈ X. An out-tree rooted at s, also called an s-out-tree, is a tree containing the vertex s in U G(D) such that every vertex v different from s has exactly one arc entering in the tree. Equivalently, s has a unique directed path to every other vertex of the tree using only arcs of the tree. An s-outbranching is a spanning s-out-tree. We use the notation T + s , B + s to denote an s-out-tree, respectively an s-out-branching.

Branchings in digraphs are important from a practical point of view and appear in many applications and hence it is relevant to consider quality measures for branchings. This has been done in a number of papers, see e.g. [START_REF] Daligault | FPT Algorithms and Kernels for the Directed k-Leaf Problem[END_REF][START_REF] Vergnas | Sur les arborescences dans un graphe orienté[END_REF][START_REF] Lokshtanov | On the directed degree-preserving spanning tree problem[END_REF][START_REF] Thomassé | Covering a strong digraph by α-1 disjoint paths: a proof of Las Vergnas' conjecture[END_REF]. An s-out-branching B + s is k-safe if no matter which out-neighbour v of s in B + s we consider, the s-out-tree T + s that we will obtain after deleting all the vertices of the out-tree T + v rooted at v in B + s contains at least k vertices (s and at least k -1 other vertices). In applications (where an s-out-branching is used to route information or similar from the root s) it is desirable to use an out-branching which is k-safe for a high value of k, because this means that no matter which arc we cut, s can still reach k other vertices using only arcs from the remaining s-out-tree.

In terms of protection against arc-faults, branchings are not a very good way of sending information from one source to all other vertices: If we insist that the vertex sets of the routes that we use to send the information from s to all other vertices may only intersect in a prefix of each route (this is equivalent to saying that the union of the routes is an s-out-branching), then the set of routes may be very vulnerable to arc-deletions. As an example consider the digraph H consisting of vertices s = v 1 , v 2 , . . . , v 2p+1 and arcs {sv 2 , sv 3 , v 2 v 3 } ∪ {v 3 v i |i ≥ 4}. This digraph contains no 3-safe s-outbranching. On the other hand, if instead we use each of the arcs sv 2 , sv 3 on p of the paths from s to V -s, then deletion of one of the arcs sv 2 , sv 3 disconnects s from only half of the other vertices. We may then ask what is the best way to route the information from s to all other vertices, while preserving a high degree of protection against arc-faults. This leads to the study of branching flows. Before we can formally define these, we need to recall a bit of flow theory.

A network N = (V, A, u) is a digraph D = (V, A) equipped with a non-negative capacity function u : A→R 0 on its arcs. A flow in N is any non-negative function x : A→R 0 which satisfies that x ij ≤ u ij for every ij ∈ A, where x ij , u ij denote, respectively, the flow value on ij and the capacity of ij. The balance-vector of a flow x is the function b x on V which to each vertex i ∈ V associates the value b x (i) = ij∈A x ij -pi∈A x pi .

If N = (V, A, u, b), that is, there is also a balance-vector specified for N , then a flow

x is feasible in N if it satisfies b x (v) = b(v) for all v ∈ V . Two flows x, y in a network N are arc-disjoint if x ij • y ij = 0 for every arc ij of N .
An important result in flow theory is the following which states that it is possible to decide in polynomial time whether or not there exists a feasible flow for a given network N = (V, A, u, b) (see e.g. [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 4.8]).

Theorem 1.1 For a given network N = (V, A, u, b) with arc-capacities given by u and vertex-balances prescribed by b one can check, using one max-flow calculation, whether there exists a feasible flow x in N .

A path flow along the path P (resp. cycle flow along the cycle C) in a network N is a flow x which has x ij = k for every arc on P (resp. C) for some positive value k and x ij = 0 for all arcs not on P (resp. C). An s-branching flow in a network N is a flow x in N with balance vector b x (v) = -1 for v = s and b x (s) = n -1, where n denotes the number of vertices in N .

The following folklore result (see e.g. [START_REF] Ahuja | Network flows[END_REF]Section 3.5] or [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 4.3.1]) is very useful when working with flows. Theorem 1.2 (Flow Decomposition Theorem) Every flow x in a network N on n vertices and m arcs is the arc-sum of at most n + m path and cycle flows. Furthermore, the path flows can be taken along paths P 1 , . . . , P q such that P i starts in a vertex s i with b x (s i ) > 0 and ends in a vertex t i with b x (t i ) < 0 for i ∈ [q]. In particular, if b x ≡ 0 there are no path flows in the decomposition and x is the arc-sum of at most m cycle flows. Given the flow x, a decomposition as above can be found in time O(nm).

Note that when we consider branching flows below, we are only interested in the acyclic part of such a flow, that is, the collection of paths from the root to all other vertices that we obtain by flow decomposition (we leave out flow along cycles since that does not contribute to the balance of the flow). By the Flow Decomposition Theorem, every branching flow x from s contains one or more out-branchings from s as a subdigraph (x sends one unit of flow from s to all other vertices).

As in the case of branchings, we may also measure the quality of an s-branching flow in terms of how vulnerable it is towards arc-deletions. If we have no restrictions on the flow values, a branching flow x may have flow equal to r ≤ n -1 on some arc out of s, corresponding to that arc belonging to r of the path flows whose arc sum forms the branching flow x. This means that if we keep only the arcs used by x and one arc fails (is deleted) then s may be unable to reach as many as r vertices after deleting that arc. In particular, if r = n -1, one arc failure can disconnect s from all other vertices in the chosen solution. Thus, from a practical point of view (say, in an application where branching flows are used to route information), it could be useful to restrict the maximum flow value in an arc to as small as possible. If follows from Theorem 1.1 that for every k, there is a polynomial algorithm to check whether a network N = (V, A, u ≡ k) has an s-branching flow from a given vertex s. Furthermore, also the min-cost version of this can be solved in polynomial time using any polynomial algorithm for minimum cost flows. These observations should be compared to the following result. Theorem 1.3 [START_REF] Bang-Jensen | Balanced branchings in digraphs[END_REF] The problem of deciding whether a digraph on n vertices has an (n -k)-safe outbranching is polynomial time solvable if k ≤ 2 and NP-complete for all k ≥ 3 (k is not part of the input).

Edmonds characterized digraphs with k arc-disjoint s-out branchings from a prescribed root s. Theorem 1.4 (Edmonds' Branching Theorem) [START_REF] Edmonds | Edge-disjoint branchings[END_REF] A digraph D = (V, A) has k arc-disjoint sout-branchings if and only if D has k arc-disjoint (s, v)-paths for every v ∈ V -s.

From Edmonds' Branching Theorem and the algorithmic proof of this due to Lovász [START_REF] Lovász | On two min-max theorems in graph theory[END_REF] (see also [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 9.3]), we obtain the following characterization of networks in which all capacities are equal to n -1 that have k arc-disjoint branching flows: Theorem 1.5 A network N = (V, A, u ≡ |V | -1) has k arc-disjoint s-branching flows x 1 , x 2 , . . . , x k if and only if there are k arc-disjoint (s, v)-paths in N for every v ∈ V \ {s}. Furthermore, there is a polynomial algorithm for constructing such flows x 1 , x 2 , . . . , x k when they exist.

The purpose of this paper is to study the complexity of the problem of deciding the existence of arc-disjoint branching flows in networks whose arc-capacities are bounded. We first show that when all capacities are bounded by a constant k, the problem becomes NP-complete as soon as k ≥ 2. The problem is trivial for k = 1 (see below).

In the second part of the paper we consider the case in which we still have uniform capacities, but now they are all n -k for some constant k. The case k = 1 is the same as asking for a pair of arc-disjoint s-out-branchings and hence polynomial by our remarks above. For k = 2 the problem is still fairly simple: we just need a pair of arc-disjoint s-out-branchings both of which are 2-safe and this can be checked in polynomial time. For larger values of k the problem becomes more complicated, but we use structural observations about branching flows in networks with high capacities (n -k for all arcs) to reduce the problem to that of checking the existence of a pair of arc-disjoint s-out-branchings for at least one digraph in a family of digraphs of polynomial size in n and k. Our method extends Lovász's algorithmic proof of Edmonds' Branching Theorem. The key idea is that, if the capacities are n -k and there is a branching flow from s in N then there exists one in which only vertices that are close to s will receive flow on more than one arc.

Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every > 0 and every k(n) with (log (n)) 1+ ≤ k(n) ≤ n 2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n -k(n).

Arc-disjoint branching flows in bounded capacity networks

Clearly a unit capacity network has two arc-disjoint branching flows from a given root s if and only if s has at least two arcs to every other vertex. So the first interesting case is arc-disjoint branching flows in networks with maximum capacity 2. Here the complexity of the uniform capacity case was open but if we allow some capacities to be only one it was shown in [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] that the problem is already NP-complete (note that the proof in [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] does not extend to a proof for the uniform capacity case).

Theorem 2.1 [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] It is NP-complete to decide whether a network N = (V, A, u), where u ij ∈ {1, 2} for all ij ∈ A, has two arc-disjoint s-branching flows.

Our first goal is to use Theorem 2.1 to prove that it is NP-complete to decide the existence of arc-disjoint branching flows from the same root in networks where all the capacities equal some fixed number k ≥ 2. This easily implies that it is also NP-complete to decide the existence of arc-disjoint branching flows from the same root in networks where all the capacities are at most k.

Theorem 2.2 For every fixed integer k ≥ 2, it is NP-complete to decide whether a network N = (V, A, u ≡ k) with special vertex s has two arc-disjoint s-branching flows.

Proof: We will reduce from the case when the capacity of each arc is either 1 or 2, which is NP-hard by Theorem 2.1. So let N = (V , A , u ) be a network, where u ij ∈ {1, 2} for all ij ∈ A . We will create a new network N = (V, A, u ≡ k) as follows.

For each arc ij ∈ A we do the following. Add k new vertices, y 1 ij , y 2 ij , . . . , y k ij and add two parallel arcs from s to y 1 ij and from y r ij to y r+1 ij for all r = 1, 2, . . . , k -1. Finally remove the arc ij and add the arcs iy u ij ij and y k ij j. Let N denote the network obtained after performing the above operation for all ij ∈ A and setting all capacities to k. Clearly N can be constructed in polynomial time given N = (V , A , u ). We will show that N has two arc-disjoint s-branching flows if and only if N has two arc-disjoint s-branching, which would complete the proof by Theorem 2.1.

First assume that there are two arc-disjoint branching flows, x 1 and x 2 , from s in N . For each ij ∈ A modify the flows as follows. Let a r,1 ij and a r,2 ij be the two parallel arcs from y r ij to y r+1 ij for r = 1, 2, . . . , k -1 and let a 0,1 ij and a 0,2 ij be the two parallel arcs from s to y 1 ij . Initially, for all r = 0, 1, . . . , k -1, add the arc a r,1 ij to x 1 with flow k -r and add the arc a r,2 ij to x 2 also with flow k -r. Also let the flow on iy u ij ij and y k ij j be zero in both branching flows. Now for each q = 1, 2, add an additional flow of x q ij to all the following arcs (which form a path).

iy u ij ij , a u ij ,q ij
, a

u ij +1,q ij , a u ij +2,q ij , . . . , a k-1,q ij
, y k ij j As x 1 and x 2 are arc-disjoint flows we note that x 1 ij = 0 or x 2 ij = 0 (or both). Therefore we have only added flow to the arcs iy u ij ij and y k ij j in at most one of x 1 and x 2 . This implies that even after the above operation the flows are arc-disjoint. Furthermore we note that no arc has received a flow of more than k, as if we add a flow of x q ij to an arc a r,q ij then r ≥ u ij , which implies that the flow in a r,q ij is at most k

-r + x q ij ≤ k -u ij + u ij ≤ k.
Furthermore the resulting flows are branching flows as, in each of them, the flow entering any vertex (except s) is one more than the flow leaving the vertex. Therefore after performing the above operation for all ij ∈ A we have obtained the desired branching flows in N .

Conversely assume that there are two arc-disjoint branching flows, x 1 and x 2 , from s in N . Without loss of generality assume that there is no directed cycle in x 1 or in x 2 (as we can easily remove such cycles by the Flow Decomposition Theorem). Consider some ij ∈ A . We will first show that we may assume that the flow from s to y 1 ij is k in both x 1 and in x 2 (each flow using a separate arc from s to y 1 ij ). Assume that this is not the case and without loss of generality the flow from s to y 1 ij is less than k in x 1 . As all parameters in the network are integer-valued we may assume that all flows are integer-valued. We must have at least one unit of flow on iy u ij ij in x 1 , as otherwise we cannot have a balance of -1 on all vertices y 1 ij , y 2 ij , . . . , y k ij . Therefore there exists a path P from s to i in x 1 with a flow of at least 1 on all arcs of P . If P uses the arc from s to y 1 ij or the arc y k ij j, then adding the arc iy u ij ij to P gives us a directed cycle, a contradiction. Now remove one unit of flow along all arcs of P and iy u ij ij and add one unit of flow to the arc sy 1 ij and if u ij = 2 then also add one unit of flow to the arc y 1 ij y 2 ij . The resulting flow is still a branching flow and no capacities are violated, but we have increased the flow from s to y 1 ij by 1. Continue this process until the flow from s to

y 1 ij is k in both x 1 and in x 2 .
As the amount of flow entering the set {y 1 ij , y 2 ij , . . . , y k ij } has to be k larger than the amount of flow leaving the set in both x 1 and x 2 , we note that in x 1 the flow on iy u ij ij and on y k ij j is the same. Analogously in x 2 the flow is the same and the flow is zero for either x 1 or x 2 (or both). Assume without loss of generality that x 2 has no flow on iy u ij ij (and therefore also no flow on y k ij j). As the capacity on the arc y

u ij ij y u ij +1 ij
is k and there are k-u ij vertices in {y

u ij +1 ij , y u ij +2 ij , . . . , y k ij } we note that the arc y k ij j cannot have flow more than k -(k -u ij ) = u ij . So removing all vertices y 1 ij , y 2 ij , . . . , y k ij
and all arcs touching these vertices, but adding back the arc ij with flow the same as we had in iy

u ij ij
(and also in y k ij j) gives us two arc-disjoint branching flows where the flow on ij is bounded by u ij . Therefore doing the above process for all ij ∈ A gives us the desired branching flows in N .

Arc-disjoint k-safe branchings

Recall that n denotes the number of vertices of the digraph in question. In the next section we will consider branching flows in networks where the capacities are n -k for some constant k. To study these, it turns out that it is relevant to study the problem of finding arc-disjoint k-safe s-out-branchings in digraphs with n vertices for some given constant k. When k = 2 the connection is straightforward as every s-branching flow in N = (V, A, u) with u ≡ n -2 corresponds to a 2-safe branching (at least two children at the root). Hence there are arc-disjoint s-branching flows x 1 , x 2 from s in N if and only if the network contains two arc-disjoint branchings, each of which uses at least two arcs from the root and such branchings are 2-safe. For higher values of k we can make use of Theorem 3.1 which also plays an important role in the next section.

The following consequence of the so-called strong version of Edmonds' Branching Theorem (see e.g. [12, Theorem 53.1]) will be useful in our search for arc-disjoint k-safe branchings. We include the proof for completeness.

By Edmonds' Branching Theorem, there are two arc-disjoint s-out-branchings if and only if we have

d -(X) ≥ 2 for all X ⊆ V -s (1)
Theorem 3.1 Let D be a digraph with two arc-disjoint s-out-trees T + s,1 , T + s,2 . Then D contains two s-out-branchings B + s,1 , B + s,2 such that A(T + s,i ) is contained in A(B + s,i ) for i = 1, 2 if and only if (1) holds and D -A(T + s,i ) has an out-branching (in which case it has one which contains all the arcs of T + s,3-i ) for i = 1, 2. Furthermore, such branchings can be found in polynomial time when they exist.

Proof: The two conditions above are clearly necessary and can be checked in polynomial time, so assume that they are both satisfied. We will show how to modify the algorithmic proof of Edmonds' Branching Theorem by Lovász, for the case of two branchings (see e.g. [3, Section 9.3] or [12, Section 53.1]) so that we achieve two arc-disjoint branchings B + s,1 , B + s,2 with A(T + s,i ) ⊆ A(B + s,i ) for i = 1, 2. We give the full proof as it is not very long and also makes it easy to check that there is a polynomial algorithm for constructing the desired branchings.

First we delete all arcs of T + s,2 , call the resulting digraph D and start the algorithm from the out-tree T + s = T + s,1 in D . We say that a set X ⊆ V -V (T + s,2 ) is dangerous if it has in-degree 1 in D -A(T + s ), where T + s is the current out-tree (containing T + s,1 ) which has been constructed so far by the algorithm. By submodularity of the in-degree function, if X, Y are both dangerous and they intersect, then so are X ∪ Y and X ∩ Y . Also, since D satisfies (1), every dangerous set must intersect V (T + s ).

We have two possible scenarios when trying to extend T + s . Note that, by our assumption, as long as V -V (T + s ) = ∅ there is at least one arc from V (T + s ) to V -V (T + s ):

(a) Every dangerous set (possibly there are none) is contained in V (T + s ).

(b) Some dangerous set intersects both V (T + s ) and V -V (T + s ).

If (a) holds, then we can take any arc uv ∈ A(D ) with u ∈ V (T + s ) and add uv to T + s and continue. If (b) holds, then (as in the original proof by Lovász) let X be an inclusionwise minimal dangerous set intersecting both V (T + s ) and V -V (T + s ). It is easy to check that there is some arc uv ∈ A(D ) with u ∈ V (T + s ) ∩ X and v ∈ X -V (T + s ): Suppose not, then every arc which enters X -V (T + s ) also enters X and we would have

d - D (X -V (T + s )) = d - D (X -V (T + s )) = d - D -A(T + s ) (X -V (T + s )) ≤ d - D -A(T + s ) (X) = 1, contradicting (1)
. So there is an arc uv ∈ A(D ) with u ∈ V (T + s ) ∩ X and v ∈ X -V (T + s ). This arc cannot enter a dangerous set since (by the remark above on intersecting dangerous sets) that would contradict the minimality of X. Hence we may extend T + s by adding uv and continue the algorithm until T + s is spanning. At that point, since every set not intersecting V (T + s,2 ) has in-degree at least one in D -A(T + s ), we can extend T + s,2 to a branching arc-disjoint from the first one and the proof is complete.

Corollary 3.2 A digraph D contains a pair of arc-disjoint s-out-branchings such that s has out-degree at least 2 in both if and only if d + (s) ≥ 4 and D contains a pair of arc-disjoint branchings.

Proof: By Theorem 3.1 it suffices to show that we can find two arc-disjoint out-trees T + s,1 , T + s,2 , each of which have out-degree 2 at s, such that there are arc-disjoint branchings extending each of these.

Call a set X ⊆ V \ {s} tight if d -(X) = 2. If X, Y ⊆ V \ {s} are distinct tight sets both containing two out-neighbours of s, then they cannot share exactly one out-neighbour of s: Suppose p, q, r are all out-neighbours of s such that X ∩ {p, q, r} = {p, q} and Y ∩ {p, q, r} = {q, r}. Then it follows from (1) the submodularity of the in-degree function that we have

2 + 2 = d -(X) + d -(Y ) ≥ d -(X ∪ Y ) + d -(X ∩ Y ) ≥ 3 + 2, (2)
a contradiction. It follows from the observation above and the fact that d + (s) ≥ 4 that we can find four outneighbours p, q, r, t of s such that there is no tight set containing both p, q and no tight set containing both r, t. This is clear if there are no tight sets containing two neighbours of s and otherwise let X be a tight set containing two neighbours a, b of s. By the claim there is no tight set containing a but not b and conversely so the claim follows. Now let T + s,1 be the out-tree formed by the two arcs sp, sq and T + s,2 be the out-tree formed by the arcs sr, st and apply the algorithm of Theorem 3.1.

See [START_REF] Bang-Jensen | Balanced branchings in digraphs[END_REF] for a more results related to Corollary 3.2. Theorem 3.1 can be generalized to extensions of p arc-disjoint s-out-trees. In [?] Szegö attributes the following result to Frank. Theorem 3.3 Let D = (V, A) be a digraph and let T + s,1 , . . . , T + s,p be arc-disjoint s-out-trees in D. There exists arc-disjoint s-out-branchings B + s,1 , . . . , B + s,p in D such that

A(T + s,i ) ⊆ A(B + s,i ) for i ∈ [p] if and only if d - D (X) ≥ q(X) for all X ⊆ V, (3)
where D is the digraph obtained from D by deleting all arcs of T + s,1 , . . . , T + s,p and q(X) denotes the number of s-out-trees among T + s,1 , . . . , T + s,p which do not intersect X.

The proof of a generalization of this result can be found in [?]. This proof, which is a direct generalization of the proof we used for Theorem 3.1, can be turned into a polynomial algorithm which either constructs the desired s-out-branchings or finds a set X violating (3) above.

Theorem 3.4 For every pair of fixed positive integer k, p, there exists a polynomial algorithm for checking whether a given input digraph D has p arc-disjoint k-safe s-out-branchings. Furthermore, such branchings can be found in polynomial time when they exist.

Proof: Observe that an s-out-branching is k-safe if and only if it contains an s-out-tree with at most 2k -1 vertices which is itself k-safe. Let B be the set of all k-safe s-out-trees from s on at most 2k -1 vertices. As k is a constant, this set can be constructed in polynomial time O(|V (D)| 2k-1 ). Now, by Theorem 3.3, it suffices to check, using the algorithmic version of the theorem for (at most) all possible collections of p arc-disjoint out-trees T + s,1 . . . , T + s,p ∈ B whether the current collection can be extended to p arc-disjoint s-out-branchings and return the branchings constructed if some iteration is successful. If no set of p arc-disjoint out-trees T + s,1 . . . , T + s,p ∈ B can be extended, then D has no set of p arc-disjoint k-safe out-branchings from s.

Arc-disjoint branching flows, the case of high capacities

We now study the complexity of finding arc-disjoint branching flows in networks where every arc has capacity n -k for some constant k. If x is an s-branching flow in D = (V, A), then let D x = (V, A x ) be the subdigraph of D with vertex set V and arc set A x = {a ∈ A | x(a) > 0}. Thus D x only contains the arcs with non-zero flow in x.

Growing and trimming a branching flow

Definition 4.1 Let D = (V, A) be a digraph of order n, let s ∈ V (D) be given, and let k be an integer. An (s, k)-branching flow, is a branching flow x from s in D, such that x(e) ≤ n -k for all arcs 1 e ∈ A. Note that x is also an (s, k)-branching flow in D x .

(s, k)-branching flows have the the nice property that an (s, k)-branching flow of an induced subdigraph of D (containing s) can be extended to an (s, k)-branching flow of D provided that every vertex of D is reachable from s. This extra condition is not too demanding because it is a trivial necessary condition for a digraph to have an (s, k)-branching flow. Proof: Since one can reach all vertices of D, there is an ordering v 1 , . . . , v p of the vertices of V (D) \ X such that for all 1 ≤ i ≤ p, there is an (s, v i )-path

P i in D i := D[X ∪ {v 1 , . . . , v i }].
Assume that D 0 = D[X] contains an (s, k)-branching flow x 0 . Let us prove by induction on i that D i contains an (s, k)-branching flow x i for all 0 ≤ i ≤ p.

Suppose now that i ≥ 1. By the induction hypothesis, D i-1 contains an (s, k)-branching flow x i-1 in D i-1 . Let x i be the flow obtained from x i-1 by adding one unit of flow on all arcs in P i . Clearly, x i is an (s, k)-branching flow in D i .

Hence x p is an (s, k)-branching flow in D p = D.

Definition 4.3 An (s, k)-core in D is a set X of vertices containing s, of cardinality 2k, and such that D[X] contains an (s, k)-branching flow.

Consider a digraph D and a vertex s from which all vertices of D are reachable. By Lemma 4.2, if D has an (s, k)-core, then it contains an (s, k)-branching flow. We shall now prove that this easy sufficient condition is also necessary (provided that D has order at least 2k). Theorem 4.4 Let k be a positive integer, let D be a digraph D of order at least 2k, and let s be a vertex from which all vertices of D are reachable. D contains an (s, k)-branching flow if and only if it has an (s, k)-core.

In order to prove this theorem, we need two lemmas. Lemma 4.5 Let D = (V, A) be a digraph on n vertices and let k be a positive integer such that n > 2k. Assume that there exists an (s, k)-branching flow, x, in D and let A ⊆ A x be arbitrary. Let N be the network consisting of the digraph D x and with capacity u(e) = n -k on all e ∈ A x \ A and u(e) = n -k -1 for all e ∈ A .

If there is no feasible s-branching flow in N , then there exists a set X ⊆ V , such that s ∈ X, |X| = k, there is only one arc, e, out of X in D x and e ∈ A .

Proof: Let N be the network defined as in the statement of the lemma and let N k be the same as N , except all capacities are n -k. In both N and N k add a vertex t and an arc from all vertices in V (D) \ {s} to t of capacity 1 and let the resulting networks be called N t and N t k , respectively. By the assumption of the lemma, there exists an (s, t)-flow in N t k of value n -1, but there does not exist an (s, t)-flow in N t of value n -1. Let (X, V ∪ {t} \ X) be a minimum (s, t)-cut in N t , which, by the Max-Flow Min-Cut Theorem (see e.g. [3, Theorem 4.5.3]), has capacity less than n -1. Recall that, by definition of an (s, t)-cut, s ∈ X. Thus by the existence of x, the cut (X, V ∪ {t} \ X) has capacity at least n -1 in N k . Therefore some arc of A must leave X, as otherwise the cut would have the same capacity in N t and N t k . We must have d + Dx (X) ≤ 1 as otherwise the capacity of the cut in N t would be at least 2(n -k -1) > n -2, a contradiction. Therefore there is exactly one arc, e, out of X in D x and we have e ∈ A . Finally if |X| < k then the capacity of (X, V ∪ {t} \ X) in N t k would be at most (|X| -1) + n -k < n -1, a contradiction, and if |X| > k then the capacity of (X, V ∪ {t} \ X) in N t would be (|X| -1) + n -k -1 > n -2, a contradiction. Therefore |X| = k, completing the proof. Lemma 4.6 Let k be a positive integer. If there exists an (s, k)-branching flow x in a digraph D of order greater than 2k, then there exists an (s, k)-branching flow in D-v for some vertex v ∈ V (D)\{s}.

Proof: Let x and D be defined as in the statement of the lemma. Any set, X, with s ∈ X and |X| = k and d + D (X) = 1 is called a critical set in D. We first show that at most one critical set exists in D. For the sake of contradiction assume that X and Y are distinct critical sets in D.

As X = Y we note that |X ∩ Y | < k. As x has flow n -1 -(|X ∩ Y | -1) > n -k leaving X ∩ Y ,
we note that there are at least two arcs, e 1 and e 2 , leaving X ∩ Y in D. Each e i leaves X or Y (or both). As only one arc leaves X and only one arc leaves Y we can without loss of generality assume that e 1 leaves X but not Y and e 2 leaves Y but not X. This implies that no arc leaves X ∪ Y as otherwise d + (X) or d + (Y ) would be greater than one. As n > 2k and |X ∪ Y | ≤ 2k -1 we get a contradiction to s being able to reach all vertices in D. Therefore at most one critical set exists in D.

If Y is a critical set in D, then let e be the arc out of Y in D and let A = A(D) \ {e} and if no critical set exists in D then let A = A(D). By Lemma 4.5, we note that there exists an (s, k)-branchng flow y in D with y(e ) ≤ n -k -1 for all e ∈ A . Now, without loss of generality, we may assume that D = D y (that is, every arc in D has non-zero flow). We may also assume that D is acyclic, as if there exists a cycle in D then we can reduce the flow along this cycle until one of the arcs gets flow zero and therefore disappears from D y .

Let P be a longest path in D starting at s, such that if some arc has flow n -k in y, then this arc belongs to P . Let v be the last vertex on this path. We must have d It is now not difficult to see that y is an (s, k)-branching flow in D -v, which completes the proof.

Proof of Theorem 4.4: We already proved that having an (s, k)-core is a sufficient condition for D to contain an (s, k)-branching flow, because all vertices are reachable from s.

Let us now prove that it is a necessary condition. Assume that D contains an (s, k)-branching flow. We repeatedly apply Lemma 4.6 and remove vertices from D, until we are left with D 2k of order 2k which contains an (s, k)-branching flow. Then V (D 2k ) is an (s, k)-core.

A polynomial algorithm for the case of capacities n minus a constant

We are now ready to apply the results developed in the previous subsection to obtain the desired algorithm.

Theorem 4.7 For every fixed natural number k there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains two arc-disjoint (s, k)-branching flows.

Proof: Let the digraph D = (V, A) on n vertices and the special vertex s be given. We may assume that n > 2k since otherwise the size of D is constant and we can solve the problem by a brute force method.

As the arc-set of every branching flow from s contains an s-out-branching, we first check whether D satisfies (1) and stop if this is not the case. Hence we assume below that D satisfies [START_REF] Ahuja | Network flows[END_REF]. Now for every choice of two sets, X, Y ⊆ V , such that |X| = |Y | = 2k, and s ∈ X ∩ Y , we will check whether they are (s, k)-cores in two arc-disjoint digraphs D X and D Y in which every vertex is reachable from s. We proceed as follows. For every subset of arcs A

X ∈ D[X] and A Y ∈ D[Y ], let D X core = (X, A X ) and D Y core = (Y, A Y )
and check if the following hold.

(i):

A X ∩ A Y = ∅.
(ii): There exists an (s, k)-branching flow in D X core and an (s, k)-branching flow in D Y core .

(iii): We can partition A(D) \ (A X ∪ A Y ) into A and A , such that there exists an s-out-branching in D X = (V (D), A X ∪ A ) and also in

D Y = (V (D), A Y ∪ A ).
Clearly, X and Y are (s, k)-cores in two arc-disjoint digraphs D X and D Y in which every vertex is reachable from s if and only if (i)-(iii) are possible. Hence, by Theorem 4.4, our algorithm is correct.

Let us now analyse its complexity. Part (i) can be checked in time O(n + m) and part (ii) can be checked in O(k 3 ) time, using a max-flow algorithm. Now let us show how to check part (iii) given that (i) and (ii) passed. Fix arbitrary spanning s-out-trees T + s,X , T + s,Y in D X core , D Y core respectively and let D * be the spanning subdigraph that we obtain from D by deleting the arcs in (A X \ A(T + s,X )) ∪ (A Y \ A(T + s,Y )). We claim that (iii) holds if and only D * contains a pair of arc-disjoint s-out-branchings B + s,X , B + s,Y such that A(T + s,X ) ⊂ A(B + s,X ) and A(T + s,Y ) ⊂ A(B + s,Y ). This follows from the fact that every s-out-branching B + s in D X = (V (D), A X ∪ A ) can be converted to an s-out-branching B + s,X such that A(T + s,X ) ⊂ A(B + s,X ) by replacing the arcs of B + s that enters a vertex in X by A(T + s,X ). The same applies to every s-out-branching B + s in D Y = (V (D), A Y ∪ A ) and A(T + s,Y ). Now it follows from Theorem 3.1 that all we need to do is to check that D * contains a pair of arc-disjoint s-out-branchings and then check that D * -A X contains an s-out-branching and D * -A Y contains an s-out-branching. For a fixed choice of A X , A Y all of this can be done in time O(n 3 ) (the time to check that (1) holds).

Note that there are less than n 2k choices for choosing X and less than n 2k choices for choosing Y . As |A(X)|, |A(Y )| < 2k 2 we note that there are less than 2 (2k 2 ) options for choosing A X and analogously for choosing A Y . Therefore there are less than n 4k × 2 (4k 2 ) options for choosing X, Y , A X and A Y , which is a polynomial when k is a constant. Therefore the algorithm runs in polynomial time.

It is not difficult to see that using the algorithmic version Theorem 3.3 we obtain the following. Theorem 4.8 For every pair of fixed natural numbers k, p there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains p arc-disjoint (s, k)branching flows.

Modifying the first part of the proof of Theorem 3.4 we can even generalize as follows. We leave the easy details to the interested reader. Theorem 4.9 For every fixed natural number p and every collection of fixed natural numbers k 1 , . . . , k p there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains p arc-disjoint branching flows x 1 , . . . , x p such that x i is an (s, k i )-branching flow.

The case of capacities n -f (n)

We now show that, under a common complexity theoretic assumption, we cannot decrease the capacities by much more than a constant before the problem of the existence of arc-disjoint branching flows becomes non-polymomial.

Exponential Time Hypothesis (ETH): [7]

There is a positive real s such that 3-SAT with n variables and m clauses cannot be solved in time 2 sn (n + m)O(1).

If the ETH is true, then there is no algorithm that solves 3-SAT in subexponential time. That is, there is no 2 o(n) algorithm that solves a 3-SAT instances with n variables. Using the so-called Sparsification Lemma we can obtain the following lemma. Lemma 5.1 [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] Given ETH, there is a positive real s such that 3-SAT with n variables and m clauses cannot be solved in time 2 s m (n + m)O(1). Lemma 5.2 Assume the ETH holds and let > 0 be arbitrary and let k(n) be an integer function, such that (log(n)) 1+ ≤ k(n) ≤ n/2 for all n > 0. Furthermore assume that there exists a constant C * such that for all c ≥ C * there exists an n such that k(n) = c.

Then there is no polynomial (in n) algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, k(n))-branching flows.

Proof: Let F be an instance of 3-SAT, with variables v 1 , v 2 , . . . , v l and clauses C 1 , C 2 , . . . , C m . That is, F = C 1 ∧ C 2 ∧ • • • ∧ C m . We will construct a digraph D as follows (see Figure 1).

Let X 1 , X 2 , X 3 . . . , X l and W 1 , W 2 , . . . , W l-1 be independent vertex sets of size two. Let Q be an independent set of size q (q will be determined later) and let the vertex set of D be the following.

V (D) = {s, t, c 1 , c 2 , . . . , c m } ∪ X 1 ∪ X 2 ∪ • • • ∪ X l ∪ W 1 ∪ W 2 ∪ • • • W l-1 ∪ Q
Add all possible arcs from X i to W i and from W i to X i+1 for all i = 1, 2, 3, . . . , l -1. Add two parallel arcs from s to each vertex in X 1 and two parallel arcs from t to each vertex in Q. Add both arcs from X l to t. Denote the vertices of X i as X i = {x i , xi } for i = 1, 2, . . . , l and if clause C j contains literal v s then add two parallel arcs from x s to c j and if C j contains literal vs then add two parallel arcs from xs to c j (for all j = 1, 2, . . . , m). Note that |V (D)| = n = 4l + m + q. Let q be determined such that k(4l + m + q) = k(n) = 2l + m. By the definition of k(n) we note that the following holds (as we may assume that 2l + m > C * , where C * is defined in the statement of the lemma).

Theorem 6.3 For every pair of fixed integers k, p, there exists a polynomial-time algorithm for deciding whether an undirected graph G with prescribed root s contains a collection of p edge-disjoint k-safe s-rooted spanning trees.

Proof: Observe that an s-rooted spanning tree T is k-balanced if and only if it contains an srooted subtree with at most 2k -1 vertices which is itself k-balanced (we need 2k -1 only if s has degree 2 in T ). Now let T be the set of all k-balanced s-rooted trees on at most 2k -1 vertices in G. We can find the set T in time O(|V | 2k-1 ). For each collection of p edge-disjoint trees U 1 , . . . , U p of T each containing s we can test in polynomial time using the algorithm of Theorem 6.2 whether there are p edge-disjoint s-rooted spanning trees that extend U 1 , . . . , U p respectively. By the remark above this proves the theorem.

Further research

Theorem 4.7 asserts that for every fixed integer k, deciding whether an input digraph with a prescribed vertex s contains two arc-disjoint (s, k)-branching flows can be done in polynomial time. A natural question is to ask about the parameterized complexity of the problem with respect to the parameter k. The above result shows that the problem is in XP. A natural question is to ask whether it is fixed-parameter tractable (FPT) or not.

Lemma 4 . 2

 42 Let D be a digraph, let s be a vertex of D such that s can reach all vertices in D, and X a set of vertices containing s. If D[X] contains an (s, k)-branching flow, then D contains an (s, k)-branching flow.

  + D (v) = 0 as otherwise there either exists a cycle in D or the path P wasn't longest possible. Let D = D -v and consider the flow y in D obtained from y by reducing the flow of each arc on P by one. By construction, no arc e ∈ A(D ) has y (e ) = n -k, which implies that y (e ) ≤ n -k -1 = |V (D )| -k for all e ∈ A(D ).

Figure 1 :

 1 Figure 1: The digraph D, whereC 1 = (v 1 ∨ v 2 ∨ v4 )

Problem 6 . 4

 64 Does there exists an integer-valued function f a constant c and an algorithm that, given an integer k, an input digraph D and a vertex s in D, decides in time f (k) • n c whether D contains two arc-disjoint (s, k)-branching flows ?

It is easy to check that every s-branching flow from s which decomposes into path flows (no cycle in the decomposition) is an (s, 1)-branching flow.

Institute Mittag-Leffler, spring 2014. The research of Bang-Jensen was also supported by the Danish research council under grant number 1323-00178B † Project Coati, I3S (CNRS, UNSA) and INRIA, The research of Yeo was supported by the Danish research council under grant number 1323-00178B

We will now consider the problem of deciding if D contains two arc-disjoint (s, k(n))-branching flows. First assume that it does and let B 1 and B 2 denote the two arc-disjoint (s, k(n))-branching flows. As all vertices in V (D) \ {s, c 1 , c 2 , . . . , c m } have in-degree two and all vertices in {c 1 , c 2 , . . . , c m } have out degree zero (and therefore in-degree exactly one in B i for i = 1, 2) we note that the arcs carying flow in B 1 and B 2 must form arc-disjoint out-branchings in D. Below we will use the name B i for both the flow B i and the corresponding branching in D.

Let P i be the (s, t)-path in B i for i = 1, 2. Note that |V (P i )| = 2l + 1 and that in B i we include an arc from t to every vertex in Q. Therefore we must send at least 2l + q units of flow through the first arc in P i in B i . As 2l + q = n -k(n) we must send exactly this much flow through the arc, which implies that all vertices in {c 1 , c 2 , . . . , c m } belong to a subtree, S i , in B i which does not start with the first arc of P i . Note that S i contains exactly one vertex in each X j , for j = 1, 2, . . . , l (the other is on P ). If S i contains the vertex x j then let v j = T rue and if S i contains the vertex xj then let v j = F alse. It is not difficult to see that clauses C r are satisfied as the arc into c r indicates which literal is true. Therefore F is satisfied in this case.

Conversely, assume that F is satisfied by the truth assignment t. Let X contain x j if v j = T rue under t and let X contain xj otherwise.

. . , l -1. Let P i be the (s, t)-path containing all vertices in X and all vertices w i j for j = 1, 2, 3, . . . , l -1 and i = 1, 2. Let S i be the out-tree containing all vertices in X ∪ {c 1 , c 2 , . . . , c m } and all vertices w 3-i j for j = 1, 2, 3, . . . , l -1 and i = 1, 2 (which is possible as F is satisfied by t). Let B i be the out tree obtained by adding (a copy of) the arcs sx 1 and sx 1 and (a copy of) each arc from t to Q to P i and S i . Note that B 1 and B 2 are two arc-disjoint out-branchings, which can easily be made into (s, k(n))-branching flows (by sending the appropriate amount of flow through the arcs of B i ). We have now shown that there exists two disjoint (s, k(n))-branching flows if and only if F is satisfiable.

For the sake of contradiction assume that there is a polynomial (in n) algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, k(n))-branching flows. Let the algorithm have complexity O(n c ), for some constant c.

As (log(n)) ) , which gives us an algorithm with the following complexity.

As l ≤ 3m, the running time is at most O(2 c(7m) ), where = 1/(1+ ) < 1. This is a contradiction to Lemma 5.1.

Let > 0 be arbitrary. By Lemma 5.2 we note that there is no polynomial (in n) algorithm (assuming the ETH) for deciding if a digraph D of order n and with s ∈ V (D) contains two arcdisjoint (s, log(n) 1+ )-branching flows. Furthermore, if c < 1/2 then there is also no polynomial algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, cn )branching flows.

6 Remarks and open problems

Analogous statements in undirected graphs

A natural question is to ask whether the analogues of our results holds for undirected graph. Some of them do. For example, the analogous statement to Corollary 3.2 is easy to show. Proposition 6.1 A graph G contains a pair of edge-disjoint s-rooted spanning trees such that s has degree at least 2 in both if and only if d(s) ≥ 4 and D contains a pair of s-rooted spanning trees.

Proof: Suppose T, T are edge-disjoint s-rooted spanning trees and s has degree only 1 in T and at least 3 in T . Let K 1 , K 2 , . . . K p be the connected components of T -s and suppose w.l.o.g that x ∈ K 1 where x is the unique neighbour of s in T . If we add the edge sy from s to K 2 in T to the tree T we obtain a cycle C. Let uv be any edge on C that enters K 2 . Then T -sy + uv and T -uv + sy are the desired spanning trees.

In contrast, the analogue of Theorem 3.1 does not hold for edge-disjoint spanning trees in undirected graphs. To see this, consider the graph G = (V, E) with V = {s, a, b, c, d} and edges E = {sa, sb, sc, sd, ab, ad, bc, cb} (so there are two parallel edges between b and c). G is the union of two spanning trees and G -{sa, sd} and G -{sb, sc} are both connected but there is no pair of spanning trees T 1 , T 2 such that T 1 contains the edges sa, sd and T 2 contains the edges sb, sc.

Still we can check for such trees efficiently using matroids. This is not new but we include the proof here for completeness. Theorem 6.2 Let p be a fixed natural number. There exists a polynomial-time algorithm for the following problem. Given an undirected graph G = (V, E) and p edge-disjoint forrests U 1 , . . . , U p ; decide whether G contains p edge-disjoint spanning trees T 1 . . . , T p such that

Proof: We show how to formulate this problem as a matroid partition problem. Given G = (V, E) and p disjoint subsets E 1 , . . . , E p of E, each inducing a forrest in G, we first define the following p subsets of E:

It is well-known and easy to show that each F i is the set of independent sets of a matroid and hence, by Edmonds' Matroid Union Theorem, the family

} is the set of independent sets of a matroid (see .e.g. [START_REF] Recski | Matroid theory and its applications in electric network theory and in statics[END_REF]). Now it follows that G contains the desired edge-disjoint trees if and only if the size of a base in the matroid M = (E, F) is p(|V | -1) -i∈[p] |E i |. Furthermore, applying the greedy algorithm for constructing a base of M we obtain either a solution or a proof that none exists in polynomial time.

The trees we will consider below are rooted at a prescribed vertex s and we say that T is s-rooted if it is rooted in s. Let us call an s-rooted spanning tree T k-safe if the tree that remains after deleting the subtree of any of the neighbours of s has at least k vertices.