Jérôme Carette

François Soleilhet

Farid Benboudjema

Xiaoyan Ma

Georges Nahas

Kamilia Abahri

Aveline Darquennes

Rachid Bennacer

Identifying the mechanisms of concrete drying: an experimental-numerical approach

Keywords: Concrete drying, relative humidity, transport properties

The loss of non-chemically linked water from concrete has a significant effect on its structural behaviour through a modification of its strength, Young modulus, fracture properties, creep and volume stability. The knowledge of the hydric state of concrete is therefore of upmost importance regarding the mechanical behaviour and durability potential of concrete structures. We use a non-linear diffusion equation for predicting the drying kinetics, including processes of the diffusion of water vapour and the permeation of liquid water. The multiple parameters of this model are then identified based on an in-house optimization algorithm and on a thorough experimental setup including measurements of mass loss and located relative humidity evolutions on various sample geometries. This coupled experimental and numerical approach allows identifying robust and meaningful material parameters of concrete used for drying predictions. This approach allows also identifying the mechanisms in concrete drying phenomena and processes by inverse analysis

Introduction

Concrete subjected to drying quickly develops strong inner gradients of water content. The loss of non-chemically linked (or free) water from a concrete has a significant effect on its structural behaviour through a modification of its strength [POP86], Young modulus [START_REF] Liu | Effect of moisture content on static compressive elasticity modulus of concrete[END_REF], fracture properties and creep [START_REF] Bažant | Drying creep of concrete: constitutive model and new experiments separating its mechanisms[END_REF]. The water loss also induces drying shrinkage [START_REF] Kim | Prediction of differential drying shrinkage in concrete[END_REF] and drying creep [START_REF] Br | Creep of concrete in compression during drying and wetting[END_REF], which induce deformation of higher magnitude than the autogenous deformation [START_REF] Zhang | Micromechanical modeling on autogenous and drying shrinkages of concrete[END_REF]. This contributes to deflection and cracking (due to drying gradients with shrinkage induced cracking, but also strains incompatibilities between cement paste and aggregates [START_REF] Bisschop | Effect of aggregates on drying shrinkage microcracking in cement-based composites[END_REF]). It also may induce prestress loss. In addition, the concrete diffusivity and permeability are highly affected by its water content [MIL61, MUA76, VAN80, HUA15, ZHA16], thus affecting its durability potential. The knowledge of the hydric state of concrete is therefore of upmost importance regarding the mechanical behaviour and durability potential of concrete structures.

The widest used measurement to characterize the hydric state of the concrete is the weight loss in drying conditions. However, this macroscopic measurement does not allow obtaining the distribution of the degree of saturation inside the specimen. Transport properties (porosity, liquid and gas permeability, diffusivity) can also be measured, but they generally suffer from hypothesis and shortcomings (cracking for instance if the material is completely dried to determine intrinsic gas permeability) that prevent these values to be used as is in a complete multi-parameter drying model. Moreover, measurements of water permeability by imposing a gradient of pressure in saturated conditions are very sensitive to the preparation of the samples (pre-dried specimens show greated "intrinsic permeability" due to drying cracks, [START_REF] Hall | Water Transport in Brick, Stone and Concrete[END_REF]). Rather, they are very powerful in order to compare different concrete compositions. This is why indirect methods are generally used to determine the moisture (or degree of saturation) gradient present in the material. These methods include electromagnetic methods [START_REF] Sbartaï | Using radar direct wave for concrete condition assessment: Correlation with electrical resistivity[END_REF], ultrasonic methods [POP05, SBA12], X-ray tomography [START_REF] Jerjen | Drying of Porous Asphalt Concrete Investigated by X-Ray Computed Tomography[END_REF], or relative humidity measurement [START_REF] Granja | Hygrometric Assessment of Internal Relative Humidity in Concrete: Practical Application Issues[END_REF][START_REF] Zhang | Simulation of moisture field of concrete with pre-soaked lightweight aggregate addition[END_REF][START_REF] Huang | Numerical simulation of moisture transport in concrete based on a pore size distribution model[END_REF]. All these possibilities are based on physical indicators that are dependent on the water content. In order to get the actual saturation degree of the material from these measurements, calibration curves are necessary. This calibration is specific to each method, and the protocol required for its determination is not straightforward. In the case of the measurement of relative humidity, obtaining the degree of saturation relies on the knowledge of desorption isotherms of the material. Even if the measurement of relative humidity (RH) is generally local and does not allow a full mapping of the water content of concrete, the advantage of this method is that concrete desorption isotherm has been widely studied in the last decades [START_REF] Xi | Moisture diffusion in cementitious materials Adsorption isotherms[END_REF]BAR07,[START_REF] Zhang | A review and statistical study of existing hysteresis models for cementitious materials[END_REF][START_REF] Zhang | Investigation of moisture transport properties of cementitious materials[END_REF]. Therefore, the determination of the saturation degree from local RH measurements is straightforward during desaturation of the material.

In any case, the experimental determination of the hydric state of concrete during drying is complex, thus justifying the many modelling approaches for the water transport in unsaturated porous media, and in particular in concrete [KIM98, MUA76, VAN80, HUA15, ZHA15, ZHA14].

In this paper, the drying of various concrete samples is cautiously studied through refined measurement of the mass loss (global measurement) and internal relative humidity distribution (local measurement). Various sample sizes and shapes are tested. From the results of these tests, the values of the model input parameters are assessed through the use of an in-house identification tool. The variation of these parameters as well as the relevance of performing combined measurements of the global and local measurements of the hydric state of concrete is discussed.

Drying model

In order to be accurate, our model includes predictive transfer equations as well as the non-linear coefficients that control the transfer, completed by realisticapplied boundary conditions.

General expression

In the concrete porosity, two main phases coexist. The solid phase and the liquid phase (liquid water and vapour water). The amount of each phase depends on parameters such as porosity, tortuosity, connectivity, ambient conditions and material saturation. These phases are not pure (presence of chloride ions for instance). Within the material, different exchanges are set up in the form of mechanisms such as permeation of liquid water as well as diffusion of the water vapour. The drying model used in this study is based on the one developed by [START_REF] Mainguy | Role of air pressure in drying of weakly permeable materials[END_REF]. It can be written in the form of a non-linear diffusion equation (equation Erreur ! Source du renvoi introuvable.) [START_REF] Baroghel-Bouny | Water vapour sorption experiments on hardened cementitious materials. Part II: Essential tool for assessment of transport properties and for durability prediction[END_REF]. The apparent coefficient of water diffusion D w is a function of the degree of saturation S, and is considered to combine two main mechanisms, which are the diffusion of water vapour and the permeation of liquid water. The water diffusion coefficient is computed according to equation Erreur ! Source du renvoi introuvable., where and are non-linear coefficient relative to the transport of liquid water and water vapour respectively. While it is known that permeation is clearly predominant for high saturation and that diffusion is predominant for low saturation, there is currently no clear consensus as to which is the predominant mechanism in intermediate saturation degrees, especially when hydraulic gradients are considered

(1)

(2) All these exchanges are considered as isotherm (latent heat of vaporization of water is not taking into account). The material is assumed to be mature and dimensionally stable (no interaction between drying and drying shrinkage). The contribution of dry air to the mass transport is neglected [START_REF] Zhang | Investigation of moisture transport properties of cementitious materials[END_REF]. If the concrete porous network is saturated, the permeation mechanism is the predominant one, whereas for a low degree of saturation, the movement of water in the form of vapour diffusion cannot be neglected. The liquid water flow can be expressed through Darcy's law, which relates the fluid mass flow through a medium to the pressure gradient of this fluid, as expressed in equation (3). In which is the concrete apparent permeability to liquid water , is the dynamic viscosity of water ( , is the water density , is the liquid water pressure ( , and is the liquid water flux .

(3)

The water vapour flow can be expressed with Fick's law, representing the flow of water in form of vapour due to a gradient in relative humidity in concrete. It can be expressed in the form of equation (4), where is the water vapour flux , is the apparent diffusion coefficient of water vapour in air , is the partial vapour pressure ( , is the molecular mass of water , is the gas constant and T is the temperature .

(4)

As shown in equation ( 5), the difference between the gas pressure P g (Pa) and liquid water pressure is the capillary pressure P c (Pa). According to Kelvin's equation, the relationship between the capillary forces and the relative humidity in concrete can be expressed as shown in equation ( 6), where h is the relative humidity, since P g is considered constant and equal to atmospheric pressure.

(

) (6) 5

Non-saturated concrete behaviour

In this model, the main unknown is chosen to be the relative humidity. This is why all further equations are expressed as function of that parameter. The desorption isotherm links the saturation degree to the relative humidity. The most common equation used to model this relationship is the van Genuchten equation [START_REF] Van Genuchten | Closed-form Equation for Predicting the Hydraulic Conductivity of Unsaturated Soils[END_REF] (equation Erreur ! Source du renvoi introuvable.), where a vg , b vg and c vg are three parameters that can be obtained from experimental results of the desorption isotherm for the tested material. A commonly used restriction is applied on the value of c vg , as shown in equation Erreur ! Source du renvoi introuvable..

(8) From combining equations (3) to (6) with mass balance principles, the equation that has to be solved for the moisture transport can be expressed as equation Erreur ! Source du renvoi introuvable., where is the concrete water porosity and P v sat is the saturation vapor pressure (Pa).

(9)

The dependency of k la to the degree of saturation can be taken into account with equation (10), where k l (m²)is the intrinsic water permeability of concrete in saturated conditions, and k rl is the relative permeability. The relative permeability can be determined through the Mualem conceptual relationship [START_REF] Mualem | A new model for predicting the hydraulic conductivity of unsaturated porous media[END_REF] shown in equation ( 11), where a mu and b mu are material parameters. Generally, the parameter a mu is considered equal to parameter c vg . While the used model considers these parameters equal, it leaves the opportunity to uncouple them during their identification process.. For cement-based materials, the recommended value for b mu is within the large range of -4 to 5.5 [MON04, LEE08, POY11, ZHO14].

(10) (11) (12) (13) In the same way, the diffusion of water vapour is highly dependent on the saturation degree. The tortuosity of the concrete porosity also affects this parameter. The empirical model shown in equation ( 13) and (13) was developed in order to take both parameters into account [START_REF] Millington | Permeability of porous solids[END_REF]. The apparent diffusion is related to the relative diffusion function and to the diffusion coefficient of water vapour in air . The parameters and can yield variable values between 1.3 and 2.74 for one and 3.3 and 4.2 for the other, respectively [START_REF] Thiéry | Modélisation du séchage des bétons -Analyse des différents modes de transfert hydrique[END_REF]. However, since these parameters are relative to the tortuosity of the material, it is to be expected that their value is depending on the concrete pore structure.

Based on the above equations, the respective contributions of liquid water permeability and water vapor diffusion to the apparent water diffusion coefficient can be expressed with equations ( 14) and (15).

Boundary conditions

Various types of boundary conditions are generally considered for modelling concrete drying. First, it is possible to impose the outdoor relative humidity directly at the air-concrete interface [START_REF] Hilaire | Etude des déformations différées des bétons en compression et en traction, du jeune au long terme : application aux enceintes de confinement[END_REF][START_REF] Oxfall | Long-term hygrothermal performance of nuclear reactor concrete containments -Laboratory evaluations of measurement setup, in situ sampling, and moisture flux calculations[END_REF]. However, this does not take into account the presence of a so-called boundary layer of air at the air-concrete interface whose moisture content depends on the distance to the concrete surface. The thickness of this boundary layer strongly depends on the ambient conditions (wind speed, temperature) and the material surface condition (surface porosity, surface roughness, and surface moisture) [START_REF] Zhang | Simulation of moisture field of concrete with pre-soaked lightweight aggregate addition[END_REF]. Generally, this boundary condition can be taken into account in the form of equation ( 16), where δ is the size of the boundary layer (in m), or more generally by equation (17) [SAK83, HUA15, ZHA15, OZB16]. The area factor reaches values varying by several orders of magnitude depending on the study. A study suggests the value of 1.5×10 -5 [START_REF] Huang | Numerical simulation of moisture transport in concrete based on a pore size distribution model[END_REF]. According to [OZB16, AKI97], its value ranges from 8×10 -7 to 2×10 -6 for w/c ranging from 0.43 to 0.55 respectively. According to other authors, it can reach much higher values in the range of 10 -3 to 10 -2 [SAK83, ZHA15].

Materials and methods

The tested concrete composition is referred to as B11 concrete. Three sample geometries for different drying patterns are placed in a storage bin and mass loss and relative humidity are recorded regularly. With the experimental data obtained in this study, a finite element simulation is performed and an identification procedure is developed on Matlab to find out the optimised parameters.

3.1.Concrete composition

The composition of B11 concrete and major properties are shown in Table 1. It has been widely studied in previous studies [START_REF] Briffaut | Numerical analysis of the thermal active restrained shrinkage ring test to study the early age behavior of massive concrete structures[END_REF][START_REF] Hilaire | Etude des déformations différées des bétons en compression et en traction, du jeune au long terme : application aux enceintes de confinement[END_REF] and its mechanical properties are therefore mostly known, including its density and water porosity. The mixing procedure is as follows : the dry materials (aggregates, sand and cement) are mixed for 60 seconds. Then, water and 1/3 of the superplasticizer are added with further mixing during 150 seconds. Then, the rest of the superplasticizer is included, followed by 90 additional seconds of mixing. 30L of concrete were mixed in one batch.

3.2.Test setup

In order to ensure the same controlled curing conditions to all concrete specimens (temperature T and relative humidity RH), a large storage bin is developed. The use of a climatic chamber is rejected due to the difficulty of limiting the forced convection on the faces subjected to drying, and of ensuring the uniformity of this phenomenon on all sides and on all samples. The storage bin is impermeable to air and moisture.

Figure 1. Experimental setup linked to the continuous measurement of RH and T sensors

In order to enable placing several temperature and relative humidity sensors inside the storage bin, holes are performed, and sealing plugs are installed. The concrete samples are placed on a plastic honeycomb duckboard allowing maximized interaction between the salt solution and the ambient air. This setup is shown in Figure 1. The saturated salt solution is prepared using potassium carbonate in order to reach an ambient RH of 45%. The room temperature is controlled at 25 ± 1°C (this has been checked using the probes).

The concrete samples are prevented from drying until the test starts, which occurred two months after mixing. Due to the high w/c ratio of the B11 concrete, weconsider that the hydration reactions are almost completed and that the auto-desiccation phenomenon can be neglected [START_REF] Briffaut | Numerical analysis of the thermal active restrained shrinkage ring test to study the early age behavior of massive concrete structures[END_REF]. The initial state of the material is therefore not fully saturated, but with a very high saturation degree due to the high w/c ratio of the B11 concrete.

The experimental measurements consist in mass loss measurements at regular intervals and of the internal relative humidity in concrete samples at various distances from the drying interface. Three sample geometries are considered (see Figure 2):

-G1: 70x70x280mm prism, drying on the two opposite lateral faces (5 samples), -G2: 70x70x110mm prism, drying on the two opposite lateral faces (3 samples), -G3: 70x110mm cylinder, drying in the radial direction (3 samples),

For each of these geometries, the average drying radius (r d , in m) is computed as the ratio between the drying surface and the sample volume. This results in r d of 0.14, 0.055 and 0.0275 and for geometries G1, G2 and G3 respectively.

The mass loss measurements are performed on 3 samples for G1 and on 2 samples for G2 and G3. This study focuses on the first few weeks after drying is initiated. The relative humidity is measured at various distances from the drying interface on geometries G1, G2 and G3 according to the distribution shown in Figure 2. The used sensors are capacitive probes Ahlborn FHA 646 R. These probes are chosen due to their extremely small dimensions (5 mm diameter) as well as their high accuracy and wide operating RH and T range. The RH sensors are placed inside concrete through holes drilled on hardened concrete. This method is considered more appropriate than reservations in concrete from the casting since the latter results in a layer of mortar around the hole that is not representative of the tested material. In order to avoid damaging the sample, 6 mm diameter holes are obtained by drilling with progressively increased diameter from 3 mm to 6 mm.

All sensors are placed in 30mm deep reservations obtained by perforation of the hardened concrete. Sensors are placed in the centre of each sample. In geometry G1, additional sensors are placed at 15, 30, and 60 mm from each drying interface. In geometries G2 and G3, two additional sensors are placed at 15 mm from the drying interface. Figure 2. Layout plan of RH sensors (sides submitted to drying displayed in red : two opposite lateral faces for G1 and G2, drying in the radial direction for G3)

3.3.Identification procedure

In this study, an identification procedure based on Finite Element Modelling Updating (FEMU) [START_REF] Neggers | Time-resolved integrated digital image correlation[END_REF] was developed using Cast3m [START_REF]Description of the finite element code Cast3M[END_REF] and Matlab. This method (FEMU) is based on the minimisation of an error function built with the difference between data gathered from experimental work and numerical results. The identification flow chart is presented in Figure 3.

It can be divided into three parts. The first is related to the experimental data obtained in this study. Then, a second part is related to the FE simulation. The last part is associated with the minimization algorithm, developed on Matlab. Figure 3.

Identification algorithm flow chart

This inverse modelling relies on a priori knowledge of the drying model and its ability to accurately predict the drying process. In this case, the used numerical model was presented in section 2. Thus, the experimental process is simulated with relative humidity and temperature as boundary conditions of the modelling. It is then possible to build an error function, shown in Eq.

(18). This error function includes experimental data (indicated by the e exponent), simulated data (indicated by the s exponent), as well as results from mass loss measurements (indicated by the ML index) and from relative humidity measurements (indicated by the RH index). This function ensures that:

-More relative importance is assigned to higher mass loss or lower relative humidity, -The same relative importance is assigned to mass loss resulting from one sample and to relative humidity measurements resulting from one sensor, -Several samples or sensors for the same measurement can easily be included independently from one another in the identification process.

(

) 18
where C e and C s are the vectors of experimental and modelling results for respectively the relative mass variation (ML) and the relative humidity values (RH). is a vector composed of model's input parameters. It is possible to add weighting factors in this error function.

Finally, the minimisation is calculated, based on Levenberg-Marquart's optimisation method implemented in Matlab. The framework of the algorithm is presented in Figure 4. The minimized parameters resulting from this process are entered in CAST3M as input parameters. The identification runs until it reaches a criterion based on the average relative increment of the identified parameters increments. If this average variation remains below the limit of 0.1% of the current parameters' values, the identification procedure is stopped.

Lastly, as our experimental work involves different shapes and dimensions, it is possible to diversify the identification process. Indeed, the process allows for identification of one or more shapes, and allows taking into account relative mass loss and relative humidity at the same time or separately.

Results

In this section, the measurement results of mass loss and relative humidity, as well as identification of model parameters is analysized.

4.1.Mass loss and relative humidity measurements

The mass loss (ML) due to water drying and the relative humidity (RH) evolution resulting from water transport are presented hereafter. First, it was verified that the RH sensors provide reproducible results, and that their presence does not affect the overall ML of drying samples. In order to do so, three G1 samples without drilled holes were tested in parallel with two G1 samples with drilled holes and RH sensors. The results shown in Figure 5(a) indicate that the variability on the ML measurement is low, and that the presence of the sensors do not affect the ML measurements. Mass loss being defined as a decrease of the mass through time, it is displayed as a positive value when drying occurs. On the other hand, the RH measurements are more variable, as displayed in Figure 5(b). This is most likely due to the heterogenous aspect of the concrete, for which the drilled holes (6 mm diameter, 30 mm depth) might be in contact with a variable amount of aggregate/mortar ratio. In addition, the presence of a large pore filled with water close to the drilled hole might locally affect the RH. Finally, local temperature gradients or discrepancies in the paricule size distribution can also contribute to these variations. However, the general trend shown by all sensors is consistant, and the reproducibility of the measurement is satisfactory for the purpose of this study.

The mass loss observed in Figure 6(a) shows a very high dependency on the geometry. As the drying radius increases (meaning that the average distance between the free water and the drying interface increases), ML increases in a more slow and progressive way. Figure 6(b) represents ML as a function of the square root of time. In the first days after samples are submitted to drying, ML increases as a linear function of t d 0.5 , which is representative of processes that can be described by a diffusion-like differential equation. As drying occurs, the concrete saturation degree decreases. This leads to a variation of the transport properties of the material, and thus to the non-linear behaviour observed after a few weeks in G2, and after a few days in G3. This process is actually more visible in Figure 6(c), where ML is multiplied by the sample drying radius. This confirms that the initial slope of the ML-t d 0.5 curve is independent on the geometry, and only depends on the material transport properties. This slope is therefore affected both by the concrete mix design and by its initial saturation degree. Then, as the drying radius decreases, the drying occurs faster, thus leading to a decrease of the transport properties, and therefore to a decrease of the rate of ML. This observation can also be observed in Figure 6(d), in which ML is represented as a function of the square root of time divided by the drying radius. This figure actually shows that for a given mass loss, the rate of drying depends mostly on the time and drying radius. However, the G1, G2 and G3 curves are not superimposed, suggesting that the gradient of saturation degree inside the material also affects the drying behaviour. This observation highlights once again the importance of being able to measure and predict the water distribution inside the material in addition to global information such as mass loss measurements. Figure 7. RH measurement inside the material at 36, 43 and 57 days as a function of the distance from the drying interface for geometry (a) G1 (b) G2 and (c) G3

Local RH measurements are performed in geometries G1, G2 and G3 at various distances from the interface. The results of these measurements are shown in Figure 7(a), (b) and (c) respectively. Only measurements when all sensors provide RH values under 95% are presented. This is due to the risk of condensation on the sensors for higher RH values, and to the limited accuracy of the sensors in such high RH environment. However, based on these measurements, it is considered that the RH in the centre of G1 is saturated through the whole experiment (3 months). This is represented by the dashed lines in Figure 7(a) between a distance of 60mm and 140 mm. In the same way, for representation purposes, it is considered in this section that the RH at the surface of the samples is equal to the RH of the ambient air, which is fixed at 45% through the whole test.

The results of Figure 7 show as expected that the RH profile decreases in proximity with the drying interface, due to the initially high humidity gradient between the concrete and the ambient air. Similarly, the RH profile decreases as the drying time increases. This phenomenon occurs in every point of all geometries. Finally, as expected, at a given distance from the drying interface, at a given drying time, the local RH value is lower as the drying radius decreases. This is explained by the lower water supply of the core of the sample as the drying radius decreases, thus resulting in a lower RH for a similar amount of evaporated water. For instance, at 36 days, G2 shows an overall lower RH at 15 mm from the drying interface than G1. In the same way, G3 has a lower RH than G2 at 15 mm from the drying interface. The core RH of G3 is lower than the core RH of G2 even though both sensors are situated at the same distance to the surface due to the fact that G2 is a prismatic sample drying from the two opposite surfaces, whereas G3 is a cylinder drying from its whole circumference. This confirms the important effect of the drying radius.

4.2.Identification of model parameters

The model described in section 2 is implemented in the CAST3M finite element software. The geometries are meshed with discretisation along the x-axis. More elements are placed in direct proximity with the drying interface due to the higher humidity gradient in that area. The meshing of G1 is given as an example in Figure 8, where only half of the prism is meshed since the test is symmetrical. The RH value is computed as the average value of the elements related to the position of the corresponding sensor S1, S3 or S3. Due to the large number of parameters in the drying model, several solutions can be found, all of them satisfying the mass loss curves of G1, G2 and G3. This is the case of sets of parameters P1, P2 and P3 (Table 2), all of which provide good superimposition of the experimental curves. However, the mass loss being a global measurement, it is shown in Figure 9 The developed identification algorithm is used in order to evaluate the effect of various experimental or simulation parameters on the identified parameters. The evaluated parameters are the specimen geometry, the input parameters of the identification, the chosen model for the relative permeability function, and the temperature. This evaluation is made through comparison of the identified apparent coefficient of water diffusion D w . For each case, this property is described as a function of the relative humidity, as well as its two contributing factors K l and D v .

Effect of specimen geometry

From a macroscopic phenomenological perspective, it is observed experimentally that the drying process is independent of the specimen geometry. For a given concrete, as the average drying radius decreases, the global mass loss decreases faster. The difference between G1, G2 and G3 observed in Figure 6 mostly come from the fact that a faster drying induces change in the transport properties due to the faster decrease of the water saturation. However, the geometry does not affect the model parameters themselves. Therefore, the developed algorithm should yield the same identified parameters, whatever the considered geometry. In order to verify this, identification is performed successively on the experimental results of mass loss and relative humidity of G1 (P5-1), G2 (P5-2), G3 (P5-3) as well as on all results simultaneously (P5). Since the latter considers all experimental results, P5 is most likely more representative of the concrete drying behaviour. The input set of parameters for these identifications is P1. Tables 3 lists the different parameters identification trategies. It is observed in Figure 11(a) that a lower drying radius results in a better identification of the drying model parameters. This is expected, since the same experiment duration was applied to all geometries. As a result, low relative humidity has already been reached in G3 at a time when G1 has higher water saturation. P5-1 exhibits a significant difference with the other parameter sets.

c vg = 1-1/b vg = 1-1/b vg = 1-1/b vg = 1-1/b vg = 1-1/b vg = 1-1/b vg = 1-1/b vg = 1-1/b vg a mu = c vg = c vg = c vg = c vg = c vg = c vg = c vg = c
We explain this by the fact that G1 exhibits the least advanced drying state, which makes it less reliable for determining the model parameters. For the test duration of this study (3 months), G3 is obviously more representative of the overall drying process than G1, due to its more advanced drying state. In almost all cases except P5-1, the liquid water transport mechanism is predominant, even for low relative humidity. As mentioned previously, the reason why set of parameter P5-1 deviates from this trend is due to its lower drying state. Interestingly, the identified set of parameters P5-2 and P5-3 show a similar Dw-RH curve, indicating similar global drying physics. However, the parameters at the origin of this behaviour are quite scattered. For instance, there is a one order of magnitude difference between the intrinsic water permeability kl of P5 and P5-3 (Table 2). This is fundamental, as it still shows that although the physics are quite correctly captured by our identification tool, there are still several possible parameter sets that can yield this physical behaviour. This is why we include all 3 geometries in our reference parameter set P5.

Finally, it should be mentioned that the identified parameters P5 are within the range of values that can be found in the literature. In particular, the h CL coefficient of 1.4x10 -5 is close to the value obtained from experiments [START_REF] Carette | Analysis of drying in concrete: effects of boundary conditions and specimen size/shape[END_REF]; the a mq and b mq are consistent with what is expected from cement-based materias [START_REF] Zhang | Investigation of moisture transport properties of cementitious materials[END_REF]; b mu is within the range suggested by [START_REF] Hilaire | Etude des déformations différées des bétons en compression et en traction, du jeune au long terme : application aux enceintes de confinement[END_REF]. And more importantly, the desorption isotherm represented by parameters a vg , b vg and c vg is close to the experimental results for this concrete obtained by Belin et al. [BEL09]. This indicates that the identified solution is satisfactory both from the phenomenological and theoretical perspective. In order to fully validate the reliability of this approach, the desorption isotherm as well as relative hydraulic conductivity curves could be compared with experimental data. In order to be fully relevant, this further step should be addressed with various concrete compositions in a thorough study, and will be the object of further work.

Effect of initial parameters

In order to verify the robustness of the identification method, the effect of the input parameters on the identification output is studied. From these results, it can be considered that according to the used drying model, and considering the mass loss and relative humidity measurements, the best fitting parameters (P5) are mostly independent on the input parameters. This unicity of solution confirms the relevance of the applied methodology.

Effect of relative permeability, relative diffusivity and desorption isotherm model

In order to study the relevance of the developed identification methodology, a last step consists in comparing different models for the relative permeability, relative diffusivity, and desorption isotherm.

Regarding the relative permeability model, four different approaches are considered. The first option consists in applying the default model, as described previously in equation ( 11). This model (relative permeability model 1) consists in 2 parameters to identify. The second option consists in using the same equation, but with one parameter less to identify, considering the approximation that a mu is considered equal to parameter c vg (relative permeability model 2). A third model is used, based on the work of Chung and Consolazio [START_REF] Chung | Numerical modelling of transport phenomena in reinforced concrete exposed to elevated temperatures[END_REF], wherein a single parameter ( ) connects the relative permeability to the degree of saturation equation (19-20) (relative permeability model 3). Finally, a fourth possibility, also suggested by Chung and Consolazio, is particularly interesting because it involves no additional parameter to the model. It consists in fixing the value of as a function of the porosity of the material according to equation (21) (relative permeability model 4).

Three relative diffusivity models are considered. The first one is the default model (relative diffusivity model 1). The second one is based on the same principle (equation ( 13)), except that only one parameter is used instead of two, with the assumption that , as recommended by the authors of that model (relative diffusivity model 2) [START_REF] Millington | Permeability of porous solids[END_REF]. Finally, the third model, shown in equation ( 19), is used whenever combined with relative permeability models 3 or 4, as recommenced by Chung and Consolazio (relative diffusivity model 3). This last model has the advantage of not adding parameters to the identification. Ultimately, the desorption isotherm model is either used by default (desorption isotherm model 1) or by applying the assumption specified in equation ( 8). This simplification decreases the amount of parameters to identify (desorption isotherm 2).

The result of this multi-model identification is presented in Figure 13. Due to the large amount of combination of models, only the resulting hydraulic conductivity and saturation degree functions are presented, without the corresponding identified parameters. The nomenclature is as follows:

corresponds to the relative permeability model , combined with relative diffusivity model , and desorption isotherm model .

As previously specified, the measured values of relative humidity do not go under 45% RH, which corresponds to the ambient relative humidity. Therefore, the identification of parameters is only relevant for RH values between 45% and 100%. This is why in Figure 13, lower RH values are shaded in gray, indicating that these values are actually not validated by our experiments. Figure 13 shows that whatever the model used among the various ones presented, the identified parameters correspond to a unique and relationship. At least, this is verified within the RH range that was measured experimentally. First, this indicates that the various models are versatile enough to represent the same physical reality. However, the relative contributions of vapour and liquid water transport to the hydraulic conductivity shown in Fig 13 (c) are largely affected by the relative permeability model. Indeed, models 3 and 4 (Chung and Consolazio [START_REF] Chung | Numerical modelling of transport phenomena in reinforced concrete exposed to elevated temperatures[END_REF]) induce a large increase in the contribution of the vapour diffusion to the hydraulic conductivity. On the other hand, the relative permeability and relative diffusivity models do not affect these respective contributions. This observation is of major importance as it shows that our current approach still requires more experimental data in order to be fully robust, especially in terms of the specific underlying mechanisms of drying in concrete.

There is therefore no preferential model among the ones who were tested, nor an optimal combination of these models. Without further validation, no model can be preferred on the basis of its predictive ability. Therefore, it seems that the model containing the least amount of parameters to identify could be preferred. Secondly, this further supports that the identification strategy that was developed in this study is robust, and yields satisfactory solutions corresponding to a global minimum of the weighed error function. The developed methodology therefore allows identifying robust and meaningful material parameters of concrete used for drying predictions.

Conclusion

An identification procedure for material parameters of a concrete drying model is proposed. It consists in performing a simultaneous measurement of mass loss due to the drying process as well as localised successive measurements of the relative humidity. This experimental setup is coupled with a developed identification tool able to handle several identification parameters with a specific weighed error function, combining both type of experiments. The numerical model is based on a non-linear diffusion-type model including two phenomena: liquid water permeation and water vapour diffusion. This coupled experimental and numerical approach allows identifying robust and meaningful material parameters of concrete used for drying predictions by inverse analysis.

The following conclusions are drawn:

-As expected, the mass loss measurement is not sufficient to identify the drying model parameters, since there is no unicity of solutions in regard of the amount of parameters to identify. This highly supports the necessity to include relative humidity measurements in the identification process. -If both experimental indicators are used in the identification, the resulting material parameters are similar, whatever the experimental specimen geometry is used. Therefore, when aiming at quantifying the drying process of a new type of cement-based material, the experimental specimen geometry (and environment) should be chosen in order to accelerate as much as possible the drying process. -If both experimental indicators are used in the identification, the resulting material parameters are independent on the input parameters. In regard of the large amount of parameters used in the identification, this shows that the solution is robust, and does not correspond to a local optimum. -Several models are used and combined for the prediction of relative permeability and diffusivity, as well as for desorption isotherm curves. Whatever the tested combination, it is shown that the shape of the identified hydraulic conductivity and desorption isotherm is equivalent. There is therefore no preferential model among the ones which were tested.

Figure 4 .

 4 Figure 4. Minimisation algorithm

Figure 5 .

 5 Figure 5. (a) Maximum, minimum and average values of relative mass loss for 5 G1 samples, with and without RH sensors (b) Maximum, minimum and average value of the RH measurement at three different distances from the drying interface from 3 G1 samples

Figure 6 .

 6 Figure 6. Mass loss of G1, G2 and G3 geometries expressed by (a) ML as a function of time (b) ML as a function of square root of time (c) ML multiplied by drying radius as a function of square root of time and (d) ML as a function of square root of time divided by drying radius

Figure 8 .

 8 Figure 8. Meshing of G1 in the CAST3M softwareIn a first stage, inputs parameters for the model are extracted from the recommendations of the thesis A. Hilaire[START_REF] Hilaire | Etude des déformations différées des bétons en compression et en traction, du jeune au long terme : application aux enceintes de confinement[END_REF], who worked on the same concrete. In addition, an exchange coefficient h CL is chosen as equal to 10 -5 . This value is extracted from previous research based on the coupled measurement and modelling of the surface RH of concrete during drying[START_REF] Carette | Analysis of drying in concrete: effects of boundary conditions and specimen size/shape[END_REF]. Finally, the intrinsic permeability of concrete is manually modified in order to ensure a superimposition of the model mass loss in comparison with experimental values. A value of k l of 1.13x10 -21 m² is thus determined. This set of parameter (P1) is shown in Table2, and results in the model-P1 curves in Figure9(a) and (b).

  (b) that these three sets of parameters do not provide the same hydraulic profiles inside the material. From a strictly modelling perspective, this is understandable, since a given saturation degree history (equivalent to the local distribution of the mass loss in the material) can result in variable relative humidity profile only by modifying the desorption isotherm values a vg , b vg or c vg . This observation justifies the need to include additional experimental measurements in the parameter identification process. Indeed, based on the coupled measurement of the mass loss and RH at 15mm and 55mm from the drying interface, a new set of parameters can be determined (P4). This set of parameter provides an overall better representation of both measurements (Figure1010(a) and (b)).

Figure 10 .

 10 Figure 10. Experimental values and corresponding simulation of G3 for two sets of parameters P1 and P4 (a) mass loss and (b) relative humidity at 15 and 55mm from the drying interface

Figure 11 .

 11 Figure 11. identification results considering only G1, G2, G3 or all of them (a) apparent coefficient of water transport as a function of relative humidity (b) diffusion to permeation ratio as a function of relative humidity This observation is confirmed in Figure 11(b), describing the identified D v /K l ratio as a function of relative humidity. A D v /K l ratio equal to 1 indicates that water vapour diffusion and liquid water permeation are present in equal proportions.In almost all cases except P5-1, the liquid water transport mechanism is predominant, even for low relative humidity. As mentioned previously, the reason why set of parameter P5-1 deviates from this trend is due to its lower drying state.

  Three different cases are confronted to the reference output parameters set P5. Each one of these cases (P6-1, P6-2 and P6-3) is chosen in order to represent different water transport mechanisms. P6-1 corresponds to a large decrease of D w , P6-2 corresponds to an increase of D w , and P6-3 consists in lower D w for high RH combined with higher D w for low RH. The hydraulic conductivity resulting from these three sets of parameters are represented in Figure12(a), showing the wide variety of transport mechanisms considered.

Figure 12 .

 12 Figure 12. (a) hydraulic conductivity functions corresponding to three input sets of parameters and a reference set of parameter P5 (b) identified diffusion to permeation ratio as a function of relative humidity The parameters corresponding to Figure 12 are displayed in Table 4. The output values are all very close to the reference case P5. The identified values of k l , a vg , b vg and h CL can be considered as independent from the input parameters. The main difference between the three identification scenarios is situated in the water vapour diffusion coefficient D v . This explains the wide variations in Figure 12 (b), while the identified D w is almost identical from P6-1, P6-2 and P6-3.The variability of D v comes from the fact that its contribution is very low in the RH range corresponding to the measurements (over 45%). Therefore, the sensitivity of parameters a mq and b mq is very low and is therefore not reproducible in comparison with the Van Genuchten equation parameters.

Figure 13 .

 13 Figure 13. (a) hydraulic conductivity functions corresponding to the identified parameters from various model combinations (b) saturation degree prediction for various model combinations (c) identified diffusion to permeation ratio as a function of relative humidity

Table 1 .

 1 B11 mix design and main properties[START_REF] Hilaire | Etude des déformations différées des bétons en compression et en traction, du jeune au long terme : application aux enceintes de confinement[END_REF]

		B11 [kg/m³]	w/c	[-]	0.573
	Cement (CEM II Airvault Calcia)	336	ρ	[kg/m 3 ]	2324
	Sand (0/4)	740	Slump	[cm]	8-11
	Aggregates (4/12.5)	303	Porosity	[-]	13.2-13.8
	Aggregates (10/20)	752	f c (28 days)	[MPa]	46.5
	Water	193	f t (28 days)	[MPa]	3.29
	Superplasticizer (Plastiment HP)	1.174	E (28 days)	[GPa]	31.34

Table 2 .

 2 Drying model parameters

		P1	P2	P3	P4	P5-1	P5-2	P5-3	P5
	k l	1.13E-21 1.25E-22 9.01E-22 1.54E-20 1.00E-19 9.57E-21 3.81E-21 4.68E-22
	a vg	4.00	1.96	100.00	10.00	6.76	6.51	5.87	2.42
	b vg	1.67	2.04	1.22	1.21	1.14	1.19	1.28	1.65

Table 3 .

 3 Different parameter identification strategies

	P1	P2	P3	P4	P5	P6	P7
	parameter set based from A. Hilaire [HIL14], complying with ML evolutions	manually modified parameters that comply with the ML evolution	manually modified parameters that comply both with ML and RH evolutions from G3 geometry	algorithm-identified parameters complying with ML and RH for all tested geometries	input : variable input parameters corresponding to different transport mechanisms / output : result of the identification	parameters resulting from various relative permeability, relative diffusivity and desorption isotherm models

Table 4 .

 4 Selected input and resulting identified (output) drying model parameters

	P5	P6-1 input P6-1 output P6-2 input P6-2 output P6-3 input P6-3 output

Acknowledgments

The authors would like to thank the IRSN for the financial support.

-The relative contribution of vapour and liquid water transport is strongly dependent on the chosen relative permeability model.

Further works are required to confirm the relevance of this model for longer term experiments, as well as additional results regarding the relative humidity gradient inside the samples. This will allow a complete description of these phenomena, also an improved strategy for identifying the parameters of the model. Besides, effects of modelling choice and different relative humidity profiles, leading to the same weight loss prediction, on drying shrinkage cracking and apparent gas permeability are currently studied. This type of study could be also undertaken on the prediction of apparent diffusivity and swelling reaction (ASR, DEF for instance), which are very dependent on water content.


Keywords: Survivability, fault tolerance, reliability, Shared Risk Resource Group, colored graphs, complexity, approximability, shortest paths, cuts

This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow -Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.

Introduction

Network survivability, as an application domain, has fostered a large scope of theoretical and algorithmic developments is the recent years. Although neglected for a long time by survivable network design studies, multiple failures scenarios are now unavoidable with the spread of multilayer networks such as IP/WDM, MPLS networks, P2P or GRID computing overlay structures. For example, in such a multilayer network, multiple and apparently independent virtual links may be paths sharing a link on the underlying network, as illustrated in Figure 1 of the link (FG) would induce multiple failures on the set of links of the virtual topology. Therefore, the need to take into account correlations between edges has appeared, and the concept of Shared Risk Link Group, later generalized to Shared Risk Resource Group (SRRG) [START_REF] Chiu | Issues for routing in the optical layer[END_REF][START_REF] Papadimitriou | Inference of shared risk link groups[END_REF][START_REF] Sebos | Auto-discovery of shared risk link groups[END_REF], has been introduced. A SRRG is a set of resources breaking down simultaneously when a given failure occurs.

In addition to their application in telecommunication networks survivability issues for which they have been introduced, Shared Risk Resource Groups are relevant to numerous practical settings. Indeed, they can model correlated traffic jams of road networks, as well as cascading failure scenarios in electrical networks. Related concepts are also relevant in the settings of cryptographic PGP (Pretty Good Privacy) keyrings [START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF].

Many classical network survivability issues are modeled as graph covering problems in which a minimum cost subset of edges satisfying some given property is to be found. The cost of such solutions is generally the size of the set, or a linear function such as the sum of the cost of the edges. Examples of such problems are minimum cost spanning tree, minimum cut and shortest paths problems. These problems model applications in which edges fail independently.

This article focuses on the counterpart of such classical problems in the settings of Shared Risk Resource Group. In the general case, a Shared Risk Resource Group may include links (edges) and nodes (vertices) of the network. However, using straightforward graph transformations, without loss of generality one can consider only sets of edges.

Shared Risk Resource Groups are naturally modeled by associating to each group (or risk) a color, and to each edge (or resource) the colors representing the risks affecting it [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF][START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF]. According to the general case of Shared Risk Resource Groups, an edge may belong to several colors, modeling the fact that a resource may face different and independent risks. In [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF], a colored graph is thus defined as an undirected graph associated to a set of colors. Each color is a subset of edges and the colors cover the edge set.

However, depending on the context, this property may be interpreted in several ways whether an edge fails when a single of its colors fails or when all its associated colors fail simultaneously.

That is why another definition for colored graphs is presented in [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF]. In that case to each edge is associated a single color (the colors then partition the edge set). According to the context, a graph transformation can be applied to a colored graph of the first model to obtain a colored graph of the second model. If in the first model an edge e fails when at least one of its λ colors fails, we replace edge e by a path with λ monochromatic edges. Thus, in the second model, any path containing edge e will fail for any failure of one of its λ colors. Figure 1 1(a) is routed through the physical links (AF), (FG) and (GH), it is therefore replaced with a path of three monochromatic edges. The colors of these edges are the colors associated to the physical links (AF), (FG) and (GH). The creation of this path requires the creation of two vertices x and y. If in the first model an edge e fails only when all its colors fail, this edge is replaced with λ monochromatic parallel edges.

Therefore, in the following we assume that edges are monochromatic, in other words colors not only cover the edge set but also partition it. This definition is actually encompassed in the definition of [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF], consequently all the NP-hardness and inapproximability results proved under the monochromatic assumption extend to the more general settings of [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF].

Definition 1.1 (Colored graph) A colored graph is a triple G = (V, E, C) where (V, E) is an undirected graph and C is a partition of E.
In a colored graph, a color containing an edge incident to a vertex is said to be incident to this vertex. Two colors are adjacent if they are incident to a same vertex. The colored degree of a given vertex is the number of colors which are incident to it.

The span of a color is an important parameter of a colored graph since the complexity and approximability properties of most of the following optimization problems depend on the maximum span of the graph. Definition 1.2 (span of a color) The span of a color is the number of connected components of the subgraph induced by the edges of this color.

An example is given in Figure 2 where color c 1 has span 2 (Fig. 2 The counterparts in colored graphs of the classical graph problems consist of finding a minimum cost set of colors satisfying a given property. For example a colored path is defined as a subset of colors whose corresponding edge set contains a usual path (Fig. 2(e)). Note that the edge set corresponding to a given colored path may contain more than one usual path. Nevertheless, a usual path is associated to a single colored path. In the following we use both ways to define a colored path, either as a set of colors, or as a usual path whose edges are colored. We can define a colored st-cut (Fig. 2(d)), a colored cut, a colored spanning tree (Fig. 2(f)) in the same way as we have defined a colored path. Then we define the following optimization problems motivated by network survivability issues.

The Minimum Color st-Path problem (MC-st-Path) consists of finding a path between vertices s and t using as few colors as possible and is NP-Hard [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF], which is the same as a colored path containing a minimum number of colors. This problem is related to finding a path of minimum failure probability. Furthermore, unlike classical graph shortest path, a subpath of a MC-st-Path is not necessarily a minimum color path. The set of color {c 1 , c 4 } is minimum color st-path in the depicted in Figure 3. There is a single classical path in the subgraph induced by these colors, this path is (s, y, w, x, v, t). However the color c 3 is a minimum color sw-path unlike the set {c 1 , c 4 }.

The 2-Color Disjoint st-Paths problem (or diverse routing problem [START_REF] Bhandari | Survivable Networks: Algorithms for Diverse Routing[END_REF]) consists of finding two paths between a pair of vertices in a graph using distinct color sets, therefore no Shared Risk Resource Group failure cause both paths to fail. Unlike the traditional edge or vertex disjoint paths problem in graph theory, this problem is NP-complete [START_REF] Hu | Diverse routing in mesh optical networks[END_REF]. It follows that minimizing the total number of colors of 2-Color Disjoint st-Paths is difficult. Moreover, it has been shown in [START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF] for a cryptographic application, that the problem Maximum Number of Color Disjoint Paths consisting in finding the maximum number of color disjoint st-paths connecting two vertices is also NP-Hard.

When no two color disjoint st-paths exists, a set of Minimum Overlapping Color st-Paths, that is a set of st-paths sharing a minimum number of colors, is of specific interest in survivable network design. It represents protection paths in a failure dependent protection scheme [START_REF] Mohan | Lightpath restoration in WDM optical networks[END_REF]. A variation of this problem, consisting of finding two edge disjoint st-paths minimizing the number of shared colors, has been studied in [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF] and shown to be NP-Hard.

The Minimum Color st-Cut problem (MC-st-Cut) consists of finding a minimum size set of colors disconnecting two vertices s and t. Similarly, we can define a Minimum Color Multi-Cut (MC-Multi-Cut) as a minimum size set of colors whose removal disconnects simultaneously several pairs of given vertices {s 1 , t 1 } . . . {s k , t k } and a Minimum Color Cut (MC-Cut) as a minimum set of colors disconnecting the graph in at least two parts. Note that as in classical graphs, the size of a MC-Cut is upper bounded by the minimum colored degree which is the minimum number of colors used by the edges adjacent to a vertex. Colored cut problems are related to the vulnerability of multilayer networks since they give tight lower bounds on the number of failures that can disconnect totally or partially a network.

The Minimum Color Spanning Tree problem (MC-Spanning Tree) consists of finding a minimum size set of colors containing a connected spanning subgraph, as depicted in Figure 2. A MC-Spanning Tree is a set of Shared Risk Resource Group whose availability guarantees the connectivity of a network. The complexity and approximability properties of this problem are detailed in [START_REF] Chang | The minimum labeling spanning trees[END_REF][START_REF] Krumke | On the minimum label spanning tree problem[END_REF][START_REF] Wan | A note on the minimum label spanning tree[END_REF].

In Table 1 we sum up the main results obtained for colored problems. The results with no references are going to be proved in this paper. The weak relations between Color Disjoint st-Paths and MC-st-Cut (analogous to min cut equals max number of edge disjoint paths) are investigated in Section 2. Section 3 is dedicated to cases when the colored problems are polynomial, while Section 4 investigates complexity and approximability of colored problems when the span of colors is bounded by a constant k. Finally Section 5 presents an approximability preserving reduction from the Minimum Label Cover problem to the MC-st-Cut and MC-st-Path problems when there is no restriction on the span of colors.

Relations between problems

In this section we show through examples that colored problems differ from classical graph theory, not only by their complexities, but also by their mutual relationships. In particular this is the case for the number of color disjoint st-paths and the MC-st-Cut no longer tightly linked. The max flow-min cut relation being essential in the study of network reliability, this result makes the Color Disjoint st-Paths problem even more thorny and stresses the interest of the Min Overlapping Color st-Paths problem [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF].

The sizes of a MC-Spanning Tree and a MC-Cut do not either verify the same inequalities as their classical counterparts [START_REF] Frank | Connectivity and Network Flows, volume 1 of Handbook of combinatorics[END_REF].

Theorem 2.1 For each k ∈ N, there is a colored graph with two vertices s and t such that the MC-st-Cut has value k, while the graph does not contain two color disjoint st-paths.

Furthermore, this colored graph is also such that the MC-Cut has value k while the graph does not contain two color disjoint spanning trees.

Proof: Let k ∈ N be a constant. We construct a colored graph G containing 2k k + 1 vertices and 2k colors. G is built from a path of length 2k k where each edge is associated with exactly a one subset of k colors. Then we replace each edge of this path by k edges with the k colors of the associated subset, see Figure 4 for k = 2. Let s and t be the extremities of the path. A colored spanning tree in G is merely a colored st-path and a MC-Cut is actually a MC-st-Cut.

Assume there is a colored st-path using l ≤ k colors. Then there is a subset of at least k colors not used by the path; that implies that the path does not contain any of the multiple edges associated to this subset of colors, and leads to a contradiction. Therefore a colored st-path uses at least k + 1 colors. Since there are only 2k available colors, Theorem 2.1 follows.

Other families of colored graphs exist for the first part of Theorem 2.1, for example we can construct a family of graphs containing k 2 colors and 2k 2 edges in which a MC-st-Cut uses k colors while no pair of color disjoint st-paths can be found. NP-Hard [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF] NP-Hard [START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF] NP-Hard [START_REF] Chang | The minimum labeling spanning trees[END_REF] general non approx ) -ε for ε < 1 2 , ---= do not apply. Note that an upper bound on the ratio maximum number of color disjoint st-paths/ MC-st-Cut, depending on the size of the colored graph, may exist, that is why it may be interesting to find families of colored graphs in which the usual relations do not hold and for which the number of colors and the size of the graphs are known. Note also that when the number of colors of the graph equals the MC-st-Cut value, then there is at least one st-path of each color.

Min. Color

• • • st-Path st Multi        -Cut Cut 2-Disjoint st-Paths 2-Min Overlap.
2 log 1-δ |C| 1 2 2 log 1-δ |C| 1 2 ? --- ? ∀ε > 0, |V |
Moreover, another pair of problems, MC-st-Cut and MC-Multi-Cut, has different relationships than their classical counterparts.

Theorem 2.2 MC-Multi-Cut is equivalent to MC-st-Cut.
Proof: First MC-st-Cut is a special case of MC-Multi-Cut. Then, we prove that MC-Multi-Cut reduces to MC-st-Cut. To see this, take k copies G 1 , . . . , G k of graph G, one for each pair s i , t i to be disconnected in a MC-Multi-Cut instance. Now, merge all vertices

s i ∈ G i (resp. t i ) together into a single vertex s (resp. t). A colored st-cut in this new graph is trivially a colored multicut in G.
As a consequence of Theorem 2.2, in the following the MC-Multi-Cut problem is not going to be considered.

Finally, as Lemma 2.3 below proves, the MC-st-Cut and MC-st-Path problems are equivalent in the special case of series-parallel graphs. Let us recall that series-parallel graphs are graphs that can be constructed from a single edge by applying a sequence of two operations : we split an edge into two adjacent edges by introducing a vertex in the middle, and we replace an edge by two parallel edges.

Lemma 2.3

The MC-st-Cut and MC-st-Path problems are equivalent in series-parallel graphs.

Proof: Let G 1 be a series-parallel graph. G 1 is constructed from a single edge whose extremities are vertices s 1 and t 1 by applying a specific succession of the two operations.

Another series-parallel graph G 2 can be constructed such that the MC-st-Path problem in G 1 is equivalent to the MC-st-Cut problem in G 2 and vice versa in the following way.

Let s 2 and t 2 be the extremities of an isolated edge and construct graph G 2 by applying the complementary succession of operations of the construction of G 1 . That is, when an edge of G 1 is split into two edges, a parallel edge is added to the corresponding edge of G 2 , and when a parallel edge is added to an edge of G 1 , the corresponding edge of G 2 is split into two edges. Give to an edge of G 2 the color given to its corresponding edge in G 1 .

An s 1 t 1 -path in G 1 is in bijection with an s 2 t 2 -cut in G 2 since a path consists of crossing edges connected in series while a cut consists of cutting "parallel" edges.

By consequence of Lemma 2.3, in the rest of the paper, all the complexity and inapproximability results are based on the construction of some specific series-parallel graphs of extremities s and t in which a colored st-path is searched. Moreover, all the NP-hardness and inapproximability proofs can be given for only one of the two problems.

Polynomial cases

In this section we present some restrictions under which colored problems are polynomial. We first extend a result of [START_REF] Datta | Diverse routing for shared risk resource groups (SRRG) failures in WDM optical networks[END_REF] which states that when the edges of each color form a star, the MC-st-Path problem is polynomial. Proof: We use the following transformation. Given a colored graph G = (V, E, C), we construct the graph H = (V H , E H ), where each vertex of V H represents a color of G. There is an edge between two vertices of V H iff two edges with the corresponding colors are adjacent in G. Now add vertex s (resp. t) and edges between s (resp. t) and any vertex of H representing a color adjacent to s (resp. t) in G.

The MC-st-Path, MC-st-Cut and MC-Cut problems in G are reduced to their classical counterparts in H, which are respectively : st-paths, vertex-st-cut and vertex-disjoint st-paths. For 2-Min Overlapping Color st-Paths, note that any two st-paths in H necessarily overlap on vertices that are vertex-st-cut of size one.

For MC-Cut, note that a colored graph in which colors have span one can also be seen as an hypergraph in which the vertices spanned by a color form an hyperedge. The MC-Cut problem is then equivalent to the minimum hyperedge cut problem in a general hypergraph which is polynomial [START_REF] Rizzi | On minimizing symmetric set functions[END_REF].

The case of MC-Cut is quite particular, since it can be solved in polynomial time when the number of edges of each color is bounded by a given constant k.

Theorem 3.2 When the number of edges of each color is bounded by a given constant k, MC-Cut can be solved in polynomial time.

Proof: Let S be the value of the minimum edge cut of the colored graph without taking its colors into account. Then, the value of the optimal color cut is in [S/k, S], and the associated edge cut must have size in [S, kS]. In [START_REF] Karger | Global min-cuts in rnc and other ramifications of a simple mincut algorithm[END_REF], Karger proved that there exist at most |V | 2k cuts of size in [S, kS]. Moreover, they can be generated in polynomial time.

Hence, the problem can be solved by examining all the k-approximated minimum cuts (about |V | 2k ) and counting the colors they use.

Note that when the maximum colored degree of the graph is bounded, MC-Cut, MC-st-Cut and MC-Multi-Cut are also polynomial since the subsets of colors of size lower than the bound can be enumerated in polynomial time.

Bounded color span case

In this section, we assume that the span of each color is bounded by a constant k ≥ 1. The case k = 2 is particularly interesting since if a problem is NP-Hard in this case, it is also NP-Hard for any constant k ≥ 2.

2-Color Disjoint st-Paths

The counterpart of the x edge-disjoint st-paths problem consists of finding x color-disjoint st-paths. In the case of paths connecting two nodes (st-paths), the classical problem is easy to solve using single commodity flow techniques, or Menger's augmentations. However, the colored version of the problem turns out to be much harder even when the span of colors is bounded by two. The proof of complexity for the 2-Color Disjoint st-Paths problem presented in [START_REF] Hu | Diverse routing in mesh optical networks[END_REF] can easily be adapted to this case. Proof: Given a collection of subsets {S i |i ∈ 1, . . . , N } of a finite set S, the Set Splitting problem consists of finding two disjoint subsets of S such that each subset contains at least one element in S i , ∀i ∈ 1, . . . , N .

We construct a colored graph G = (V, E, C) as follows. V contains N + 1 vertices u 1 , . . . u N +1 . To each triple s, S i , S j such that s ∈ S i ∩ S j we associate a color c s ij . We connect u i and u i+1 with |S i | parallel paths, each of them corresponds to an element of S i . The path associated to s between u i and u i+1 consists of edges of every color c s ij for each j such that s ∈ S i ∩ S j .

In this graph colors have span two, and two color disjoint u 1 u N +1 -paths correspond to two disjoint subsets of S containing each at least one element in S i , ∀i ∈ 1, . . . , N and vice versa.

Maximum Number of Color Disjoint st-Paths

The Maximum Number of Color Disjoint st-Paths Problem has been proved NP-Hard in [START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF] using a reduction from 3SAT. This reduction fits for the case of colors of span at most two. However the following reduction from the Maximum Independent Set problem implies a stronger inapproximability factor since this problem is not approximable within a factor n Proof: To an instance of Maximum Independent Set problem on a graph G = (V, E), we associate the following color disjoint paths instance.

A colored graph H is constructed as follows. A color of H corresponds to an edge of G. Let s and t be two vertices of H. For each vertex v of G an st-path is added in H of length d(v), the colored degree of v in G, and using the d(v) colors adjacent to v in G. An example is given in Figure 5. Note that colors have span 2.

Trivially, two st-paths are color disjoint in H if and only if the two corresponding vertices are not adjacent in G. The maximum number of color disjoint paths is henceforth the size of a maximum independent set of G. In addition, |V H | ≤ |V | 2 , and so we deduce the inapproximability result of the theorem.

MC-st-Path and MC-st-Cut

When the span of each color is at most two (i.e. k = 2), the reduction from Min Set Cover of [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF] is inadequate to show the NP-hardness of MC-st-Path and MC-st-Cut since they require that the maximum size of the subsets available to cover the elements of the Min Set Cover instance is bounded by k = 2 too. In this case Min Set Cover can be polynomialy solved by matching techniques.

The NP-hardness of MC-st-Path for k = 2 (and so of MC-st-Cut, by Lemma 2.3) will be proved by giving a reduction from Maximum 3 Satisfiability. This reduction also proves the inapproximability of these problems. To such an instance we associate a colored graph G as follows. G has n + m + 1 vertices u i 1 ≤ i ≤ n + m + 1. Two colors, T i,j (T like true) and F i,j (F like false), are associated to each couple (i, j) such that x i or x i appears in C j . Let n i denote the number of clauses containing either x i or x i . There are 6m = 2 i=1,...n n i colors.

For each i ∈ {1, . . . , n} two paths of length n i connect u i and u i+1 , the first one contains one edge of each color T i,j and the second one contains one edge of each color F i,j .

For each j ∈ {1, . . . , m}, u n+j and u n+j+1 are connected with three parallel edges, each one corresponds to a literal y present in the clause C j . The color of such an edge is either T i,j or F i,j depending on y = x i or y = x i for some i ∈ {1 . . . n} (see Figure 6). Note that each color is used on exactly two edges.

In the graph G the MC-st-Path instance of interest is to find a path from s = u 1 to t = u n+m+1 using a minimum number of colors.

First we show that to each truth assignment of the variables of the Maximum 3 Satisfiability instance satisfying µ ≤ m clauses corresponds a u 1 u n+m+1 -path in the colored graph G with 4m-µ colors.

Consider an assignment of the variables, and construct an u 1 u n+m+1 -path as follows. If the variable x i is set to true (resp. false) the u 1 u n+m+1 -path contains between u i and u i+1 the subpath using the colors T i,j (resp. F i,j ). If a clause C j is satisfied by the assignment, the u 1 u n+m+1 -path contains between u n+j and u n+j+1 the edge associated to one of the variables satisfying the clause. That is, if the literal x i ∈ C j and the variable x i is set to true, the path uses the edge of color T i,j , or if the literal x i ∈ C j and the variable x i is set to false, the path uses the edge of color F i,j .

If the clause C j is not satisfied by the assignment, then the u 1 u n+m+1 -path uses any one of the three edges connecting u n+j and u n+j+1 .

The path described above uses 3m + (m -µ) colors. More precisely, i=1,...n n i = 3m colors are used between u 1 and u n+1 and for each of the µ satisfied clauses the color used belongs to these i=1,...n n i colors. For each of the m -µ unsatisfied clauses an additional color is needed. We now prove that a path using 3m + (m -µ) colors represents a truth assignment of the variables of the Maximum 3 Satisfiability instance such that µ clauses are satisfied.

Consider a u 1 u n+m+1 -path. The subpath between u i and u i+1 either uses the edges of color T i,j and the variable x i is set to true, or it uses the edges of color F i,j and the variable x i is set to false.

Assume that between u n+j and u n+j+1 the path uses one of the 3m colors already used between u 1 and u n+1 , w.l.o.g. let this color be T i,j . Then by construction of the colored graph G, the literal x i belongs to the clause C j , otherwise the color T i,j would not be available between u n+j and u n+j+1 . As the variable x i is set to true, the clause C j is satisfied.

As the u 1 u n+m+1 -path uses 3m + (m -µ) colors, µ colors among the 3m used in the subpath between u 1 and u n+1 are used between u n+1 and u n+m+1 , and thus µ clauses are satisfied. That proves the NP-hardness of MC-st-Path.

In addition, it is hard to decide if the minimum number of clauses unsatisfied is 0 or ε sat m for some ε sat > 0 [START_REF] Vazirani | Approximation Algorithms[END_REF]. Hence it is hard to decide if the optimal number of colors is 3m or 3m + ε sat m, which completes the proof.

For the MC-st-Cut problem, note that the constructed graph is a series-parallel graph and thus the result follows by Lemma 2.3.

A self-improvement construction similar to the one used in an inapproximability proof for the Maximum Clique problem [START_REF] Hochbaum | Approximation Algorithms for NP-Hard Problems[END_REF] permits to increase the inapproximability factor of Theorem 4.3 up to the factor given in the following theorem. Theorem 4.4 When the span of colors is bounded by a given constant k, there is an ε > 0 independent of k such that MC-st-Path and MC-st-Cut are hard to approximate within a factor k ε .

Given a colored graph G = (V, E, C) and two vertices s, t ∈ V , the aforesaid self-improvement construction consists of a colored graph product G 2 st (Fig. 7). First we replace each edge (u, v) of G by a copy G uv of the graph G, the vertices u and v are identified with the vertices s and t of the copy. Therefore there are |E| 2 edges in G 2 st . Then for an edge (x, y) belonging to a copy G uv , we define its color as (c uv , c xy ), where c xy is the color of edge (x, y) in G. Hence the color set of

G 2 st is C × C.
Note that two edges belonging to distinct copies of G replacing edges of distinct colors of G are of distinct colors in G 2 st too. In the same way the graph G p st is built recursively for any p ∈ N by replacing each edge of G p-1 st by a copy of G. Two key relations between solutions of MC-st-Path or MC-st-Cut in G p st and G are stated in Lemmas 4.5 and 4.6. They are based on the decomposition of a path of G p st into paths of G. Proof: The proof is detailed for the case p = 2, but we can generalize the used path decomposition to any constant p ∈ N, there are then p levels of paths instead of only the two following. Consider the path A(G 2 st ) returned by algorithm A for the MC-st-Path in G 2 st . This path can be decomposed into an external path P and several internal subpaths P i .

The external path P is the projection on G of the path A(G 2 st ) into G, by replacing the subpaths of the copies of G by the edges of G which they correspond to. Let |C P | the number of colors used by path P in G.

An internal subpath P i is a subpath of the path A(G Proof: As for Lemma 4.5, the proof is detailed for p = 2 but it can be easily generalized for any p ∈ N. Consider an optimal solution for MC-st-Path in G using color set C opt and remark that the Cartesian product C opt × C opt is a colored path in G 2 st . Indeed if the path P connects s to t using only colors in C opt in G, the path of G 2 st obtained by replacing each edge of P in G by the path P itself provides a feasible solution in G 2 st and uses only colors in C opt × C opt . Therefore OPT(G 2 st ) ≤ OPT(G) 2 . By lemma 4.5 if an optimal solution for MC-st-Path in G 2 st uses OPT(G 2 st ) colors, then a solution for MC-st-Path in G can be found which uses less than [OPT(G 2 st )]

1 2 . Thus OPT(G) ≤ [OPT(G 2 st )] 1 2 . 4 3 3 2 1 s t (a) G (1,1) (1,4) (1,3) (1,3)
(1,2)

(4.4) (4,3) (4,3) (4,2) (3,1) (3,4) (3,3) (3,2) (3,3) (3,1) (3,4) (3,3) (3,2) (3,3)
(2,1)

(2,4) that a label l v is eligible for a vertex v ∈ V if it belongs to at least one admissible pair (l u , l v ) ∈ Π uv for each neighbor u ∈ U of v.

(2,3) (2,2) (2,3) (4,1) s t (b) G 2 st
The Minimum Label Cover problem consists in finding a minimum cost labeling covering every edge of B. We assume the existence of an eligible label for each vertex v ∈ V . Otherwise, it can be decide in polynomial time that there is no labeling covering every edge of B.

In the following, we describe a reduction from Minimum Label Cover to MC-st-Cut and MCst-Path problems with a tight control of the dimensions of the instances that are built. This allows us to increase the order of magnitude of the inapproximability factor.

For each vertex

v i ∈ V , there is a vertex x i in V C . 3. There is an additional vertex x |V |+1 in V C . 4. For each label l v ∈ L V which is eligible for vertex v i ∈ V , there is a path connecting x i to x i+1 .
For each neighbor u ∈ U of v i , there is a corresponding edge in the path. This edge can be multiple since it must contain an edge with color c lu for each label l ∈ L U such that (l, l v ) is an admissible pair of labels for the edge {u, v i } : (l, l v ) ∈ Π uv i . Thus, if there is a single label l ∈ L U such that (l, l v ) is an admissible pair of labels for the edge {u, v i }, the corresponding edge is simple. However, if there are more than one such label, the corresponding edge of the path is indeed a multiple edge.

Figure 8(b) depicts the MC-st-Path instance that corresponds to the Minimum Label Cover instance of Figure 8(a). Note that in this case, the label 2 is not eligible for vertex e: even if it belongs to the relation Π ae , it does not belong to Π ce . Assigning this label to vertex e would therefore prevent from covering the edge {c, e}.

In the following we consider a x 1 x |V |+1 -colored path P with µ colors, and built a corresponding labeling covering all edges of E with cost µ.

The subpath of P between vertices x i and x i+1 is associated to a label

l v ∈ L V that is eligible for v i . Let assign l v to v i in the labeling: f V (v i ) = {l v }.
By construction, for each u neighbor of v i , the subpath contains an edge of color c luu , where l u belongs to an admissible pair of labels for the edge {u, v i }. Let assign l u to u in the labeling:

l u ∈ f U (u).
Consequently, the labeling constructed that way covers all edges. Its cost is µ since for each color c lu in the path, there is a label that is assigned to a vertex of U , and two distinct colors correspond to distinct pairs (label,vertex).

For example the path {c a4 , c c2 , c b2 , c d1 } in Figure 8(b) induces the assignment of label 4 to a since the color c a4 is used, the assignment of 2 to b and c and 1 to d. The label 1 is also assigned to e since between vertices x 1 and x 2 the path uses the subpath corresponding to label 1. In the same way, label 4 is assigned to f and label 2 to g. Conversely, we prove in the following that a labeling covering all the edges of E with cost µ induces a x 1 x |V |+1 -colored path using µ colors.

Consider the set of colors C = {c lu |l ∈ f U (u) ⊆ L U , u ∈ U } with all colors corresponding to a (label,vertex) pair of the labeling. This set is of size µ. Moreover, for each vertex v i ∈ V , each edge {u, v i } adjacent to v i is covered by a label l u . Therefore, the colors in C contains at least the edges of a x i x i+1 -path, as we claimed.

Henceforth, an algorithm that would yield a ρ-approximation for MC-st-Path would also yield a ρ-approximation for Minimum Label Cover. As a matter of fact, Minimum Label Cover cannot be approximated within 2 For the MC-st-Cut problem, note that G is a series-parallel graph and that the inapproximability factor depends only on the number of colors. Thus by Lemma 2.3 the theorem is also proved for MC-st-Cut.

Remark that the MC-st-Path problem is a sub-case of the colored problem consisting of finding a Steiner tree [START_REF] Garey | Computers and Intractability: A Guide to the theory of NPcompleteness[END_REF] using the minimum number of colors. The latest problem is therefore at least as hard to approximate as MC-st-Path.

Conclusion

In this paper, we have investigated complexity and approximability properties of optimization problems yielded by the notion of Shared Risk Resource Group. This work has been conducted in the combinatorial framework given by the notion of colored graphs.

We have shown that standard relationship between classical graph theory problems cannot be imported in the colored graph settings. In particular no min/max relation analogous to the classical max flow-min cut theorem holds, while st-cut and multicut problems are equivalent. Nevertheless the existence of a relation between colored problems depending on the size of the colored graph has to be investigated as well as many other open questions.

We have identified an important parameter in the complexity and approximability of some problems : the span of a color. When the maximum span of the colored graph is 1, most problems are polynomial, while when the maximum span is bounded by a constant k > 1 they become NP-Hard or NP-Complete. These problems are even harder to approximate when there is no assumption on the span of the colors.

Concerning generic settings, global problems (MC-Cut and MC-Spanning Tree) and local problems, i.e. concerning two vertices such as MC-st-Path and MC-st-Cut, appear to belong to different complexity classes (Table 1). Global problems seem to be easier than local ones.

However, the complexity of MC-Cut remains a conjecture in the general case. Note that in different settings, the problem has been proven to be NP-Hard [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF].

We proved that MC-st-Path and MC-st-Cut problems belong to the class III defined in particular in [START_REF] Hochbaum | Approximation Algorithms for NP-Hard Problems[END_REF], i.e., that is they are not approximable within a factor 2 log 1-δ |C| 1 2 for some δ > 0. But inapproximability within a factor |V | ε or |C| ε is still an open problem. However, we conjecture that one can find a booster construction for MC-st-Path and MC-st-Cut that can close the question, in a similar way as for the Maximum Clique problem [START_REF] Hochbaum | Approximation Algorithms for NP-Hard Problems[END_REF].

  (a) where a single failure 1 A Shared Risk Link Group : AH and EI links share the same risk FG. The virtual connection EI breaks whenever only one of the underlying links EF, FG or GI fails, it is thus replaced with a path of monochromatic edges.

Figure 1 :

 1 Figure 1: A multilayer network and its transformation into a colored graph.

  (b) illustrates this

Figure 2 :

 2 Figure 2: Examples

  (b)) and color c 3 has span 1 (Fig.2(c)).

Figure 3 :

 3 Figure 3: A minimum color st-path is not necessarily composed of minimum color paths.

  question, δ = (log log |C|1 2

Theorem 3 . 1

 31 When each color has span 1, the MC-st-Path, MC-st-Cut, MC-Cut, 2-Color Disjoint st-Paths, 2-Min Overlapping Color st-Paths and Maximum Number of Color Disjoint Paths problems are polynomial.

Theorem 4 . 1

 41 There is a reduction from the Set Splitting problem to the 2-Color Disjoint st-Paths problem restricted to the case of colors of span bounded by 2.

1 2 1 4

 11 -ε for any ε > 0 in a graph with n vertices unless P = N P [10]. Theorem 4.2 There is an approximation preserving reduction from the Maximum Independent Set Problem to the Maximum Number of Color Disjoint st-Paths Problem when colors have span at most two. The Maximum Number of Color Disjoint st-Paths Problem is not approximable within a factor o(n -ε ) for any ε > 0 unless P = N P .

Figure 5 :

 5 Figure 5: Example of a colored graph built from a Max Independent Set instance.

Theorem 4 . 3

 43 The MC-st-Path and MC-st-Cut problems are NP-Hard when each color contains at most two edges and there is an ε > 0 such that they are hard to approximate within a factor 1 + ε.Proof: We reduce Maximum 3 Satisfiability to MC-st-Path. Consider an instance of Maximum 3 Satisfiability with n variables x i , 1 ≤ i ≤ n, and m clauses C j , 1 ≤ j ≤ m, each being a disjunction of three variables. The Maximum 3 Satisfiability problem consists of finding a truth assignment to the variables which satisfies the maximum number of clauses.

Figure 6 :

 6 Figure 6: Reduction of Maximum 3 Satisfiability to MC-st-Path with colors of span 2

Lemma 4 . 5 | 1 p

 451 Let A be an algorithm for MC-st-Path, then, ∀p ∈ N, a colored path P G of G of cost at most |A(G p st )can be deduced from A(G p st ).

Figure 7 :

 7 Figure 7: A graph G and its square graph G 2 st .

Theorem 5 . 1 1 2 2 )

 5112 MC-st-Path and MC-st-Cut problems are NP-Hard to approximate within a factor2 log 1-δ |C| where δ = (log log |C| 1 -ε for any ε < 1/2. Proof: Let B = (U, V, E), L U , L V , {Π uv })be an instance of Minimum Label Cover. We built a colored graph G = (V C , E C , C) and an instance of MC-st-Path in G as follows. 1. For each pair (l, u) ∈ L U × U , there is a color c lu in C. Note that |C| = |L U ||U |.

  3,1),(4,1),(4,2),(3,2),(1,4)} = {(4,1),(3,1),(2,2),(3,2)} = {(3,1),(2,1),(4,2),(1,2)} = {(2,1),(4,1),(4,2),(2,2),(3Instance of MC-st-Path

Figure 8 :

 8 Figure 8: Illustration of the reduction from Minimum Label Cover to MC-st-Path.

1 2 1 2 ≤ |V | 3 2.

 113 log 1-δ |V | , where δ = (log log |V |) -ε and ε < 1 2 [6]. This results holds for instances where |L U | ≤ 2 log 1-δ |V | ≤ |V | and |U | ≤ |V |(log log |V |) As far as the size of the color set of G is |C| = |U ||L U | ≤ |V | 2 , MC-st-Path cannot be approximated within 2 log 1-δ |C| where δ = (log log |V |) -ε and ε < 1/2.

Table 1 :

 1 Complexity and approximability properties of colored problems. Figure 4: Example of colored graph in which the minimum color st-cut is 2 but there is no pair of color disjoint paths.

s t

  2 st ) corresponding to an edge i of G. Let |C P 0 | be the minimum number of colors used by an internal subpath among all internal subpaths. The proof finishes by noticing that |A(G 2 st )| ≥ |C P ||C P 0 | ≥ [min{|C P |, |C P 0 |}] 2 . Let G be a colored graph, s and t two vertices of G and p ∈ N. Optimal solutions of MC-st-Path in G and in the graph G p st satisfy |OPT(G p st )| = |OPT(G)| p .

	Lemma 4.6

The research reported in this paper is funded in part by NSF grant ANI-9973102, DARPA/NSA grant N66001-00-1-8949, ACI-SI PRESTO, Région PACA, France Telecom R&D, European projects IST FET AEOLUS and COST 293 Graal.

Proof: [Theorem 4.4] From a graph G where each color contains at most two edges, we construct a graph G p st , an instance of MC-st-Path, for some p ∈ N. Note that in G p st each color has span at most 2 p since at most two edges belong to the same color in G and thus the number of edges of a given color is at most twice in G p st than in G p-1 st . By Lemmas 4.5 and 4.6, there is ε 1 such that no algorithm can approximate MC-st-Path within a factor (1 + ε 1 ) p , for otherwise it would contradict Theorem 4.3. Since this inapproximability factor is proved for colored graphs of maximum span 2 p for any p ∈ N, it is still true for any colored graph of maximum span bounded by a constant k ∈ N . We can write k = 2 log 2 k . Hence in the case p = log 2 k , it is hard to approximate MC-st-Path within a factor (1 + ε 1 )

Even if the gap between approximability and inapproximability factors remains large, the following trivial approximation algorithm shows that the MC-st-Path, MC-st-Cut and MC-Cut problems are easier to approximate than the Maximum Number of Color Disjoint Paths problem.

Theorem 4.7 When the span of each color is bounded by a given constant k, the MC-st-Path, MC-st-Cut, MC-Cut problems can be approximated within a factor k.

Proof: The transformations presented in the proof of Theorem 3.1 can be generalized to the case of colors of span bounded by a constant k.

Let G = (V, E, C) be a colored graph, then H = (V H , E H ) is the graph constructed as follows. Each vertex of H represents a connected component of some color of C. Two vertices of V H are joined by an edge of E H if the two associated components have a common vertex in G. Two vertices s and t are added to V H and an edge of E H connects s (resp. t) to a vertex v of V H if s (resp. t) belongs to the component represented by v. Now assume that Γ is the value of a minimum vertex st-cut in H. Since there are no more than k vertices in H corresponding to the same color of G, and since in the minimum color st-cut of G at most Γ components are cut, the number of colors of a minimum color st-cut in G is between Γ and Γ/k. The same reasoning works for MC-st-Path.

For MC-Cut, construct an hypergraph from the colored graph whose hyperedges are the connected components of each color. Each color generates at most k hyperedges and the same reasoning as for MC-st-Cut and MC-st-Path applies to MC-Cut and the hypergraph cut.

General Case : MC-st-Path and MC-st-Cut

In the case of colored graphs with generic span of colors, MC-st-Cut and MC-st-Path problems have been shown hard to approximate within a factor 2 log 1-δ |C| ) -ε for all ε < 1/2 [START_REF] Carr | On the red-blue set cover problem[END_REF][START_REF] Wirth | Multicriteria Approximation of Network Design and Network Upgrade Problems[END_REF].

In this section, we improve this result using a reduction from the Minimum Label Cover problem [START_REF] Dinur | On the hardness of approximating label-cover[END_REF] defined as follows.

Let B = (U, V, E) be a bipartite graph, L U and L V two sets of labels that can be assigned to the vertices of U and V , respectively. For each edge {u, v} ∈ E B , with u ∈ U and v ∈ V , a relationship Π uv ⊆ L U × L V defines the pairs of labels that are admissible for {u, v}.

A labeling is a pair of functions f U : U → 2 L U and f V : V → 2 L V -{∅} defining the assignment of a set of labels to each vertex of B, where 2 L represents the set of all subsets of a given set L.

The cost of a labeling is u∈U |f U (u)|. An edge {u, v} ∈ B, with u ∈ U and v ∈ V , is covered by a labeling if for every label l v assigned to v, there is a label l u assigned to u such that the pair (l u , l v ) is admissible: (l u , l v ) ∈ Π uv . We say