Jean-Claude Bermond
email: jean-claude.bermond@inria.fr

David Coudert
email: david.coudert@inria.fr

D ' Gianlorenzo
email: gianlorenzo.d_angelo@inria.fr

Angelo

Fatima Zahra Moataz

Diverse Routing with the star property

Keywords: Diverse routing, Shared Risk Link Group, colored graph, labeled graph, complexity, algorithms

 for computing pairs of SRLG-disjoint paths in networks with the star property, and then prove that this problem is in fact N P -hard in the strong sense. More generally, we prove that the diverse routing problem in networks with the star property is N P -hard in the strong sense, hard to approximate, and W [1]-hard when the parameter is the number of SRLG-disjoint paths. Last, we devise polynomial time algorithms for practically relevant subcases, in particular when the number of SRLG is constant, the maximum degree of the vertices is strictly smaller than 5, and when the network is a directed acyclic graph.

Diverse Routing with the star property

Résumé : La notion de groupe de liens partageant un risque (Shared Risk Link Group, (SRLG) a été introduite pour modéliser des problèmes de tolérance aux pannes simultanées d'ensembles de liens d'un réseau. Dans ce contexte, le problème du routage diversifié est de trouver un ensemble de chemins SRLG-disjoints entre une paire donnée de noeuds du réseau. Ce problème a été prouvé NP-complet en général [START_REF] Hu | Diverse routing in mesh optical networks[END_REF] et certains cas polynomiaux ont été caractérisés [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF].

Dans cet article, nous étudions le problème du routage diversifié dans les réseaux satisfaisants la propriété d'étoile [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF]. Dans un réseau satisfaisant la propriété d'étoile, un lien peut être affecté par plusieurs SRLGs, mais tous les liens affectés par un même SRLG sont incidents à un même sommet. Nous commençons par donner des contre-exemples à l'algorithme polynomial proposé dans [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] pour le calcul de paires de chemins SRLG-disjoints dans les réseaux satisfaisants la propriété d'étoile. Puis, nous prouvons que ce problème est en fait NP-difficile au sens fort. Plus généralement, nous montrons que le problème du routage diversifié dans les réseaux avec la propriété d'étoile est NP-difficile au sens fort, APX-difficile, et W [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF]-difficile lorsque le paramètre est le nombre de chemins SRLG-disjoints. Enfin, nous caractérisons de nouvelles instances polynomiales, en particulier lorsque le degré maximum des sommets est 4, ou lorsque le réseau est acyclique.

Mots-clés : Diverse routing, Shared Risk Link Group, colored graph, labeled graph, complexity, algorithms.

Introduction

The notion of Shared Risk Link Groups (SRLG) has been introduced to capture survivability issues when a set of links of a network may fail simultaneously. More precisely, a SRLG is a set of network links that are likely to fail simultaneously if a given event (i.e., a risk) occurs. The scope of this concept is very broad, from the set of fiber links of an optical backbone network that are physically buried at the same location and so that could be cut simultaneously (i.e., backhoe fade), or that are located in the same seismic area, to radio links in access and backhaul networks subject to localized environmental conditions affecting signal transmission, or to traffic jam propagation in road networks.

The graph theoretic framework for studying optimization problems in networks with SRLGs is the colored-graph model [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF][START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF][START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF][START_REF] Doucette | Shared-risk logical span groups in span-restorable optical networks: Analysis and capacity planning model[END_REF][START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF][START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF], also called labeled-graph model [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][START_REF] Broersma | Paths and cycles in colored graphs[END_REF][START_REF] Cerulli | Heuristic approaches for the minimum labelling hamiltonian cycle problem[END_REF][START_REF] Cerulli | Extensions of the minimum labelling spanning tree problem[END_REF][START_REF] Cerulli | The Next Wave on Computing, Optimization, and Decision Technologies, chapter Metaheuristics comparison for the minimum labelling spanning tree problem[END_REF][START_REF] Hassin | The complexity of bottleneck labeled graph problems[END_REF][START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF][START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF][START_REF] Carrabs | The labeled maximum matching problem[END_REF][START_REF] Couëtoux | Labeled traveling salesman problems: Complexity and approximation[END_REF]. In the colored-graph model, the network topology is modeled by a graph G = (V, E) and the set of SRLGs by a set of colors R. Each SRLG is modeled by a distinct color, and that color is assigned to all the edges corresponding to the network links subject to this SRLG. Also, an edge modeling a network link subject to several SRLGs will be assigned as many colors as SRLGs. A colored-graph is therefore defined by the triple (V, E, R) in which the set R of colors is a covering of the edges of E.

In the context of colored graphs, basic graph connectivity problems have been re-stated in terms of colors and proved much more difficult to address than their usual counterparts. For instance, the minimum color st-path problem is to find a path from vertex s to vertex t in the graph that minimizes the cardinality of the union of the colors of the edges along that path. This problem has been proved N P -hard [START_REF] Shen | Shared risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks[END_REF][START_REF] Broersma | Paths and cycles in colored graphs[END_REF] and hard to approximate [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF][START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF] in general, W [START_REF] Berman | On approximation properties of the independent set problem for degree 3 graphs[END_REF]-hard when parameterized by the number of used colors and W [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF]-hard when parameterized by the number of edges of the path [START_REF] Fellows | The parameterized complexity of some minimum label problems[END_REF]. The minimum color spanning tree problem, which asks to find a spanning tree of the graph that minimizes the cardinality of the union of the colors of its edges, has been proved N P -hard [START_REF] Chang | The minimum labeling spanning trees[END_REF][START_REF] Wan | A note on the minimum label spanning tree[END_REF][START_REF] Jiang | Improving robustness of PGP keyrings by conflict detection[END_REF][START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF], as hard to approximate as set cover [START_REF] Krumke | On the minimum label spanning tree problem[END_REF], and W [START_REF] Berman | On approximation properties of the independent set problem for degree 3 graphs[END_REF]hard when parameterized by the number of used colors [START_REF] Fellows | The parameterized complexity of some minimum label problems[END_REF]. Other graph connectivity problems have been studied in colored-graphs such as the minimum color cut [START_REF] Faragó | A graph theoretic model for complex network failure scenarios[END_REF][START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF], the minimum color st-cut [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF], the minimum color maximum matching [START_REF] Fellows | The parameterized complexity of some minimum label problems[END_REF], and the diverse routing problem [START_REF] Hu | Diverse routing in mesh optical networks[END_REF]. In this paper, we are interested in the last problem.

The diverse routing problem is one of the most fundamental problem for network survivability. It asks to find a set of color-disjoint paths between a given pair of end nodes of the graph. This problem has been proved N P -complete in general [START_REF] Hu | Diverse routing in mesh optical networks[END_REF] even when seeking for only two colordisjoint paths [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems[END_REF]. But, when both the set R of colors is a partition of the edges and the subgraphs induced by each color are stars then the diverse routing problem can be solved in polynomial time [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF]. More generally, the diverse routing problem can be solved in polynomial time when R is a partition and the subgraphs induced by each color are connected [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]. However, no other polynomial instances are know so far.

An interesting property when studying connectivity problems in colored graphs is the star property [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF]. We say that a colored graph has the star property if the induced subgraph of each color is a star. From a networking perspective, this property indicates that correlated failures are sets of links incident to a router node. The failure of the router node itself is modeled with a color assigned to all its incident links. As said above, the diverse routing problem can be solved in polynomial time in colored graphs satisfying the star property and such that the set of colors forms a partition of the edges [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF][START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]. Moreover, it has been proved in [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems[END_REF] that the minimum color st-path problem can be solved in polynomial time in colored graphs with the star property, without any assumption on the set of colors (R is a covering). A natural question is thus if the diverse routing problem can be solved in polynomial time in colored graphs with the star property when leveraging the partition assumption. Indeed, this question has been addressed in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] for computing two color-disjoint paths, claiming that this can be done in polynomial time. However, in this paper we disprove the correctness of the algorithm proposed in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF], and we show that the problem is in fact N P -hard in the strong sense in this setting.

In detail, given a colored graph G = (V, E, R), we denote by α the maximum number of colors per arc, by β the maximum number of arcs having the same color, and by ∆ and ∆ c , the maximum degree and the maximum colored degree, respectively.

We show that finding k SRLG disjoint paths is N P -hard in the strong sense, even with the star property and α and β are fixed with α ≥ 3 and β ≥ 3 or α ≥ 6 and β ≥ 2. Moreover, unless P = N P , such problem cannot be approximate within O(|V |) even if β is fixed, β ≥ 2 and it is AP X-hard if α is fixed. Such inapproximability results hold also when the graph is a Directed Acyclic Graph (DAG) or it is an undirected graph.

The above inapproximability results imply that, if α is unbounded, we cannot find an approximation factor better than |V | k , where k is a constant. This corresponds to find k color-disjoint st-paths, where k is a given constant. In other words, the only way to cope with this problem (in a general graph with the star property) is to find a fixed number of color-disjoint paths. However, we can also prove that the problem is W [1]-hard which means that no F P T algorithms can be devised, unless F P T = W [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF], that is cannot exist an algorithm which finds k color-disjoint paths in O(2 k • poly(|V |)) time. Finally we have shown that even finding a fixed number k ≥ 2 of color-disjoint paths is N P -hard. This implies that it is impossible to devise an algorithm which finds k color-disjoint paths in O(|V | O(poly(k)) ) time. This last result holds even if ∆ is fixed with ∆ ≥ 6 + k; α, β and ∆ c are fixed with α ≥ 4, β ≥ 2, and

∆ c ≥ 14 + k or α ≥ 2, β ≥ 4 and ∆ c ≥ 2 + k.
On the positive side, we show that the problem can be solved in polynomial time in particular subcases which are relevant in practice. Namely, we solve the problem when the input graph is a DAG, when the number of SRLGs is bounded by a constant (i.e. |R| = O(1)) or when the degree of the graph is strictly smaller than 5. In detail, the algorithm for DAGs requires O((|V |∆) 2k ) time. As finding k color-disjoint paths is W [1]-hard, this is basically the best time possible up to a constant in the exponent. The algorithm for fixed |R| and the one for ∆ < 5 require O(|V | + |E|) time. Also in this case the computational time matches the theoretical lower bound. Note also that the above restrictions on the input instances do not constitute a constraint in practical applications as in real networks both the number of SRLGs and the maximum degree is usually very small.

Notation and problem statement and preliminaries

We model a network as a directed graph G = (V, E), where the vertices in V represent the nodes and the arcs in E represent the links. We associate a color to each SRLG. Let us denote by R the set of all the colors, by E(c) the set of arcs having color c ∈ R, and by R(e) the set of colors associated with arc e ∈ E.

A multi-colored graph is a triple mG = (V, E, R), where (V, E) is a directed graph and R is a set of colors assigned to E. We denote by α = max e∈E |R(e)| (i.e. the maximum number of colors per arc) and by β = max c∈R |E(c)| (e.i. the maximum number of arcs having the same color ). Given a vertex v, Γ -(v) and Γ + (v) denote the in-neighbors and out-neighbors of v, respectively,

Γ(v) = Γ -(v) ∪ Γ + (v).
A color is incident to a vertex v if such color is assigned to an arc incident to v. The colored degree of a given vertex v is its number of incident colors and it is denoted by d c (v). The degree of a vertex v is the size of Γ(v) and it is denoted by d(v). The maximum degree and the maximum colored degree of a graph are denoted by ∆ and ∆ c , respectively.

Inria

We assume that the graphs have the so-called star property [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF]. A color c ∈ R is called a star color if all arcs of E(c) are incident to the same vertex. A multi-colored graph has the star property if it has only star colors.

Given a multi-colored graph mG and two vertices s and t, an st-path is an alternating sequence of vertices and arcs, beginning with s and ending with t, in which each arc is incident with the vertex immediately preceding it and the vertex immediately following it. A path is denoted by the sequence of vertices or by the sequence of vertices and arcs. We say that two paths P 1 and

P 2 are color-disjoint if (∪ e∈P1 R(e)) ∩ (∪ e∈P2 R(e)) = ∅.
We aim at finding the maximum number of color-disjoint paths, formally:

Definition 1 (Max Diverse Colored st-Paths (MDCP)) Given a multi-colored graph mG and two vertices s and t, find the maximum number of color-disjoint st-paths.

The corresponding decision problem is the following.

Definition 2 (Diverse Colored st-Paths (DCP)) Given a multi-colored graph mG, two vertices s and t and an integer k, are there k color-disjoint st-paths?

We refer the problem in which k is fixed and not in the input of the problem as k-DCP.

Definition 3 (k Diverse Colored st-Paths (k-DCP)) Given a multi-colored graph mG and two vertices s and t, are there k color-disjoint st-paths?

Note that, as is MDCP an optimization version of DCP, an algorithm for a problem implies an algorithm for the other one.

Counterexample to Luo&Wang's algorithm

In [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] it is proposed a polynomial time algorithm to find two color-disjoint paths from a source vertex s to a destination vertex t in an undirected multi-colored graph with the star property. In this section, we show that the algorithm given in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] is not correct by giving two counterexamples that show that, on the one hand, the algorithm sometimes is not able to find two disjoint paths when they exist and on the other hand, it might find paths which are not color-disjoints.

We mainly use the notation of the paper. We denote by s the source vertex (called v s or v 0 in the paper) and t the destination vertex (called v d in the paper). The Luo&Wang's algorithm is a modified version of the Bhandari's algorithm [START_REF] Bhandari | Survivable Networks: Algorithms for Diverse Routing[END_REF]. In detail, the algorithm works in five steps. In the first step, a shortest path P a = {s ≡ u 0 , u 1 , . . . , u ≡ t} from s to t is computed using e.g. Dijkstra's algorithm. In the second step, each edge {u i , u i+1 }, i = 0, 1, . . . , -1, in P a is transformed into a directed arc (u i+1 , u i ), i.e. the arc is directed towards the opposite direction of path P a . In the third step, some virtual vertices are added to divide edges which are not part of P a but have their endpoints in P a . Finally, a second path P b from s to t in this modified graph is computed. If P b and P a do not share any edge or vertex, then two color-disjoint paths are found. Otherwise, the algorithm performs the segment deletion and exchange process of the Bhandari's algorithm.

In the counterexamples we mention only some colors. Other colors are not represented, we can either suppose there are no other colors or that they are different from the colors explicitly mentioned and appear on only one edge. All edges have cost 1.

In the example 1 (see Figure 1), color c is shared between edges {s, w 0 } and {s, v 1 } and color c = c is shared between edges {s, w 0 } and {s, v 2 }. The shortest path is P a = {s, w 0 , t}. Let us apply the algorithm. As it is also explained in page 451 lines 9-10, the initialization part guarantees that the first edge of P b , is color-disjoint from P a . Therefore, in the example 1, the

v 2 w 1 w 2 w 0 c c c c v 1 t s Figure 1: Example 1.
algorithm does not find any edge to start and so terminates and the authors conclude there are no two color-disjoint paths. However such two color-disjoint paths clearly exist, namely they are P 1 = {s, v 1 , w 1 , t} and P 2 = {s, v 2 , w 2 , t}. Similar counterexample exist with the colors at destination vertex putting color d shared between edges {w 0 , t} and {w 1 , t} and color d shared between edges {w 0 , t} and {w 2 , t}.

In the example 2 (see Figure 2), we have 4 specific colors c and c = c (forming a star in v) and d and d (the last two are different from c and c , but can be the same). The shortest path from s to t is P a = {s, a, v, b, t}. In this example vertex v is a cut-vertex, then if there exist two color-disjoint paths, they both have to contain v. In this case, one path should use the subpath u, v, b and the other one should use the subpath u , v, b (b and b can be interchanged). Indeed, if we use the edge {a, v} of P a there is no path which is color-disjoint from this edge. In vertex w one path uses the edge {w, u} and the other {w, u }. Let us apply the algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF]. The shortest path found in the first step is P a = {s, a, v, b, t}. Procedure in Fig. 6 of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] will find successively a , w, u, u by case 1 and put them in V n . It will add (case 2) v, keeping the conflict and so next step it will have to go backwards (case 3) till a with T 2 information. At that stage, if we follow strictly what is said in the algorithm we can find perhaps z but never w again and the algorithm stops missing the fact there exist two color-disjoint paths when d = d . Another interpretation of the algorithm (or a variant of the figure by adding an edge {a , v} with both colors c and c ) will be to use the virtual edges around v and it might be that the algorithm discovers the two paths P 1 and P 2 . But in all cases in w the algorithm considers only possible conflicts with P a and there are no such conflicts. So in that situation, the algorithm gives that P 1 and P 2 are color-disjoint, but they are not if d = d .

Inria 4 Hardness results

We first show that DCP is N P -hard in the strong sense and that MDCP is hard to approximate within some bound, even with some restrictions on α and β. Note that all the following results are based on transformations which use undirected graphs which can be easily reformulated for directed graphs.

In the next theorem, we give a reduction from the exact cover by 3-sets (X3C) problem.

Definition 4 (Exact cover by 3-sets (X3C)) Given a set X with |X| = 3q and a collection C of 3-element subsets of X, does C contain an exact cover for X, i.e., a sub-collection C ⊆ C such that every element of X occurs in exactly one member of C ?

Problem X3C is known to be N P -hard in the strong sense [START_REF] Garey | Computers and Intractability: A Guide to the theory of NPcompleteness[END_REF] and it remains N P -hard if no element occurs in more than three subsets. Moreover, note that any feasible sub-collection C has cardinality q, i.e, |C | = q.

Theorem 1 DCP is N P -hard in the strong sense, even with the star property and α and β are fixed with α ≥ 3 and β ≥ 3 or α ≥ 6 and β ≥ 2.

Proof.

Given and instance of X3C, we define an instance of DCP as follows.

• for each element C i of C, we define a vertex v i , moreover, we add two vertices s and t;

• we add edges {s, v i } and {v i , t}, for each C i ∈ C;

• for each C i , C j ∈ C, such that i = j and C i ∩ C j = ∅, we add a new color to {s, v i } and {s, v j }; every other edge has a different color (or no colors if it is allowed);

• k = q.

The transformation is polynomial time computable and the star property holds. See Figure 3 for two examples. By definition each color is associated with two edges and hence β = 2. As X3C is N P -hard even if no element occurs in more than three subsets, each edge has at most 6 colors and hence α = 6. Furthermore, we can modify the transformation as follows: instead of adding colors as in the third item above, we define a color r x for each element x ∈ X and, for each C i = {x, y, z} ∈ C, we associate colors r x , r y , and r z to edge {s, v i }. In this way, each edge has 3 colors and each color is associated with at most 3 edges, that is α = 3 and β = 3. We first show that if the answer to the instance of X3C is "yes", then the answer to the instance of DCP is "yes". Let us denote as C = {C i1 , C i2 , . . . , C iq } an exact cover of the instance of X3C. We define k = q paths P j = {s, v ij , t}, for each j = 1, 2, . . . q. The set of paths is denoted by P . As |P | = q = k, it remains to show that the paths in P are color-disjoint. By contradiction, let us assume that two paths P a , P b ∈ P are not color-disjoint. As we chose different colors for each edge {v i , t}, P a and P b have to share some colors in edges {s, v ia } and {s, v i b } which implies that C ia ∩ C i b = ∅, a contradiction to the fact that C is an exact cover.

We now show that if the answer to the instance of DCP is "yes", then the answer to the instance of X3C is "yes". Let us denote as P a set of k color-disjoint paths st-paths in the instance of DCP. Each path P j in P is in the form {s, v ij , t}, for j = 1, 2, . . . , k. We define C as C = {C i1 , C i2 , . . . , C i k }. All the elements of C are pairwise disjoint, in fact if by contradiction, we assume that there exist C ia and C i b such that C ia ∩ C i b = ∅, then the corresponding paths P a and P b would share some colors which is a contradiction to the fact that the paths in P are color-disjoint. Moreover, C is a covering of X as k = q, |C ij | = 3 and the sets in C are pairwise disjoint, which implies that C contains 3q = |X| distinct elements.

s t v 1 v 3 v 2 6 1, 2 5 4 1 2 s t v 1 v 3 v 2 6 2, 3 1, 2 1, 3 5 4
OBJ(S MDCP ) ≤ OBJ(S MSP ), (1)
where OP T and OBJ denote the value of the optimal solution and the value of the objective function of a solution, respectively. Inequalities 1 and 2 imply that OP T (IMSP) OBJ(SMSP) ≤ OP T (IMDCP) OBJ(SMDCP) . Therefore, any α approximation algorithm for MDCP implies an α approximation algorithm for MSP.

We use the same transformation given in Theorem 1 as algorithm f .

(|V |) even if β is fixed, β ≥ 2. Moreover, it is AP X-hard if α is fixed, α ≥ 3.
Proof. The first statement follows from the O(|C|) inapproximability of MSP [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF] and from the transformation where each color is associated with two edges which implies that β = 2. Moreover, as MSP is AP X-hard if the cardinality of all sets in C is upper bounded by a constant c ≥ 3 [START_REF] Kann | Maximum bounded 3-dimensional matching is max snp-complete[END_REF], we can modify the transformation as we did in Theorem 1 that is we define a color r x for each element x ∈ X and, for each c i = {x, y, z} ∈ C, we associate colors r x , r y , and r z to edge {s, v i }. In this way, α = 3.

Theorem 3 MDCP is W [1]
-hard where the parameter is the number of color-disjoint paths, even with the star property.

Proof. It is enough to observe that the reductions used in Theorems 1 and 2 are parameterizedpreserving reductions where the parameter is the number of color-disjoint paths which corresponds to the number of disjoint subsets in a set packing. In [START_REF] Downey | Fixed-parameter tractability and completeness ii: On completeness for w[1[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF] it has been shown that MSP is W [1]-hard if the parameter is the number of disjoint subsets.

Corollary 2 MDCP is not in F P T , unless F P T = W [1].
As |V | is an upper bound to any optimal solution of MDCP, Corollary 1 implies that, if α is unbounded, we cannot find an approximation factor better than |V | c , where c is a constant. This corresponds to find c color-disjoint st-paths, where c is a given constant. In other words, the only way to cope with this problem (in a general graph with the star property) is to find a fixed number of color-disjoint paths. However, Theorem 3 implies that no FPT algorithms can be devised, unless F P T = W [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF], that is cannot exist an algorithm which finds k color-disjoint paths in O(2 k • poly(|V |)) time. Moreover, the next theorem shows that even finding a fixed number k ≥ 2 of color-disjoint paths is N P -hard. This implies that it is impossible to devise an algorithm which finds k color-disjoint paths in O(|V | O(poly(k)) ) time. Note also that the transformation used in Theorems 1-3 makes use of simple graph that can be easily turned on directed acyclic graphs.

The proof of the next theorem consists in a reduction from the problem of finding a Tcompatible path (or a path avoiding forbidden transitions), proved N P -complete in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF].

Let G = (V, E) be an undirected graph. A transition in v is a pair of edges incident to v. A set T (v) of admissible (or allowed) transitions in v is associated with vertex v in V . The transitions are represented in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] by a graph also denoted T (v) where vertices represent the edges of G incident to v and two vertices are joined if the edges they represent form an admissible transition. We call transition system the set T = {T (v) | v ∈ V }. Let G = (V, E) be a graph and T a transition system, a path P = {v 0 , e 1 , v 1 , . . . , e k , v k } in G, where v i ∈ V , e i ∈ E, is said to be T -compatible if, for every 1 ≤ i ≤ k -1, the pair of edges {e i , e i+1 } is admissible, i.e. {e i , e i+1 } ∈ E(T (v i )).

Definition 6 (T -Compatible path (T -CP))

Given a graph G = (V, E), two vertices s, t in V , and a transition system T , does G contain a T -compatible path?

It has been proved in [START_REF] Szeider | Finding paths in graphs avoiding forbidden transitions[END_REF] that problem T -CP is N P -complete in the strong sense and it remains N P -complete for simple graphs where vertices have either degree 4 or 3, vertices s and t have degree 3, and where for each vertex v: Proof. We first prove the statement for k = 2 and then we extend it for any fixed k ≥ 3.

• If d(v) = 4, T (v)
Given and instance of T -CP, we define an instance of 2-DCP as follows. We define a graph H = (V H , E H , R) where:

• For every edge e = {u, v} in G, we associate in H two paths of length 2: {u, x e , v} and {u, x e , v}. H has then |V (G)| + 2|E(G)| vertices and 4|E(G)| edges.

• We assign the colors to edges incident to a vertex v in H as follows:

no colors are assigned to edges incident to t;

for each pair of edges e and f incident to s in G such that f = e, we assign colors C ef and C ef (C e f and C e f , resp.) to edge {s, x e } ({s, x e }, resp.), and colors C ef and C e f (C ef and C e f , resp.) to edge {s, x f } ({s, x f }, resp.);

for each v = s, t, and for each pair of edges e and f incident to v in G such that f = e and {e, f } is not an admissible transition (i.e. {e, f } / ∈ E(T (v)) ), we assign colors C ef and C ef (C e f and C e f , resp.) to edge {v, x e } ({v, x e }, resp.), and colors C ef and C e f (C ef and C e f , resp.) to edge {v, x f } ({v, x f }, resp.). As each vertex has either degree 3 or 4, two cases can occur: * If d(v) = 4, let e, f, g and h be the 4 edges incident to v and E(T (v)) = {{e, f }, {g, h}}. Then edge {v, x e } receives the 4 colors C eg , C eg , C eh , C eh . Similarly, edge {v, x f } receives the 4 colors C f g , C f g , C eh and C f h . See Figure 5 for the complete list of colors assigned to all the edges. The transformation is polynomial time computable and the star property holds. Moreover, note that each edge has at most 4 colors, each color is associated with two edges, the degree of each vertex is at most 8 and the color degree is at most 16. It follows that α = 4, β = 2, ∆ = 8, and ∆ g = 16.

Inria v e h f g (a) v in G, T (v) = {e, f } ∪ {g, h} v x g x g x f x f x e x h x e x h (b) v in H Edge Colors {v, x e } C eg , C eg , C eh , C eh {v, x e } C e g , C e g , C e h , C e h {v, x f } C f g , C f g , C f h , C f h {v, x f } C f g , C f g , C f h , C f h {v, x g } C eg , C e g , C f g , C f g {v, x g } C eg , C e g , C f g , C f g {v, x h } C eh , C e h , C f h , C f h {v, x h } C eh , C e h , C f h , C f h
To prove the theorem, we first give the following properties.

Property 1 Given an edge e incident to s in G, the edge {s, x e } in H shares a color with all the other edges incident to s but {s, x e }. Said otherwise, the only pair of edges incident to s having no color in common are of the form {{s, x e }, {s, x e }} for some e. We first show that if there exists a T -compatible path in G, then there exist two colordisjoint paths in H. Let P = {s, e 1 , v 1 , . . . , e k , v k , e k+1 , t} be a T -compatible path from s to t in G. Q = {s, x e1 , v 1 , . . . , x e k , v k , x e k+1 , t} and Q = {s, x e1 , v 1 , . . . , x e k , v k , x e k+1 , t} are then

v h e f (a) v in G, T (v) = {e, h} ∪ {f, h} v x e x e x f x f x h x h (b) v in H Edge Colors {v, x e } C ef , C ef {v, x e } C e f , C e f {v, x f } C ef , C e f {v, x f } C ef , C e f {v, x h } no colors {v, x h } no colors
Figure 6: Color assignment for vertices with degree 3.

two color-disjoint paths in H. In fact, any edge {v, x e } has no color in common with {v, x e } by Properties 1, 2, or 3. Conversely, we now show that if there exist two color-disjoint paths in H, then there exists a Tcompatible path in G. Let Q = {s, x 1 , v 1 , . . . , x k , v k , x k+1 , t} and Q = {s, y 1 , u 1 , . . . , y h , u h , y h+1 , t} be two color-disjoint paths in H. We prove by induction on i ∈ {1, . . . , k + 1}, that {x i , y i } = {x ei , x ei }, v i = u i and k = h.

For i = 1, by property 1, {s, x 1 } and {s, y 1 } have no color in common only if {x 1 , y 1 } = {x e , x e } and then v 1 = u 1 .

Let us suppose that it is true till i = l and prove it for i = l + 1. In v l = u l , let the two edges used by Q and Q be {x e l , v l } and {x e l , v l }.

• If d(v l ) = 4, by property 3, the only possibility as Q and Q are color-disjoint is that they use the edges {v l , x e l+1 } and {v l , x e l+1 } where {e l , e l+1 } ∈ E(T (v l )) and so the statement is true for i = l + 1.

• If d(v l ) = 3, we distinguish two cases:

e l belongs to an edge of T (v l ) say {e l , h l } and the paths Q and Q being color-disjoint can only use the edges {v l , x h l } and {v l , x h l };

e l belongs to two edges in T (v l ), {e l , f l } and {e l , h l }. If one path uses the edge {v l , x h l } ({v l , x h l }, resp.) the other path cannot use the edge {v l , x f l } or {v l , x f l } by Property 2, it has then to use edge {v l , x h l } ({v l , x h l }, resp,).

It follows that the path P = {s, e 1 , v 1 , . . . , e k , v k , e k+1 , t} satisfies {e i , e i+1 } ∈ E(T (v i )) for every i ∈ {1, k} and then it is T -compatible.

To show that the problem remains N P -hard even for fixed α ≥ 2, β ≥ 4 and ∆ c ≥ 4, let us modify the above transformation by using the following color assignments.

Inria

• Edges incident to vertices whose degree in G is 4 have the color assignment of Figure 7; • Edges incident to vertex s have the color assignment of Figure 8; • the other vertices of degree 3 in G and t keep the same color assignment as before.

The above proof works with this color assignment. It follows then that 2-DCP is N P -hard even for fixed α ≥ 2, β ≥ 4 and ∆ c ≥ 4. To extend the proof to the case of k ≥ 3, it is enough to add k -2 paths length 2 from s to t called P i = {s, w i , t}, i = 3, 4, . . . k, with a new color assigned to each edge {s, w i }. These paths are color-disjoint among them and with the two paths in the above transformation. Moreover, this assignment does not change α and β and increases ∆ and ∆ c by k -2.

v e h f g (a) v in G, T (v) = {e, f } ∪ {g, h} v x g x g x f x f x e x h x e x h (b) v in H Edge Colors {v, x e } C 1 , C 2 {v, x e } C 3 , C 4 {v, x f } C 1 , C 2 {v, x f } C 3 , C 4 {v, x g } C 1 , C 3 {v, x g } C 2 , C 4 {v, x h } C 1 , C 3 {v, x h } C 2 , C 4
As finding k color-disjoint paths is N P -hard, we cannot find algorithms to approximate MDCP in general graphs. In the next section, we give algorithms for some important special cases.

Polynomial cases

In this section we give polynomial time algorithms for MDCP and DCP for some important special cases. We recall that, as is MDCP an optimization version of DCP, an algorithm for a problem implies an algorithm for the other one.

In particular, we solve DCP for the cases where the input graph is a Directed Acyclic Graph (DAG), for the cases where the number of colors is bounded by a constant (i.e. |R| = O(1)) and for some cases where the degree of the graph is strictly smaller than 5.

s h e f (a) s in G s x e x e x f x f x h x h (b) s in H Edge Colors {s, x e } C 1 , C 2 {s, x e } C 3 , C 4 {s, x f } C 1 , C 3 {s, x f } C 2 , C 4 {s, x h } C 1 , C 4 {s, x h } C 2 , C 3

Directed acyclic graphs

In this section we give an algorithm for finding k = O(1) color-disjoint paths in a DAG. Note that, the transformations in Theorems 1-3 can be modified in a straightforward way in order to obtain a DAG. It follows that, even in DAGs, finding k color-disjoint paths is N P -hard if k is not a fixed constant and it is not in F P T . Therefore, we will give an algorithm with complexity O(|V | O(poly(k)) ), note that this is the best possible according to the lower bounds. First we give an algorithm for finding 2 color-disjoint paths and then we generalize it to the case of k = O(1). The algorithm uses two graph transformations introduced in [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems[END_REF] and [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF] to find one shortest path in a multi-colored graph with the star property and to find two vertex-disjoint paths with forbidden pairs in a layered graph, respectively. We first give some definitions.

Definition 7 (Layered graph)

A directed graph G = (V, E) is layered if there is a layering function l : V → [0, 1, . . . , (|V | -1)] such that for every arc (u, v) ∈ E, l(v) = l(u) + 1.
We say that vertex u is in layer l(u) and arc (x, y) is in layer l(x). Layered directed graphs are acyclic. Definition 8 (Vertex-disjoint paths with forbidden pairs) Given a directed graph G = (V, E), two vertices s and t and a set of pairs of arcs F ⊆ E × E (called forbidden pairs), find two paths P 1 and P 2 between s and t such that P 1 and P 2 are vertex-disjoint and for any forbidden pair {e 1 , e 2 } ∈ F , if P 1 uses e 1 (e 2 , resp.), then P 2 does not use e 2 (e 1 , resp.).

A topological ordering of a DAG G = (V, E) is a linear ordering of its vertices such that, for every arc (u, v) ∈ E, u comes before v in the ordering. We define the ordering function f o : V → N as follows:

f o (v) = 0 if Γ -(v) = ∅ max{f o (u) | u ∈ Γ -(v)} + 1
otherwise.

Inria

The algorithm is based on the following observations.

• Every DAG can be transformed in polynomial time to a layered DAG. In fact, we can order topologically the DAG, and then replace every arc (u, v) with a directed path from u to v of length f o (v) -f o (u), with f o being the ordering function.

• The graph transformation introduced in [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial and FPT optimisation problems[END_REF] (see pages 6-7) to find a shortest coloredpath in graphs with the star property can be used to find two color-disjoint paths in a multi-colored graph.

Let mG be a multi-colored graph and G m the graph obtained by applying such a transformation, we will show that finding two color-disjoint paths in G is equivalent to finding two vertex-disjoint paths with forbidden pairs in G m , with the forbidden pairs being pairs of arcs belonging to the same color. However, the transformation has to be slightly modified to work for directed graphs. We report the modified transformation later in this section and we refer to it as Transformation 1 in the remainder of the section. It is important to note that if the directed graph is layered, the auxiliary graph will be layered as well.

• It has been proved in [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF] that finding two vertex-disjoint paths with forbidden pairs can be solved in polynomial time in layered DAGs where for every forbidden pair {e 1 , e 2 }, the arcs e 1 and e 2 are in the same layer of the graph. In [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF] (pages 119-120), the two paths have distinct sources and sinks, but the algorithm can be adapted to find two paths from s to t. If G = (V, E) is a layered graph, l its layering function and F is a set of forbidden pairs and we want to find two vertex-disjoint paths with forbidden pairs from s to t, the transformed graph G = (V , E ) will be constructed as follows:

V = {< u, v > |(u, v) ∈ V 2 , u = v, and l(s) < l(u) = l(v) < l(t)} ∪ {s} ∪ {t} E = {(< u 1 , v 1 >, < u 2 , v 2 >)|((u 1 , u 2 ), (v 1 , v 2 )) ∈ E × E -F } ∪{(s, < u, v >)|((s, u), (s, v)) ∈ E × E -F } ∪{(< u, v >, t)|((u, t), (v, t)) ∈ E × E -F }
In [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF] it has been proven that finding 2 vertex-disjoint pair in G with forbidden pairs F corresponds to finding a path in G . We will refer to this transformation as transformation 2 in the remainder of this paper.

The algorithm for finding 2 color-disjoint paths is the following.

1. Topologically sort G and define the ordering function f o ;

2. For every arc a from

v 1 to v 2 such that f o (v 2 ) -f o (v 1 ) > 1:
• replace a with a directed path P = (r 1 , . . . , r fo(v2)-fo(v1) ) from v 1 to v 2 ;

• assign to r 1 the colors of a incident to v 1 and to r fo(v2)-fo(v1) the colors of a incident to v 2 ;

We obtain then a layered DAG G 1 with the star property.

3. Apply transformation 1 to G 1 .

1. To each color we associate the center of the star of the edges with this color.

If the color has only one occurrence we choose arbitrarily as associated center one of the end vertices of the edge containing this color.

2. To a multicolored digraph mG we associate an auxiliary digraph G st (which is almost the line digraph of mG) as follows.

2.1. To each arc e of mG we associate in G st a vertex e and we join two vertices e and e by an arc from e to e , if the terminal vertex x of e is the initial vertex of e . 2.2. In G st we give to the arc (e, e ) the colors of e and e having x as center of their star. Let G 2 = (V 2 , E 2 ) be the obtained graph. Let F be the set of forbidden pairs of G 2 , which are the pairs of arcs of the same color. Note that G 2 is a layered graph as well and the edges of a forbidden pairs are in the same layer.

4. Apply the graph transformation 2 to G 2 . The new graph is G 3 .

V 3 = {< u, v > |(u, v) ∈ V 2 2
, u = v, and l(s) < l(u) = l(v) < l(t)} ∪ {s} ∪ {t} The algorithm can be generalized to find k color-disjoint paths using the same graph transformation with the following modifications:

E 3 = {(< u 1 , v 1 >, < u 2 , v 2 >)|((u 1 , u 2 ), (v 1 , v 2 )) ∈ E 2 × E 2 -F } ∪{(s, < u, v >)|((s, u), (s, v)) ∈ E 2 × E 2 -F } ∪{(< u, v >, t)|((u, t), (v, t)) ∈ E 2 × E 2 -F }
• F is the set of forbidden k-tuples (a k-tuple of arcs is forbidden if two of its elements have a color in common).

• G 3 is constructed as follows:

Inria -In each layer of G 2 , every k-tuple of vertices is represented by a vertex in G 3 -Two vertices in G 3 are linked by an arc if there is a k-tuple r of arcs linking the corresponding two k-tuples of vertices, such that r is not in F .

The next theorem shows the correctness of the above algorithm.

Theorem 5 There exists an algorithm that solves DCP if in a DAG which requires O((|V |∆) 2k ) computational time.

Proof. We show that each transformation is correct.

It is straightforward to see that there exist k color-disjoint paths in G if and only if there exist k color-disjoint paths in G 1 .

We now show that there exist k color-disjoint paths in G 1 if and only if there exist k vertexdisjoint paths in G 2 with forbidden k-tuples F . Graph G 1 has k color-disjoint paths P 1 , P 2 , . . . , P k from s to t, where P i = {s, v i,1 , v i,2 , . . . , v i,ji , t}, for each i = 1, 2, . . . , k if and only if the paths P i = {s, (s, v 1 ), (v 1 , v 2 ), . . . , (v i,ji , t), t} in G 2 are vertex-disjoint (as paths P i are edge-disjoint) and they do not use a forbidden k-tuple (as paths P i are color-disjoint).

We now show that there exist k vertex-disjoint paths in G 2 with forbidden k-tuples F if and only if there exists one path from s to t in G 3 . Since the input graph is a layered graph and the edges of a forbidden pairs are in the same layer this follows by the same arguments used in [START_REF] Chakaravarthy | New results on the computability and complexity of points-to analysis[END_REF] (see page 119) but with k-tuples instead of pairs and only one source-destination pair.

Step In the following, we give an example of how the algorithm finds 2 color-disjoint paths. Let's consider the DAG in Figure 11 and the ordering function f o defined as: The only path from s to t in G 3 is P = (s, v 2 v 3 , v 5 v 6 , v 8 v 9 , v 11 v 12 , t). In G 2 , P corresponds to the two vertex-disjoint paths with forbidden pairs P 1 = (s, v 2 , v 5 , v 9 , v 12 , t) and P 2 = (s, v 3 , v 6 , v 8 , v 11 , t), which correspond in G to the two color-disjoint paths (s, b, d, f, t) and (s, c, d, e, t).

f o (s) = 0, f o (a) = f o (b) = f o (c) = 1, f o (d) = 2, f o (e) = f o (f ) =
s b a c d f e t c2,c3 c1,c4 c1,c5 c4,c10,c11 c5,c7 c3,c8 c6,c7 c8,c9 c9,c11 c6,c10 Figure
11: G = (V, E) s b a g h c d f e t c2,c3 c1,c4 c1,c5 c4 c10,c11 c5,c7 c3,c8 c6,c7 c8,c9 c9,c11 c6,c10
Figure 12:

G 1 = (V 1 , E 1 )
after applying the Step 2 of the algorithm (Layering).

s v 2 v 1 v 4 v 3 v 6 v 5 v 7 v 8 v 9 v 10 v 11 v 12 t c2 c1 c1 c4 c3 c5 c7,c8 c8 c7 c7,c8 c6 c9 c10,c11 c10 c11
Figure 13: G 2 = (V 2 , E 2 ) after applying the Step 3 of the algorithm (Transformation 1). The forbidden pairs are: F = {{(s, v 1 ), (s, v 3 )}; {(v 5 , v 8 ), (v 5 , v 9 )}; {(v 5 , v 8 ), (v 6 , v 8 )}; {(v 5 , v 8 ), (v 6 , v 9 )}; {(v 5 , v 9 ), (v 6 , v 9 )}; {(v 6 , v 8 ), (v 6 , v 9 )}; {(v 10 , t), (v 11 , t)}; {(v 10 , t), (v 12 , t)}}.

Optimal diverse routing in weighted DAGs with the star property.

The above algorithm can be also used to find an minimum cost pair of color-disjoint paths in a weighted multi colored DAG. Let us assume that w is a weight function on the arcs of a graph G.

The previous algorithm can be adapted to find a minimum cost pair of color-disjoint paths by applying the following modifications.

1. In step 2, assign to (r 1 , r 2 ) the weight of (v 1 , v 2 ); 2. In step 1 of transformation 1, assign to (x, v m ) the weight of (x, y); 3. In step 2 of transformation 1, assign to (w, w ) the sum of the weights of (w, v) and (v, w ); 4. In transformation 2, assign to every arc of E 3 the sum of the weights of the two corresponding arcs in E 2 ; 5. With these modifications, the shortest path in G 3 corresponds to the optimal pair of disjoint paths in G.

Inria s v 1 v 3 v 1 v 2 v 4 v 5 v 2 v 3 v 5 v 6

Finding 2 color-disjoint paths with the minimum total number of colors in DAGs with the star property

We can use the previous algorithm to find a pair of color-disjoint paths with the minimum total number of colors by applying the following modifications:

1. In step 4, assign to every new edge (< u 1 , v 1 >, < u 2 , v 2 >) a weight equal to |R((u 1 , v 1 )) ∪ R((u 2 , v 2 ))|

2. The shortest path in the weighted graph G 3 will correspond then to the pair of color-disjoint paths with the minimum number of colors.

Bounded number of colors

In this section, we give an algorithm for finding k color-disjoint paths in the special case where the number |R| of colors in the network is bounded by a constant, i.e. |R| = O(1). We observe that such an algorithm works for every graph topology and even if the star property does not hold.

The algorithm is as follows.

1. Enumerate all the subsets of R. Let F be the family of all the subsets of R.

2.

For each set f in F consider the subgraph G f of G induced by all the arcs e such that R(e) ⊆ f .

3.

Remove from F all the elements f such that G f does not have a path from s to t and associate to the other elements a path P f from s to t.

4. Build a k-Set Packing instance where X = R and C = F and solve such instance by the exact algorithm in [START_REF] Björklund | Set partitioning via inclusion-exclusion[END_REF]. If there exists a tuple of k color-disjoint sets in F , then output the set of paths corresponding to such tuple; otherwise mG does not contain k color-disjoint paths.

1 Consider the graph G obtained from G by removing vertices s and t and the arcs incident to them; 2 foreach pair {s 1 , s 2 } of neighbors of s in G such that R((s, s 1 )) ∩ R((s, s 2 )) = ∅ and for each pair {t 1 , t 2 } of neighbors of t such that R((t 1 , t)) ∩ R((t 2 , t)) = ∅: do There exist two color-disjoint paths from s to t in G;

9 No 2 color-disjoint paths from s to t exist in G; Note that the above algorithm cannot be extended neither to find 3 or 4 color-disjoint paths on a graphs with ∆ = 4 nor to the case of ∆ ≥ 5.

Figure 2 :

 2 Figure 2: Example 2.

Figure 3 :

 3 Figure 3: Examples where C = {C 1 = {a, b, c}, C 2 = {d, e, f }, C 3 = {a, b, d}} (left) and C = {C 1 = {a, b, d}, C 2 = {b, c, d}, C 3 = {b, e, f }} (right). Colors are represented as numbers close to edges.

To show inequality 1 ,

 1 let us consider an optimal solution C OP T for MSP, C OP T = {c i1 , c i2 , . . . , c i |C OP T | }. We define a solution for I MDCP as the set P of paths P j = {s, v ij , t}, for each j = 1, 2, . . . , |C OP T |. It can be shown that the paths in P are color-disjoint by using the same arguments as in the Inria proof of Theorem 1. It follows that P is a feasible solution for I MDCP with |P | = |C OP T |, and then, OP T (I MSP ) = |C OP T | = |P | ≤ OP T (I MDCP ). To show inequality 2, let us define algorithm g as the one which transforms a set P of paths in the form {s, v ij , t}, j = 1, 2, . . . , |P | (which is a solution for I MDCP ) into a solution C for I MSP , where C = {c i1 , c i2 , . . . , c i |P | }. Again, it can be show that the elements of C are pairwise disjoint by using the same arguments used in the proof of Theorem 1 and then C is a feasible solution for MSP such that |P | = |C |. It follows that OBJ(S MDCP ) = |P | = |C | ≤ OBJ(S MSP ). Corollary 1 Unless P = N P , MDCP cannot be approximate within O

  consists of two pairs of distinct edges {e, f } and {g, h} where e, f, g and h are the 4 edges incident to v (i.e. T (v) = K 2 + K 2 , see Figure4a);• If d(v) = 3, T (v) consists of two pairs of edges {e, h} and {f, h} where e, f and h are the 3 edges incident to v (i.e. T (v) = P 3 , see Figure4b).

Figure 4 :

 4 Figure 4: Transition graphs used in the transformation.

Figure 5 :

 5 Figure 5: Color assignment for vertices with degree 4.

Property 2 Property 3

 23 If v = s, t, d(v) = 3 and E(T (v)) = {{e, h}, {f, h}}, then only the edges {v, x e } and {v, x e } share colors with edges {v, x f } and {v, x f }. If v = s, t, d(v) = 4 and E(T (v)) = {{e, f }, {g, h}}, then the edges {v, x e } and {v, x e } ({v, x g } and {v, x g }, resp.) share no colors and share colors with any other edge but {v, x f } and {v, x f } ({v, x h } and {v, x h }, resp.).

Figure 7 :

 7 Figure 7: Color assignment for a vertex of degree 4 ( = t).

Figure 8 :

 8 Figure 8: Color assignment for s.

Figure 9 :

 9 Figure 9: Transformation 1

Figure 10 :

 10 Figure 10: Transformation 2

  1 of the algorithm requires O(|V | + |E|) time. Step 2 requires O(|V | 2 ) as, in the worst case, G 1 has O(|V | 2 ) vertices and O(|V | 2 ) arcs. Step 3 adds O(∆ 2 ) arcs for each vertex and a vertex for each arc of G 1 and hence G 2 has O(|V | 2 ) vertices and O((|V |∆) 2 ) arcs. Therefore, Step 3 requires O((|V |∆) 2 ) time. In G 3 there are O(|V | 2k ) vertices and O((|V |∆) 2k ) edges. Hence Step 3 requires O((|V |∆) 2k ) time.

3

 3 and f o (t) = 4. Figures 12, 13 and 14 represent the graphs G 1 , G 2 and, G 3 obtained after applying Steps 2, 3, and 4 of the algorithm, respectively.

v 4 v 6 v 7 v 8 v 7 v 9 v 8 v 9 v 10 v 11 v 10 v 12 v 11 v 12 tFigure 14 :

 689911121214 Figure 14: G 3 = (V 3 , E 3 ) after applying the Step 4 of the algorithm (Transformation 2).

3 if 5 else 6 if 7 if

 3567 there exist 2 vertex-disjoint paths form {s 1 , s 2 } to {t 1 , t 2 } in G then 4 There exist two color-disjoint paths from s to t in G; all the cut-vertices from {s 1 , s 2 } to {t 1 , t 2 } in G have degree 4 then for each cut vertex v there exist two arcs e and f ingoing to v which are closer to s and the other two arcs g and h outgoing from v which are closer to t such that R(e) ∩ R(f ) = ∅, R(g) ∩ R(h) = ∅ R(e) ∩ R(h) = ∅, and R(f ) ∩ R(g) = ∅ then 8

Figure 15 :

 15 Figure 15: Algorithm for solving k-DCP when ∆ = 4.

  2.3. We add two vertices s and t and join s (resp. t) to the vertices e (resp. f ) associated to an arc e (resp. f ) having s (resp. t) as initial vertex (resp. terminal vertex) and give to the arc (s, e) (resp. (e, t)) the colors of e (resp f ) having s (resp. t) as center.

RR n°8071

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

The correctness and complexity of the above algorithm are shown in the next theorem. Proof. We prove the correctness by contradiction. First let us assume that the algorithm outputs k paths P 1 , P 2 , . . . , P k but they are not color-disjoint. These implies that there exists two paths P i and P j that share some colors, that is the corresponding set in C in the set packing instance of Step 4 are not disjoint, a contradiction.

Let us assume that the algorithm does not output the paths but that there exist k disjoint paths in G. Let us consider k disjoint paths P 1 , P 2 , . . . , P k in G and let C 1 , C 2 , . . . , C k be the sets of colors induced by them. Then these sets belongs to F at step 1 and are not removed from it at step 3 because for each C i there exists at least a path (e.g. P i ) from s to t. Moreover, as sets C 1 , C 2 , . . . , C k are disjoint, will be chosen at step 4 by the set packing algorithm.

The family

Bounded degree

In this section, we give algorithms for finding k color-disjoint paths when ∆ < 4 and for finding 2 color-disjoint paths when ∆ = 4. First, note that the maximum number of color-disjoint paths in a graph is upper bounded by ∆.

If ∆ ≤ 2 the problem is trivial as the graph is either a path or a cycle. In the first case, it always exists only one path from s and t. In the second case, the only vertices where the two possible paths can share colors are s and t and hence it is enough to check if the two arcs incident to s (and t) are color-disjoint.

If ∆ = 3, observe that if two different paths share a vertex, they necessarily share also an arc and hence all the colors of that arc. It follows that DCP can be solved by finding k ∈ {2, 3} vertex-disjoint paths from all the subsets of size k of the neighbors of s to all the subsets of size k of the neighbors of t. In detail, let S be the subsets of size k of Γ + (s) such that for each x ∈ S and for each s i , s j ∈ x, R((s, s i )) ∩ R((s, s j )) = ∅ and let T be the subsets of size k of Γ -(t) such that for each y ∈ T and for each t i , t j ∈ y, R((t i , t)) ∩ R((t j , t)) = ∅. Then, there exist k color-disjoint paths from s to t if and only if there exists k vertex-disjoint paths from a subset x of S to a subset y of T . As finding k ∈ {2, 3} vertex-disjoint paths requires linear time [START_REF] Hopcroft | Algorithm 447: efficient algorithms for graph manipulation[END_REF][START_REF] Hopcroft | Dividing a graph into triconnected components[END_REF], then the above algorithm requires

If ∆ = 4, the algorithm for solving 2-DCP is reported in Figure 15.

The correctness of the above algorithm is shown in the next theorem.

Theorem 7 There exists an algorithm that solves DCP if ∆ = 4 which requires O(|V | + |E|) computational time.

Proof. If there exist two neighbors s 1 and s 2 of s and two neighbors t 1 and t 2 of t such that R((s, s 1 )) ∩ R((s, s 2 )) = ∅ and R((t 1 , t)) ∩ R((s 2 , t)) = ∅, and there exists two vertex-disjoint paths from {s 1 , s 2 } to {t 1 , t 2 } in G , then such two paths are clearly color-disjoint in G.

Otherwise, for each pair {s 1 , s 2 } of neighbors of s and for each pair {t 1 , t 2 } of neighbors of t such that R({s, s 1 }) ∩ R({s, s 2 }) = ∅ and R((t 1 , t)) ∩ R((s 2 , t)) = ∅ there exists at least one cut vertex in G . If one of such cut vertices has degree 2 or 3, then each path from {s 1 , s 2 } to {t 1 , t 2 } has to share an edge and hence cannot exist color-disjoint paths from {s 1 , s 2 } to {t 1 , t 2 }. It follows that there exists two color-disjoint paths in G only if all the cut-vertices from some pair Inria