J Araujo
email: julio.araujo@inria.fr

J - C Bermond

F Giroire

F Havet

D Mazauric
email: dorian.mazauric@inria.fr

R Modrzejewski
email: remigiusz.modrzejewski@inria.fr

Weighted Improper Colouring. $

Keywords: graph colouring, improper colouring, interference, radio networks, frequency assignment

In this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc. We model this with a weighted graph (G, w) where the weight function w on the edges of G represents the noise (interference) between the two endvertices. The total interference in a node is then the sum of all the noises of the nodes emitting on the same frequency. A weighted t-improper k-colouring of (G, w) is a k-colouring of the nodes of G (assignment of k frequencies) such that the interference at each node does not exceed the threshold t. We consider here the Weighted Improper Colouring problem which consists in determining the weighted t-improper chromatic number defined as the minimum integer k such that (G, w) admits a weighted t-improper k-colouring. We also consider the dual problem, denoted the Threshold Improper Colouring problem, where, given a number k of colours, we want to determine the minimum real t such that (G, w) admits a weighted t-improper k-colouring. We first present general upper bounds for both problems; in particular we show a generalisation of Lovász's Theorem for the weighted t-improper chromatic number. Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes at distance two. We derive the weighted t-improper chromatic number for all values of t.

Introduction

Let G = (V, E) be a graph. A k-colouring of G is a function c : V → {1, . . . , k}. The colouring c is proper if uv ∈ E implies c(u) = c(v). The chromatic number of G, denoted by χ(G), is the minimum integer k such that G admits a proper k-colouring. The goal of the Vertex Colouring problem is to determine χ(G) for a given graph G. It is a well-known NP-hard problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

A k-colouring c is l-improper if |{v ∈ N (u) | c(v) = c(u)}| ≤ l, for all u ∈ V (as usual in the literature, N (u) stands for the set {v | uv ∈ E(G)}). Given a non-negative integer l, the l-improper chromatic number of a graph G, denoted by χ l (G), is the minimum integer k such that G admits an l-improper k-colouring. Given a graph G and an integer l, the Improper Colouring problem consists in determining χ l (G) and is also NP-hard [START_REF] Woodall | Improper colorings of graphs[END_REF][START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF]. Indeed, if l = 0, observe that χ 0 (G) = χ(G). Consequently, Vertex Colouring is a particular case of Improper Colouring.

In this work we define and study a new variation of the Improper Colouring problem for edge-weighted graphs. An edge-weighted graph is a pair (G, w) where G = (V, E) is a graph and w : E → R * + . Given an edge-weighted graph (G, w) and a colouring c of G, the interference of a vertex u in this colouring is defined by

I u (G, w, c) = {v∈N (u)|c(v)=c(u)} w(u, v).
For any non-negative real number t, called threshold, we say that c is a weighted t-improper k-colouring of (G, w) if c is a k-colouring of G such that I u (G, w, c) ≤ t, for all u ∈ V .

Given a threshold t ∈ R * + , the minimum integer k such that the graph G admits a weighted t-improper k-colouring is the weighted t-improper chromatic number of (G, w), denoted by χ t (G, w). Given an edge-weighted graph (G, w) and a threshold t ∈ R * + , determining χ t (G, w) is the goal of the Weighted Improper Colouring problem. Note that if t = 0 then χ 0 (G, w) = χ(G), and if w(e) = 1 for all e ∈ E, then χ l (G, w) = χ l (G) for any positive integer l. Therefore, the Weighted Improper Colouring problem is clearly NP-hard since it generalises Vertex Colouring and Improper Colouring.

On the other hand, given a positive integer k, we define the minimum kthreshold of (G, w), denoted by T k (G, w) as the minimum real t such that (G, w) admits a weighted t-improper k-colouring. Then, for a given edge-weighted graph (G, w) and a positive integer k, the Threshold Improper Colouring problem consists in determining T k (G, w). The Threshold Improper colouring problem is also NP-hard. This fact follows from the observation that determining whether χ l (G) ≤ k is NP-complete, for every l ≥ 2 and k ≥ 2 [START_REF] Cowen | Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency[END_REF][START_REF] Cowen | Defective coloring revisited[END_REF][START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF]. Consequently, in particular, it is a NP-complete problem to decide whether a graph G admits a weighted t-improper 2-colouring when all the weights of the edges of G are equal to one, for every t ≥ 2.

Motivation

Our initial motivation to these problems was the design of satellite antennas for multi-spot MFTDMA satellites [START_REF] Alouf | Quasioptimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF]. In this technology, satellites transmit signals to areas on the ground called spots. These spots form a grid-like structure which is modelled by an hexagonal cell graph. To each spot is assigned a radio channel or colour. Spots are interfering with other spots having the same channel and a spot can use a colour only if the interference level does not exceed a given threshold t. The level of interference between two spots depends on their distance. The authors of [START_REF] Alouf | Quasioptimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF] introduced a factor of mitigation γ and the interference of remote spots are reduced by a factor 1-γ. When the interference level is too low, the nodes are considered to not interfere anymore. Considering such types of interference, where nodes at distance at most i interfere, leads to the study of the i-th power of the graph modelling the network and a case of special interest is the power of grid graphs (see Section 3).

Related Work

Our problems are particular cases of the Frequency Assignment problem (FAP). FAP has several variations that were already studied in the literature (see [START_REF] Aardal | Models and solution techniques for frequency assignment problems[END_REF] for a survey). In most of these variations, the main constraint to be satisfied is that if two vertices (mobile phones, antennas, spots, etc.) are close, then the difference between the frequencies that are assigned to them must be greater than some function which usually depends on their distance.

There is a strong relationship between most of these variations and the L(p 1 , . . . , p d )-labelling problem [START_REF] Yeh | A survey on labeling graphs with a condition at distance two[END_REF]. In this problem, the goal is to find a colouring of the vertices of a given graph G, in such a way that the difference between the colours assigned to vertices at distance i is at least p i , for every i = 1, . . . , d.

In some other variants, for each non-satisfied interference constraint a penalty must be paid. In particular, the goal of the Minimum Interference Frequency Assignment problem (MI-FAP) is to minimise the total penalties that must be paid, when the number of frequencies to be assigned is given. This problem can also be studied for only co-channel interference, in which the penalties are applied only if the two vertices have the same frequency. However, MI-FAP under these constraints does not correspond to Weighted Improper Colouring, because we consider the co-channel interference, i.e. penalties, just between each vertex and its neighbourhood.

The two closest related works we found in the literature are [START_REF] Mannino | An enumerative algorithm for the frequency assignment problem[END_REF] and [START_REF] Fischetti | Frequency assignment in mobile radio systems using branch-and-cut techniques[END_REF]. However, they both apply penalties over co-channel interference, but also to the adjacent channel interference, i.e. when the colours of adjacent vertices differ by one unit. Moreover, their results are not similar to ours. In [START_REF] Mannino | An enumerative algorithm for the frequency assignment problem[END_REF], they propose an enumerative algorithm for the problem, while in [START_REF] Fischetti | Frequency assignment in mobile radio systems using branch-and-cut techniques[END_REF] a Branch-and-Cut method is proposed and applied over some instances.

Results

In this article, we study both parameters χ t (G, w) and T k (G, w). We first present general bounds; in particular we show a generalisation of Lovász's Theorem for χ t (G, w).

Motivated by the original application, we then study a special interference model on various grids (square, triangular, hexagonal) where a node produces a noise of intensity 1 for its neighbours and a noise of intensity 1/2 for the nodes that are at distance two. We derive the weighted t-improper chromatic number for all possible values of t. These proofs easily lead to optimal polynomial-time algorithms to find weighted improper colourings of these graphs. We also give an algorithm for trees for this interference model differing from the lower bound by at most 2.

General Results

In this section, we present some results for Weighted Improper colouring and Threshold Improper colouring for general graphs and general interference models.

Let (G, w) be an edge-weighted graph with positive rational weights given by w :

E(G) → Q * + . For any vertex v ∈ V (G), its weighted degree is d w (v) = u∈N (v) w(u, v). The maximum weighted degree of G is ∆(G, w) = max v∈V d w (v). Given a k-colouring c : V → {1, . . . , k} of G, we define, for every vertex v ∈ V (G) and colour i = 1, . . . , k, d i w,c (v) = {u∈N (v)|c(u)=i} (u, v). Note that d c(v) w,c (v) = I v (G, w, c).
We say that a k-colouring c of G is w-balanced if c satisfies the following property:

For any vertex v ∈ V (G), I v (G, w, c) ≤ d j
w,c (v), for every j = 1, . . . , k.

We denote by gcd(w) the greatest common divisor of the weights of w (observe that gcd(w) > 0 because we just consider positive weights). We use here the generalisation of the gcd to non-integer numbers (e.g. in Q) where a number x is said to divide a number y if the fraction y/x is an integer. The important property of gcd(w) is that the difference between two interferences is a multiple of gcd(w); in particular, if for two vertices v and u,

d i w,c (v) > d j w,c (u), then d i w,c (v) ≥ d j w,c (
u) + gcd(w). If t is not a multiple of the gcd(w), that is, there exists an integer a ∈ Z such that a gcd(w) < t < (a + 1)gcd(w), then χ w t (G) = χ w a gcd(w) (G).

Proposition 1. Let (G, w) be an edge-weighted graph. For any k ≥ 2, there exists a w-balanced k-colouring of G.

Proof. Let us colour G = (V, E) arbitrarily with k colours and then repeat the following procedure: if there exists a vertex v coloured i and a colour j such that d i w,c (v) > d j w,c (v), then recolour v with colour j. Observe that this procedure neither increases (we just move a vertex from one colour to another) nor decreases (a vertex without neighbour on its colour is never moved) the number of colours within this process. Let W be the sum of the weights of the edges having the same colour in their end-vertices. In this transformation, W has increased by d j w,c (v) (edges incident to v that previously had colour j in its endpoint opposite to v), but decreased by d i w,c (v) (edges that previously had colour i in both of their end-vertices). So, W has decreased by d i w,c (v)d j w,c (v) ≥ gcd(w). As W ≤ |E| max e∈E w(e) is finite, this procedure finishes and produces a w-balanced k-colouring of G.

The existence of a w-balanced colouring gives easily some upper bounds on the weighted t-improper chromatic number and the minimum k-threshold of an edge-weighted graph (G, w). It is a folklore result that χ(G) ≤ ∆(G) + 1, for any graph G. Lovász [START_REF] Lovász | On decompositions of graphs[END_REF] extended this result for Improper Colouring problem using w-balanced colouring. He proved that χ l (G) ≤ ⌈ ∆(G)+1 l+1 ⌉. In what follows, we extend this result to weighted improper colouring.

Theorem 2. Let (G, w) be an edge-weighted graph with w : E(G) → Q * + , and t a multiple of gcd(w). Then

χ t (G, w) ≤ ∆(G, w) + gcd(w) t + gcd(w) .
Proof. If t, ω, and G are such that χ t (G, ω) = 1, then the inequality is trivially satisfied. Thus, consider that χ t (G, ω) > 1.

Observe that, in any w-balanced k-colouring c of a graph G, the following holds:

d w (v) = u∈N (v) w(u, v) ≥ kd c(v) w,c (v). (1)
Let k * = ∆(G,w)+gcd(w) t+gcd(w)

≥ 2 and c * be a w-balanced k * -colouring of G. We claim that c * is a weighted t-improper k * -colouring of (G, w).

By contradiction, suppose that there is a vertex v in G such that c * (v) = i and that d i w,c (v) > t. Since c * is w-balanced, d j w,c (v) > t, for all j = 1, . . . , k * . By the definition of gcd(w) and as t is a multiple of gcd(w), it leads to d j w,c (v) ≥ t + gcd(w) for all j = 1, . . . , k * . Combining this inequality with Inequality (1), we obtain:

∆(G, w) ≥ d w (v) ≥ k * (t + gcd(w)), giving ∆(G, w) ≥ ∆(G, w) + gcd(w),
a contradiction. The result follows.

Note that when all weights are unit, we obtain the bound for the improper colouring derived in [START_REF] Lovász | On decompositions of graphs[END_REF]. Brooks [START_REF] Brooks | On colouring the nodes of a network[END_REF] proved that for a connected graph G, χ(G) = ∆(G)+1 if, and only if, G is complete or an odd cycle. One could wonder for which edge-weighted graphs the bound we provided in Theorem 2 is tight. However, Correa et al. [START_REF] Correa | About a Brooks-type theorem for improper colouring[END_REF] already showed that it is NP-complete to determine if the improper chromatic number of a graph G attains the upper bound of Lovász, which is a particular case of Weighted Improper colouring, i.e. of the bound of Theorem 2.

We now show that w-balanced colourings also yield upper bounds for the minimum k-threshold of an edge-weighted graph (G, w). When k = 1, then all the vertices must have the same colour, and T 1 (G, w) = ∆(G, w). This may be generalised as follows, using w-balanced colourings.

Theorem 3. Let (G, w) be an edge-weighted graph with w : E(G) → R * + , and let k be a positive integer. Then

T k (G, w) ≤ ∆(G, w) k .
Proof. Let c be a w-balanced k-colouring of G. Then, for every vertex v ∈ V (G):

kT k (G, w) ≤ kd c(v) w,c (v) ≤ d w (v) = u∈N (v) w(u, v) ≤ ∆(G, w)
Because T 1 (G, w) = ∆(G, w), Theorem 3 may be restated as kT k (G, w) ≤ . . . ≤ T 1 (G, w). This inequality may be generalised as follows. Proof. Set t = T p (G, w). Let c be a t-improper p-colouring of (G, w). For i = 1, . . . , p, let G i be the subgraph of G induced by the vertices coloured i by c. By definition of improper colouring ∆(G i , w) ≤ t for all 1 ≤ i ≤ p. By Theorem 3, each (G i , w) admits a t/k-improper k-colouring c i with colours {(i -1)k + 1, . . . , ik}. The union of the c i 's is then a t/k-improper kp-colouring of (G, w).

Theorem 4 and its proof suggest that to find a kp-colouring with small impropriety, it may be convenient to first find a p-colouring with small impropriety and then to refine it. In addition, such a strategy allows to adapt dynamically the refinement. In the above proof, the vertex set of each part G i is again partitioned into k parts. However, sometimes, we shall get a better kp-colouring by partitioning each G i into a number of k i parts, with p i=1 k i = kp. Doing so, we obtain a T -improper kp-colouring of (G, w), where T = max{ ∆(Gi,w) ki , 1 ≤ i ≤ p}.

One can also find an upper bound on the minimum k-threshold by considering first the k -1 edges of largest weight around each vertex. Let (G, w) be an edge-weighted graph, and let v 1 , . . . , v n be an ordering of the vertices of G. The edges of G may be ordered in increasing order of their weight. Furthermore, to make sure that the edges incident to any particular vertex are totally ordered, we break ties according to the label of the second vertex. Formally, we say that

v i v j ≤ w v i v j ′ if either w(v i v j ) < w(v i v j ′ ) or w(v i v j ) = w(v i v j ′ ) and j < j ′ .
With such a partial order on the edge set, the set E k w (v) of min{|N (v)|, k -1} greatest edges (according to this ordering) around a vertex is uniquely defined. Observe that every edge incident to v and not in

E k w (v) is smaller than an edge of E k (v) for ≤ w .
Let G k w be the graph with vertex set V (G) and edge set v∈V (G) E k w (v). Observe that every vertex of E k w (v) has degree at least min{|N (v)|, k -1}, but a vertex may have an arbitrarily large degree. For if any edge incident to v has a greater weight than any edge not incident to v, the degree of v in G k w is equal to its degree in G. However we now prove that at least one vertex has degree k -1.

Proposition 5. If (G, w) is an edge-weighted graph, then G k w has a vertex of degree at most k -1.
Proof. Suppose for a contradiction, that every vertex has degree at least k, then for every vertex x there is an edge xy in E(G k w )\E k w (x), and so in E k w (y)\E k w (x). Therefore, there must be a cycle (x 1 , . . . , x r ) such that, for all 1

≤ i ≤ r, x i x i+1 ∈ E k w (x i+1 ) \ E k w (x i ) (with x r+1 = x 1 ). It follows that x 1 x 2 ≤ w x 2 x 3 ≤ w • • • ≤ w x r x 1 ≤ w x 1 x 2 . Hence, by definition, w(x 1 x 2 ) = w(x 2 x 3 ) = • • • = w(x r x 1 ) = w(x 1 x 2 ).
Let m be the integer such that x m has maximum index in the ordering v 1 , . . . , v n . Then there exists j and j ′ such that x m = v j and x m+2 = v j ′ . By definition of m, we have j > j ′ . But this contradicts the fact that x m x m+1 ≤ w x m+1 x m+2 . Corollary 6. If (G, w) is an edge-weighted graph, then G k w has a proper kcolouring.

Proof. By induction on the number of vertices. By Proposition 5, G k w has a vertex x of degree at most k -1. Trivially, G k w -x is a subgraph of (G -x) k w . By the induction hypothesis, (G -x) k w has a proper k-colouring, which is also a proper k-colouring of G k w -x. This colouring can be extended in a proper k-colouring of G k w , by assigning to x a colour not assigned to any of its k -1 neighbours.

Corollary 7. If (G, w) is an edge-weighted graph, then T k (G, w) ≤ ∆(G \ E(G k w ), w).

Squares of Particular Graphs

As mentioned in the introduction, Weighted Improper colouring is motivated by networks of antennas similar to grids [START_REF] Alouf | Quasioptimal bandwidth allocation for multi-spot MFTDMA satellites[END_REF]. In these networks, the noise generated by an antenna undergoes an attenuation with the distance it travels. It is often modelled by a decreasing function of d, typically 1/d α or 1/(2 d-1 ).

Here we consider a simplified model where the noise between two neighbouring antennas is normalised to 1, between antennas at distance two is 1/2 and 0 when the distance is strictly greater than two. Studying this model of interference corresponds to study the Weighted Improper colouring of the square of the graph G, that is the graph G 2 obtained from G by joining every pair of vertices at distance two, and to assign weights w 2 (e) = 1, if e ∈ E(G), and

w 2 (e) = 1/2, if e ∈ E(G 2 ) \ E(G).
Observe that in this case the interesting threshold values are the non-negative multiples of 1/2.

Figure 1 shows some examples of colouring for the square grid. In Figure 1(b), each vertex x has neither a neighbour nor a vertex at distance two coloured with its own colour, so I x (G 2 , w 2 , c) = 0 and G 2 admits a weighted 0-improper 5-colouring. In Figure 1(c), each vertex x has no neighbour with its colour and at most one vertex of the same colour at distance 2. So I x (G 2 , w 2 , c) = 1/2 and G 2 admits a weighted 0.5-improper 4-colouring.

For any t ∈ R + , we determine the weighted t-improper chromatic number for the square of infinite paths, square grids, hexagonal grids and triangular grids under the interference model w 2 . We also present lower and upper bounds for χ t (T 2 , w 2 ), for any tree T and any threshold t.

Infinite paths and trees

In this section, we characterise the weighted t-improper chromatic number of the square of an infinite path, for all positive real t. Moreover, we present lower and upper bounds for χ t (T 2 , w 2 ), for a given tree T .

Theorem 8. Let P = (V, E) be an infinite path. Then,

χ t (P 2 , w 2 ) =      3, if 0 ≤ t < 1; 2, if 1 ≤ t < 3; 1, if 3 ≤ t. Proof. Let V = {v i | i ∈ Z} and E = {(v i-1 , v i ) | i ∈ Z}.
Each vertex of P has two neighbours and two vertices at distance two. Consequently, the equivalence χ t (P 2 , ω 2 ) = 1 if, and only if, t ≥ 3 holds trivially.

There is a 2-colouring c of (P 2 , w 2 ) with maximum interference 1 by just colouring v i with colour (i mod 2) + 1. So χ t (P 2 , w 2 ) ≤ 2 if t ≥ 1. We claim that there is no weighted 0.5-improper 2-colouring of (P 2 , w 2 ). By contradiction, suppose that c is such a colouring

. If c(v i ) = 1, for some i ∈ Z, then c(v i-1 ) = c(v i+1 ) = 2 and c(v i-2 ) = c(v i+2 ) = 1. This is a contradiction because v i would have interference 1.
Finally, the colouring c(v i ) = (i mod 3) + 1, for every i ∈ Z, is a feasible weighted 0-improper 3-colouring. Theorem 9. Let T = (V, E) be a (non-empty) tree. Then, ∆(T )-⌊t⌋ 2t+1

+ 1 ≤ χ t (T 2 , w 2 ) ≤ ∆(T )-1 2t+1 + 2.
Proof. The lower bound is obtained by two simple observations. First, χ t (H, w) ≤ χ t (G, w), for any H ⊆ G. Let T be a tree and v be a node of maximum degree in T . Then, observe that the weighted t-improper chromatic number of the subgraph of T 2 induced by v and its neighbourhood is at least ⌈ ∆(T )-⌊t⌋ 2t+1 ⌉ + 1. Indeed, the colour of v can be assigned to at most ⌊t⌋ vertices on its neighbourhood. Any other colour used in the neighbourhood of v cannot appear in more than 2t + 1 vertices because each pair of vertices in the neighbourhood of v is at distance two.

Let us look now at the upper bound. Choose any node r ∈ V to be the root of T . Colour r with colour 1. Then, by a breadth-first traversal in the tree, for each visited node v colour all the children of v with the ⌈ ∆(T )-1 2t+1 ⌉ colours different from the ones assigned to v and to its parent in such a way that at most 2t + 1 nodes have the same colour. This is a feasible weighted t-improper k-colouring of T 2 , with k ≤ ⌈ ∆(T )-1 2t+1 ⌉ + 2, since each vertex interferes with at most 2t vertices at distance two which are children of its parent.

For a tree T and the weighted function w 2 , Theorem 9 provides upper and lower bounds on χ t (T 2 , w 2 ), but we do not know the computational complexity of determining χ t (T 2 , w 2 ).

Grids

In this section, we show the optimal values of χ t (G 2 , w 2 ), whenever G is an infinite square, hexagonal or triangular grid, for all the possible values of t.

Square Grid

The square grid is the graph S in which the vertices are all integer linear combinations ae 1 + be 2 of the two vectors e 1 = (1, 0) and e 2 = (0, 1), for any a, b ∈ Z. Each vertex (a, b) has four neighbours: its down neighbour (a, b -1), its up neighbour (a, b + 1), its right neighbour (a + 1, b) and its left neighbour (a -1, b) (see Figure 1(a)).

Theorem 10.

χ t (S 2 , w 2 ) =                5, if t = 0; 4, if t = 0.5; 3, if 1 ≤ t < 3; 2, if 3 ≤ t < 8; 1, if 8 ≤ t.
Proof. If t = 0, then the colour of vertex (a, b) must be different from the ones used on its four neighbours. Moreover, all the neighbours have different colours, as each pair of neighbours is at distance two. Consequently, at least five colours are needed. The following construction provides a weighted 0-improper 5-colouring of (S 2 , w 2 ): for 0 ≤ j ≤ 4, let A j = {(j, 0) + a(5e 1 ) + b(2e 1 + 1e 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 4, assign the colour j + 1 to all the vertices in A j (see Figure 1(b)).

4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 4 1 2 3 1 2 3 4 1 2 3 4 1 2 3 2 1 3 2 4 3 (c) 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (d)
Figure 1: Optimal colourings of (S 2 , w 2 ): (b) weighted 0-improper 5-colouring of (S 2 , w 2 ), (c) weighted 0.5-improper 4-colouring of (S 2 , w 2 ), and (d) weighted 3-improper 2-colouring of (S 2 , w ). When t = 0.5, we claim that at least four colours are needed to colour (S 2 , w 2 ). The proof is by contradiction. Suppose that there exists a weighted 0.5-improper 3-colouring of it. Let (a, b) be a vertex coloured 1. None of its neighbours is coloured 1, otherwise (a, b) has interference 1. If three neighbours have the same colour, then each of them will have interference 1. So two of its neighbours have to be coloured 2 and the two other ones 3 (see Figure 2(a)). Now consider the four nodes (a -1, b -1), (a -1, b + 1), (a + 1, b -1) and (a + 1, b + 1). For all configurations, at least two of these four vertices have to be coloured 1 (the ones indicated by a * in Figure 2(a)). But then (a, b) will have interference at least 1, a contradiction. A weighted 0.5-improper 4colouring of (S 2 , w 2 ) can be obtained as follows (see Figure 1(c)): for 0 ≤ j ≤ 3, let B j = {(j, 0)+a(4e 1 )+b(3e

1 +2e 2 ) | ∀a, b ∈ Z} and B ′ j = {(j +1, 2)+a(4e 1 )+ b(3e 1 +2e 2 ) | ∀a, b ∈ Z}.
For 0 ≤ j ≤ 3, assign the colour j +1 to all the vertices in B j and in B ′ j . If t = 1, there exists a weighted 1-improper 3-colouring of (S 2 , w 2 ) given by the following construction: for 0 ≤ j ≤ 2, let C j = {(j, 0) + a(3e 1 ) + b(e 1 + e 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 2, assign the colour j + 1 to all the vertices in C j . Now we prove by contradiction that for t = 2.5 we still need at least three colours in a weighted 2.5-improper colouring of (S 2 , w 2 ). Consider a weighted 2.5-improper 2-colouring of (S 2 , w 2 ) and let (a, b) be a vertex coloured 1. Vertex (a, b) has at most two neighbours of colour 1, otherwise it will have interference 3. We distinguish three cases:

1. Exactly one of its neighbours is coloured 1; let (a -1, b) be this vertex. Then, the three other neighbours are coloured 2 (see Figure 2 A weighted 3-improper 2-colouring of (S 2 , w 2 ) can be obtained as follows: a vertex of the grid (a, b) is coloured with colour ( a 2 + b 2 mod 2) + 1, see Figure 1(d).

Finally, since each vertex has four neighbours and eight vertices at distance two, there is no weighted 7.5-improper 1-colouring of (S 2 , w 2 ) and, whenever t ≥ 8, one colour suffices.

Hexagonal Grid

There are many ways to define the system of coordinates of the hexagonal grid. Here, we use grid coordinates as shown in Figure 3 Proof. Note first, that when t = 0, at least four colours are needed to colour the grid, because a vertex and its neighbourhood in H form a clique of size four in coloured 2 (interference in C) nor 3 (interference in E). So H is coloured 1. The vertex I is coloured 3, otherwise the interference constraint in H or in C is not satisfied. Then, J can receive neither colour 1, because of the interference in H, nor colour 2, because of the interference in C, nor colour 3, because of the interference in I.

χ t (H 2 , w 2 ) =          4, if 0 ≤ t < 1; 3, if 1 ≤ t < 2; 2, if 2 ≤ t < 6; 1, if 6 ≤ t.
There exists a construction attaining this bound and the number of colours, i.e. a 0-improper 4-colouring of (H 2 , w 2 ) as depicted in Figure 3. We define for 0 ≤ j ≤ 3 the sets of vertices A j = {(j, 0) + a(4e 1 ) + b(2e 1 + e 2 )|∀a, b ∈ Z}. We then assign the colour j +1 to the vertices in A j . This way no vertex experiences any interference as vertices of the same colours are at distance at least three.

For t = 1.5 it is not possible to colour the grid with less than three colours. By contradiction, suppose that there exists a weighted 1.5-improper 2-colouring. Consider a vertex A coloured 1. If all of its neighbours are coloured 2, they have already interference 1, so all the vertices at distance two from A need to be coloured 1; this gives interference 3 in A. Therefore one of A's neighbours, say D, has to be coloured 1 and consider that the other two neighbours B and C are coloured 2. B and C have at most one neighbour of colour 2. It implies that A has at least two vertices at distance two coloured 1. This is a contradiction, because the interference in A would be at least 2 (see Figure 5(b)).

Figure 4(a) presents a weighted 1-improper 3-colouring of (H 2 , w 2 ). To obtain this colouring, let B j = {(j, 0) + a(3e 1 ) + b(e 1 + e 2 ) | ∀a, b ∈ Z}, for 0 ≤ j ≤ 2. Then, we colour all the vertices in the set B j with colour j + 1, for every 0 ≤ j ≤ 2.

For t < 6, it is not possible to colour the grid with one colour. As a matter of fact, each vertex has three neighbours and six vertices at distance two in H. Using one colour leads to an interference equal to 6. There exists a 2-improper 2-colouring of the hexagonal grid as depicted in Figure 4(b). We define for 0 ≤ j ≤ 1 the sets of vertices C j = {(j, 0) + a(2e 1 ) + be 2 |∀a, b ∈ Z}. We then assign the colour j + 1 to the vertices in C j .

Triangular Grid

The triangular grid is the graph T whose vertices are all the integer linear combinations af 1 + bf 2 of the two vectors f 1 = (1, 0) and

f 2 = ( 1 2 , √ 3
2 ). Thus we may identify the vertices with the ordered pairs (a, b) of integers. Each vertex v = (a, b) has six neighbours: its right neighbour (a + 1, b), its right-up neighbour (a, b+1), its left-up neighbour (a-1, b+1), its left neighbour (a-1, b), its left-down neighbour (a, b -1) and its right-down neighbour (a + 1, b -1) (see Figure 7(a)).

Theorem 12.

χ t (T 2 , w 2 ) =                        7, if t = 0; 6, if t = 0.5; 5, if t = 1; 4, if 1.5 ≤ t < 3; 3, if 3 ≤ t < 5; 2, if 5 ≤ t < 12; 1, if 12 ≤ t.
Proof. If t = 0, there is no weighted 0-improper 6-colouring of (T 2 , w 2 ), since in T 2 there is a clique of size seven induced by each vertex and its neighbourhood. There is a weighted 0-improper 7-colouring of (T 2 , w 2 ) as depicted in Figure 6(a). This colouring can be obtained by the following construction: for 0 ≤ j ≤ 6, let A j = {(j, 0) + a(7f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 6, assign the colour j + 1 to all the vertices in A j .

In what follows, we denote by V 0 a vertex coloured 1 and by N 0 , N 1 , N 2 , N 3 , N 4 , N 5 the six neighbours of V 0 in T in a cyclic order. Let Γ 2 be the set of twelve vertices at distance two of V 0 in which N i(i+1) denotes the vertex adjacent to both N i and N i+1 and N ii the vertex joined only to N i . For every 0 ≤ i ≤ 5, i + 1 is taken modulo 6 (see Figure 7(b)).

We claim that there is no weighted 0.5-improper 5-colouring of (T 2 , w 2 ). We prove it by contradiction, thus let c be such a colouring. No neighbour of V 0 can be coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 1. As two consecutive neighbours are adjacent, they cannot have the same colour. Furthermore, there cannot be three neighbours with the same colour (each of them will have an interference at least 1). As there are four colours different from 1, exactly two of them, say 2 and 3, are repeated twice among the six neighbours. So, there exists a sequence of three consecutive neighbours the first one with a colour different from 2 and 3 and the two others coloured 2 and 3. W.l.o.g., let c(N 5 ) = 4, c(N 0 ) = 2, c(N 1 ) = 3.

Note that the vertices coloured 2 and 3 have already an interference of 0.5, and so none of their vertices at distance two can be coloured 2 or 3. In particular, let A = {N 50 , N 00 , N 01 , N 11 , N 12 }; the vertices of A cannot be coloured 2 or 3. At most one vertex in Γ 2 can be coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 1. If (d) there is no vertex coloured 1 in A, we have a contradiction as we cannot have a sequence of five vertices uniquely coloured 4 and 5 (indeed colours should alternate and the vertex in the middle N 01 will have interference at least 1). Suppose N 4 is coloured 3, then N 45 and N 55 can only be coloured 1 and 5; but, as they have different colours, one is coloured 1 and so there is no vertex coloured 1 in A. So the second vertex coloured 3 in the neighbourhood of V 0 is necessarily N 3 (it cannot be N 2 neighbour of N 1 coloured 3). Then, N 4 cannot be also coloured 5, otherwise N 45 is coloured 1 and again there is no vertex coloured 1 in A. In summary c(N 4 ) = 2, c(N 3 ) = 3 and the vertex of Γ 2 coloured 1 is in A. But then the five consecutive vertices A ′ = {N 23 , N 33 , N 34 , N 44 , N 45 } can only be coloured 4 and 5. A contradiction as I N34 (T 2 , w 2 , c) ≥ 1. A weighted 0.5-improper 6-colouring of (T 2 , w 2 ) can be obtained by the following construction (see Figure 6(b)): for 0 ≤ j ≤ 11, let B j = {(j, 0) + a(12f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 5, assign the colour j + 1 to all the vertices in B j , B 6 with colour 2, B 7 with colour 1, B 8 with colour 4, B 9 with colour 3, B 10 with colour 6 and B 11 with colour 5. Now we prove that (T 2 , w 2 ) does not admit a weighted 1-improper 4-colouring. Again, by contradiction, suppose that there exists a weighted 1-improper 4colouring c of (T 2 , w 2 ). We analyse some cases:

1 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 (e) 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 (f)
1. There exist two adjacent vertices in T with the same colour.

Let V 0 and one of its neighbours be both coloured 1. Note that no other neighbour of V 0 , nor the vertices at distance two from V 0 are coloured 1 (otherwise, I V0 (T 2 , w 2 , c) > 1). We use intensively the following facts: Fact 1. There do not exist three consecutive vertices with the same colour (otherwise the vertex in the middle would have interference at least 2). Fact 2. In a path of five vertices there cannot be four of the same colour (otherwise the second or the fourth vertex in this path would have interference at least 1.5).

One colour other than 1 should appear at least twice in the neighbourhood of V 0 . Let this colour be denoted 2 (the other colours being denoted 3 and 4). To obtain a weighted 1-improper 5-colouring of (T 2 , w 2 ), for 0 ≤ j ≤ 4, let C j = {(j, 0) + a(5f 1 ) + b(2f 1 + f 2 ) | ∀a, b ∈ Z}. For 0 ≤ j ≤ 4, assign the colour j + 1 to all the vertices in C j . See Figure 6(c).

I N0 (T 2 , w 2 , c) > 1 (respectively I N2 (T 2 , w 2 , c) > 1). One of N 3 and N 5 is not coloured 1, say N 3 . It is not coloured 2, otherwise I N3 (T 2 , w 2 , c) > 1. Let c(N 3 ) = 3. If N 4 or
(T 2 , w 2 ) has a weighted 1.5-improper 4-colouring as depicted in Figure 6(d). Formally, this colouring can be obtained by the following construction: for 0 ≤ j ≤ 3, let D j = {(j, 0) + a(4f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z}; then assign colour 4 to all the vertices in D 0 , 1 to all the vertices in D 1 , 3 to all the vertices in D 2 and 2 to all the vertices in D 3 . Now, for 0

≤ j ≤ 3, let D ′ j = {(j, 1) + a(4f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z}.
Then, for 0 ≤ j ≤ 3, assign colour j + 1 to all the vertices in D ′ j . The proof that (T 2 , w 2 ) does not admit a weighted 2.5-improper 3-colouring can be found in [START_REF] Araujo | Weighted Improper Colouring[END_REF]. The proof uses the same tools as for the other cases, but we have to distinguish a great number of cases and subcases and being around 30 pages long we omitted it. It is worth noting that for the proof we only need to consider vertices at distance at most three from the vertex V 0 . Now we present the colouring providing the corresponding upper bound. For a weighted 3-improper 3-colouring of (T 2 , w 2 ) set, for 0 ≤ j ≤ 2, E j = {(j, 0) + a(3f 1 ) + b(f 2 ) | ∀a, b ∈ Z}. Then, for 0 ≤ j ≤ 2, assign the colour j + 1 to all the vertices in E j . See Figure 6(e). Now we prove that (T 2 , w 2 ) does not admit a weighted 4.5-improper 2colouring. Again, by contradiction, suppose that there exists a weighted 4.5improper 2-colouring c of (T 2 , w 2 ) with the interference function w 2 . A vertex can have at most four neighbours of the same colour as it. We analyse some cases:

1. There exists a vertex V 0 with four of its neighbours coloured with its own colour, say 1. Therefore among the vertices of Γ 2 at most one is coloured 1. Consider the two neighbours of V 0 coloured 2. First, consider the case in which they are adjacent and let them be N 0 and N 1 . In Γ 2 , N 0 has three neighbours and four vertices at distance two; since at most one being of colour 1, these vertices produce in N 0 an interference equal to 4 and as N 1 is also of colour 2, then I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. In case the two neighbours of V 0 coloured 2 are non adjacent, let them be N i and N j . At least one of them, say N i has its three neighbours in Γ 2 coloured 2 and it has also at least three vertices at distance two in Γ 2 coloured 2; taking into account that N j is coloured 2 and at distance two from N i , we get I Ni (T 2 , w 2 , c) ≥ 5, a contradiction.

2.

No vertex has four neighbours with its colour and there exists at least one vertex V 0 coloured 1 that has three neighbours of the same colour 1.

(a) The three other neighbours of V 0 coloured 2 are consecutive and let them be N 0 , N

0 , N 1 , N 2 in Γ 2 is coloured 1, otherwise I V0 (T 2 , w 2 , c) ≥ 5.
Furthermore all the other vertices of Γ 2 are coloured 2. Then, if c(N 12 ) = c(N 45 ) = 2, we conclude that I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. Consequently, w.l.o.g., suppose that c(N 12 ) = 1. In this case, N 23 has at least three neighbours coloured 2 and we are in some previous case.

3. No vertex has three neighbours coloured with its own colour, but there exists at least one vertex, say V 0 , of colour 1 that has two neighbours coloured 1. A weighted 5-improper 2-colouring of (T 2 , w 2 ) is obtained as follows: for 0 ≤ j ≤ 1, let F j = {(j, 0) + a(2f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z} and F ′ j = {(j -1, 1) + a(2f 1 ) + b(f 1 + 2f 2 ) | ∀a, b ∈ Z}. Then, for 0 ≤ j ≤ 1, assign the colour j + 1 to all the vertices in F j and in F ′ j . See Figure 6(f). Since each vertex has six neighbours and twelve vertices at distance two in T, there is no weighted t-improper 1-colouring of (T 2 , w 2 ), for any t < 12. Obviously, there is a weighted 12-improper 1-colouring of T 2 .

Conclusion, Open Problems and Future Directions

In this paper, we introduced and studied a new colouring problem, Weighted Improper Colouring. This problem is motivated by the design of telecommunication antenna networks in which the interference between two vertices depends on different factors and can take various values. For each vertex, the sum of the interferences it receives should be less than a given threshold value.

We first give general bounds on the weighted-improper chromatic number. We then study the particular case of infinite paths, trees and grids: square, hexagonal and triangular. For these graphs, we provide their weighted-improper chromatic number for all possible values of t.

Many problems remain to be solved:

• In the study of the grid graphs, we considered a specific function where vertices at distance one interfere by 1 and vertices at distance two by 1/2. Other weight functions should be considered. e.g. 1/d2 or 1/(2 d-1 ), where d is the distance between vertices.

• Other families of graphs could be considered, for example hypercubes.

• We showed in [START_REF] Araujo | Weighted Improper Colouring[END_REF] that the Threshold Improper Colouring problem can be transformed into a problem with only two possible weights on the edges 1 and ∞, that is a mix of proper and improper colouring. This simplifies the nature of the graph interferences but at the cost of an important increase of instance sizes. We want to further study this. In particular, let G = (V, E, w) be an edge-weighted graph where the weights are all equal to 1 or M . Let G M be the subgraph of G induced by the edges of weight M ; is it true that if ∆(G M ) ≪ ∆(G), then χ t (G, w) ≤ χ t (G) ≤ ∆(G,w)+1 t+1 ?

A similar result for L(p, 1)-labelling [START_REF] Havet | L(2,1)-labelling of graphs[END_REF] suggests it could be true.

Note that the problem can also be solved algorithmically for other classes of graphs and for other functions of interference. We started looking in this direction in [START_REF] Araujo | Weighted Improper Colouring[END_REF]. The problem can be expressed as a linear program and then be solved exactly using solvers such as CPLEX 1 or Glpk 2 for small instances of graphs. For larger instances, we propose a heuristic algorithm inspired by DSATUR [START_REF] Brélaz | New methods to color the vertices of a graph[END_REF] but adapted to the specifics of our colouring problem. We used it to derive colourings with few colours for Poisson-Voronoi tessellations as they are good models of antenna networks [START_REF] Baccelli | Stochastic geometry and architecture of communication networks[END_REF][START_REF] Gupta | The capacity of wireless networks[END_REF][START_REF] Haenggi | Stochastic geometry and random graphs for the analysis and design of wireless networks. Selected Areas in Communications[END_REF]. We plan to further investigate the algorithmic side of our colouring problem.

Theorem 4 .

 4 Let (G, w) be an edge-weighted graph with w : E(G) → R + , and let k and p be two positive integers. Then T kp (G, w) ≤ T p (G, w) k .

Figure 2 :

 2 Figure 2: Lower bounds for the square grid: (a) if t ≤ 0.5 and k ≤ 3, there is no weighted t-improper k-colouring of (S 2 , w 2 ); (b) the first case when t ≤ 2.5 and k ≤ 2, and (c) the second case.

3 .

 3 (b)). Consider the two sets of vertices {(a -1, b -1), (a + 1, b -1), (a, b -2)} and {(a -1, b + 1), (a + 1, b + 1), (a, b + 2)} (these sets are surrounded by dotted lines in Figure 2(b)); each of them has at least two vertices coloured 1, otherwise the vertex (a, b -1) or (a, b + 1) will have interference 3. But then (a, b) having four vertices at distance two coloured 1 has interference 3, a contradiction. 2. Two neighbours of (a, b) are coloured 1. (a) These two neighbours are opposite, say (a -1, b) and (a + 1, b) (see Figure 2(c) left). Consider again the two sets {(a -1, b -1), (a + 1, b -1), (a, b -2)} and {(a -1, b + 1), (a + 1, b + 1), (a, b + 2)} (these sets are surrounded by dotted lines in Figure 2(c) left); they both contain at least one vertex of colour 1 and therefore (a, b) will have interference 3, a contradiction. (b) The two neighbours of colour 1 are of the form (a, b -1) and (a -1, b) (see Figure 2(c) right). Consider the two sets of vertices {(a + 1, b -1), (a + 1, b + 1), (a+2, b)} and {(a+1, b+1), (a-1, b+1), (a, b+2)} (these sets are surrounded by dotted lines in Figure 2(c) right); these two sets contain at most one vertex of colour 1, otherwise (a, b) will have interference 3. Moreover, each of these sets cannot be completely coloured 2, otherwise (a + 1, b) or (a, b + 1) will have interference at least 3. So vertices (a + 1, b-1), (a + 2, b), (a, b + 2) and (a-1, b + 1) are of colour 2 and the vertex (a + 1, b + 1) is of colour 1. But then (a -2, b) and (a -1, b -1) are of colour 2, otherwise (a, b) will have interference 3. Thus, vertex (a -1, b) has exactly one neighbour coloured 1 and we are again in Case 1. All neighbours of (a, b) are coloured 2. If one of these neighbours has itself a neighbour (distinct from (a, b)) of colour 2, we are in Case 1 or 2 for this neighbour. Therefore, all vertices at distance two from (a, b) have colour 1 and the interference in (a, b) is 4, a contradiction.

  . The hexagonal grid graph is then the graph H whose vertex set consists of pairs of integers (a, b) ∈ Z 2 and where each vertex (a, b) has three neighbours: (a -1, b), (a + 1, b), and (a, b + 1) if a + b is odd, or (a, b -1) otherwise. Theorem 11.

Figure 3 :

 3 Figure 3: Weighted 0-improper 4-colouring of (H 2 , w 2 ). Left: Graph with coordinates. Right: Corresponding hexagonal grid in the euclidean space.

1 (b) t = 2 , k = 2 Figure 4 :

 1224 Figure 4: (a) weighted 1-improper 3-colouring of (H 2 , w 2 ) and (b) weighted 2-improper 2colouring of (H 2 , w 2 ).

H 2 .Figure 5 :

 25 Figure 5: Lower bounds for the hexagonal grid. (a) when t ≤ 0.5 and k ≤ 3, there is no weighted t-improper k-colouring of (H 2 , w 2 ); (b) vertices coloured 2 force a vertex coloured 1 in each ellipse, leading to interference 2 in central node.

Figure 6 :Figure 7 :

 67 Figure 6: Optimal colourings of (T 2 , w 2 ): (a) weighted 0-improper 7-colouring, (b) weighted 0.5-improper 6-colouring, (c) weighted 1-improper 5-colouring, (d) weighted 1.5-improper 4colouring, (e) weighted 3-improper 3-colouring, and (f) weighted 5-improper 2-colouring.

  (a) Two neighbours of V 0 coloured 2 are consecutive, say N 0 and N 1 . By Fact 1, N 2 is coloured 3 w.l.o.g. None of N 05 , N 00 , N 01 , N 11 , N 12 , N 22 and N 23 can be coloured 2, otherwise I N1 (T 2 , w 2 , c) > 1. One of N 12 , N 22 and N 23 is coloured 3, otherwise we contradict Fact 1 with colour 4 and at most one of N 01 , N 11 , N 12 , N 22 and N 23 is coloured 3, otherwise I N2 (T 2 , w 2 , c) > 1; but we have a contradiction with Fact 2. (b) Two neighbours of V 0 coloured 2 are at distance two, say N 0 and N 2 . Then N 50 , N 00 and N 01 (respectively N 12 , N 22 and N 23 ) are not coloured 2, otherwise

2 .

 2 No colour appears in two adjacent vertices of T.Let V 0 be coloured 1. No colour can appear four or more times among the neighbours of V 0 , otherwise there are two adjacent neighbours with the same colour. (a) One colour appears three times among the neighbours of V 0 , say c(N 0 ) = c(N 2 ) = c(N 4 ) = 2. W.l.o.g., let c(N 1 ) = 3. No vertex at distance two can be coloured 2. N 01 , N 11 and N 12 being neighbours of N 1 cannot be coloured 3 and they cannot be all coloured 4. So one of N 01 , N 11 , N 12 is coloured 1. Similarly one of N 23 , N 33 , N 34 is coloured 1 (same reasoning with N 3 instead of N 1 ) and one of N 45 , N 55 , N 50 is coloured 1, so I V0 (T 2 , w 2 , c) > 1. (b) The three colours appear each exactly twice in the neighbourhood of V 0 . i. The same colour appears in some N i and N i+2 , 0 ≤ i ≤ 3. W.l.o.g., let c(N 0 ) = c(N 2 ) = 2 and c(N 1 ) = 3. Then, c(N 3 ) = c(N 5 ) = 4 and c(N 4 ) = 3. Then, c(N 50 ) = 1 or 3, c(N 01 ) = 1 or 4. If c(N 50 ) = 3 and c(N 01 ) = 4, then c(N 00 ) = 1. Among N 50 , N 00 , N 01 , at least one has colour 1. Similarly one of N 12 , N 22 , N 23 has colour 1. So I V0 (T 2 , w 2 , c) ≥ 1 and c(N 34 ) = c(N 45 ) = 2. Consequently, no matter the colour of N 44 some vertex will have interference greater than 1. ii. We have c(N 0 ) = c(N 3 ) = 2, c(N 1 ) = c(N 4 ) = 3 and c(N 2 ) = c(N 5 ) = 4. Here we find in each of the sets {N 50 , N 00 , N 01 } ,{N 12 , N 22 , N 23 } and {N 34 , N 44 , N 45 } a vertex coloured 1. Therefore I V0 (T 2 , w 2 , c) > 1, a contradiction.

( a ) 4 .

 a4 These two neighbours are consecutive say N 0 and N 1 . The neighbours of N 3 and N 4 in Γ 2 are all coloured 1, otherwise they would have at least three neighbours with the same colour. Similarly, at least one of N 12 and N 22 is coloured 1, otherwise N 2 would have at least three neighbours also coloured 2. Then, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction.(b) These two neighbours are of the form N i and N i+2 , for some 0 ≤ i ≤ 3.W.l.o.g., let these neighbours be N 0 and N 2 . Thus, the three neighbours of N 4 in Γ 2 , N 34 , N 44 and N 45 are coloured 1 and at least one vertex of N 23 and N 33 (resp. N 55 and N 50 ) is coloured 1. Moreover, at least one vertex of N 01 , N 11 and N 12 must be coloured 1, otherwise N 1 would have three neighbours with its colour. Consequently, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction. (c) These two neighbours are of the form N i and N i+3 , for some 0 ≤ i ≤ 2. W.l.o.g., let these neighbours be N 0 and N 3 . Again, at least three vertices among N 01 , N 11 , N 12 , N 22 and N 23 and at least three other vertices among N 34 , N 44 , N 45 , N 55 and N 50 are coloured 1. Consequently, I V0 (T 2 , w 2 , c) ≥ 5, a contradiction. No vertex has two neighbours of the same colour. Suppose V 0 is coloured 1 and has only one neighbour N 0 coloured 1. Then, its other five neighbours are coloured 2 and N 2 has two neighbours of the colour 2, a contradiction.

  N 11 is coloured 2, then N 33 and N 34 are not coloured 2, otherwise I N2 (T 2 , w 2 , c) > 1 and we have a sequence of five vertices N 12 , N 22 , N 23 , N 33 and N 34 contradicting Fact 2 as four are of colour 4 (indeed, at most one is coloured 3 due to interference in colour 3 with N 3 or N 22 ). So N 11 is coloured 3 or 4. If N 1 also is coloured 3 or 4, we have a contradiction with Fact 2 applied to the five vertices N 00 , N 01 , N 11 , N 12 and N 22 , by the same previous argument. So c(N 1 ) = 1; furthermore N 4 is not coloured 1 (at most one neighbour coloured 1), nor 2 as we have seen above, nor 3, otherwise we are in the case (a). Therefore c(N 4 ) = 4 and c(N 5 ) = 3, by the same reason. But then c(N 23 ) = 4, otherwise the interference in V 0 or N 2 or N 3 is greater than 1. N 33 and N 34 can be only coloured 2, otherwise V 0 , N 3 , N 4 or N 23 will have interference strictly greater than 1, but N 33 has interference greater than 1, a contradiction. (c) Two neighbours of V 0 coloured 2 are at distance three say N 0 and N 3 . Then N 50 , N 00 and N 01 (respectively N 23 , N 33 and N 34 ) are not coloured 2, otherwise I N0 (T 2 , w 2 , c) > 1 (respectively I N3 (T 2 , w 2 , c) > 1). W.l.o.g., let N 1 be the vertex coloured 1. Among the four vertices N 12 , N 22 , N 44 and N 45 at most one is coloured 2, otherwise I N3 (T 2 , w 2 , c) > 1. So, w.l.o.g, we can suppose N 44 and N 45 are coloured 3 or 4; but we have a set of five consecutive vertices N 23 , N 33 , N 34 , N 44 , N 45 , contradicting Fact 2 (indeed at most one can be of the colour of N 4 ).

  1 and N 2 . N 34 , N 44 and N 45 are all coloured 2, otherwise N 4 would have four neighbours coloured 1 and we would be in Case 1. At most one of N 01 , N 11 and N 12 has colour 2, otherwise N 1 would have four neighbours coloured 2 and we would be again in Case 1. i. N 11 is coloured 2. Then c(N 01 ) = c(N 12 ) = 1. As already I V0 (T 2 , w 2 , c) ≥ 4, there is at most another vertex in Γ 2 coloured 1. So either the three vertices N 22 , N 23 and N 33 or the three vertices N 00 , N 50 and N 55 are all coloured 2 and then I N2 (T 2 , w 2 , c) ≥ 5 or I N5 (T 2 , w 2 , c) ≥ 5, a contradiction. ii. N 01 is coloured 2 (the case N 12 is symmetric). Then, c(N 11 ) = c(N 12 ) = 1. One of N 00 and N 50 is of colour 1 otherwise, N 0 has four neighbours of colour 2. But then I V0 (T 2 , w 2 , c) ≥ 4.5 so all the other vertices of Γ 2 are coloured 2. Therefore, I N2 (T 2 , w 2 , c) ≥ 5, a contradiction. iii. N 01 , N 11 and N 12 all have colour 1. In that case I V0 (T 2 , w 2 , c) ≥ 4.5. Therefore all the other vertices of Γ 2 are coloured 2 and I N0 (T 2 , w 2 , c) ≥ 4.5. So the other vertices at distance two of N 0 are coloured 1 and then I N01 (T 2 , w 2 , c) ≥ 5, a contradiction. (b) Among the three vertices of colour 2, only two are consecutive. W.l.o.g., let the three vertices of colour 2 be N 0 , N 1 and N 3 . At least one vertex of N 50 , N 00 , N 01 is coloured 1, otherwise N 0 has four neighbours of the same colour as it and we would be in the previous case. Similarly at least one vertex of N 01 , N 11 , N 12 is coloured 1, otherwise N 1 has four neighbours with its colour and we would be in the previous case. At least one vertex of N 23 , N 33 , N 34 is coloured 1, otherwise N 3 has three consecutive neighbours of the same colour as it and we are in the previous case. Suppose N 01 is coloured 2, then I V0 (T 2 , w 2 , c) ≥ 4.5 and exactly one of N 50 , N 00 and one of N 11 , N 12 is coloured 1 and N 45 , N 55 are coloured 2, otherwise I V0 (T 2 , w 2 , c) ≥ 5. Then I N0 (T 2 , w 2 , c) ≥ 5, a contradiction. So, c(N 01 ) = 1. If both N 50 , N 00 are coloured 2, then I N0 (T 2 , w 2 , c) ≥ 5 with three neighbours coloured 2 and at least four vertices at distance two coloured 2, namely N 3 and three vertices among N 45 , N 55 , N 11 , N 12 (at most one vertex of these could be of colour 1, otherwise I V0 (T 2 , w 2 , c) ≥ 5). So, one of N 50 , N 00 is coloured 1 and all the other vertices in {N 11 , N 12 , N 22 , N 44 , N 45 , N 55 } are coloured 2 implying that I N3 (T 2 , w 2 , c) ≥ 5, a contradiction. (c) No two vertices of colour 2 are consecutive. W.l.o.g, let these vertices be N 0 , N 2 , N 4 . The three neighbours of N 0 (resp. N 1 , N 2 ) in Γ 2 that are not neighbours of V 0 cannot be all coloured 2, otherwise we are in Case (a). So exactly one neighbour of N

http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/

http://www.gnu.org/software/glpk/

Acknowledgements

We are very pleased to thank the referees for their careful reading. All their comments and remarks have greatly improved the paper.

$ This work was partially supported by région PACA, ANR Blanc AGAPE (ANR-09-BLAN-0159) and ANR International Taiwan GRATEL (ANR-09-BLAN-0373).


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

David Coudert
email: david.coudert@inria.fr

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

Fatima Angelo

Zahra Moataz
email: fatima-zahra.moataz@inria.fr

Diverse Routing in Networks with Star SRLGs * Early stage research

Keywords: G.2.2 [Discrete Mathematics]: Graph theory-Graph algorithms, Network problems; F.2.0 [Analysis of Algorithms and Problem Complexity]: General Diverse routing, SRLG

The notion of Shared Risk Link Group, SRLG has been introduced to capture multiple correlated failures in a network. A SRLG is a set of links that fail simultaneously if a given event (risk) occurs. In such multiple failures scenario, the problem of Diverse Routing consists in finding two SRLGdisjoint paths between a pair of nodes. We consider such problem for localized failures, when all the links of a SRLG verify the star property i.e. when they are incident to the same node. We prove that in this case the problem is in general NP-complete and determine some polynomial cases.

Motivations. To ensure reliable communications, many protection schemes have been proposed. One of the most used, called dedicated path protection, consists in computing for each demand both a working and a protection path. A general requirement is that these paths have to be diversely routed, so that at least one path can survive a single failure in the network. This method works well in a single link failure scenario, as it consists in finding two edge-disjoint paths between a pair of nodes. This is a well-known problem in graph theory for which there exist efficient polynomial algorithms. However, the problem of finding two diversely routed paths between a pair of nodes becomes much more difficult in case of multiple correlated link failures that can be captured by the notion of SRLG (Shared Risk Link Group). In fact, a SRLG is a set of network links that fail simultaneously if a given event (i.e. risk) occurs. The scope of this concept is very broad. For example it can correspond to a 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 or JCB fade). It can also represent links that are located in the same seismic area, or radio links in access and backhaul networks subject to localized environmental conditions affecting signal transmission, or traffic jam propagation in road networks. In practice the failures are localized and very common SRLGs are star SRLGs or SRLGs verifying the star property [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] (coincident SRLGs in [START_REF] Doucette | Shared-risk logical span groups in span-restorable optical networks: Analysis and capacity planning model[END_REF]). Under this property, a link can be affected by more than one risk but all links of any SRLG share an endpoint. Such failure scenarios can correspond to risks arising in router nodes like card failures or to the cut of a conduit containing links issued from a node (see Figure 1). Related work. In the context of SRLG, basic network connectivity problems have been proven much more difficult to address than their usual counterparts. For instance, the problem of finding a "SRLG-shortest" st-path that is a path from node s to node t having the minimum number of risks has been proven N P -hard and hard to approximate in general (see [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]). However, the problem has been proven to be polynomial in two generic practical cases corresponding to localized failures: when all risks verify the star property [START_REF] Coudert | Shared risk resource groups and colored graph: Polynomial cases and transformation issues[END_REF] and when risks are of span 1 ; i.e. when a link is affected by at most one risk and links sharing a given risk form a connected component [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF].

l 1 l 6 l 5 l 4 l 3 l 2 l 8 l 7 l 1 l 6 l 5 l 4 l 3 l 2 l 8 l 7 s 4 s 3 s 2 s 1 v v P ort1 P ort3 P ort2
The diverse routing problem has been proven N P -complete in general (see [START_REF] Bermond | Diverse Routing with the star property[END_REF] for references) and many heuristics have been proposed. The problem has been proven to be polynomial in some specific cases of localized failures: when SRLGs have span 1 [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF], and in a specific case of SRLG's having the star property [START_REF] Datta | Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures[END_REF] (this result also follows from [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF]).

The more general case of diverse routing with the star property where there are no restrictions on the number of risks per link has been studied in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF]. The authors claim that the diverse routing problem can be solved in polynomial time. Unfortunately their algorithm is not correct; indeed we exhibit counterexamples showing that in some cases their algorithm concludes to the non existence of two SRLGdisjoint paths although two such paths exist. We have not only disproved the validity of their algorithm, but have also been able to prove that the problem is in fact NP-complete (again, contradicting the supposed polynomiality of the algorithm, unless P = N P ) and we have also determined some cases where the diverse routing problem is polynomial. Our precise results. Figure 2 shows a counter example to the algorithm in [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] that can give to the reader a flavor of the difficulty of the problem. In this figure, we have 2 specific risks r1 and r2 = r1 forming a star in v. Other risks are not represented, we can either suppose there are no other or that they are different from the risks explicitly mentioned and appear on only one link. As vertex v is a cutvertex any path should contain v. In this case, and to ensure the SRLG-disjointedness, one path should use the subpath u, v, b and the other one should use the subpath u , v, b . We have two SRLG-disjoint paths P1 = {s, a, z, w, u, v, b, t} and P2 = {s, a , w, u , v, b , t}. The algorithm of [START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF] uses the shortest path Pa = {s, a, v, b, t} and then performs a backwards phase which never finds w again. Then the algorithm stops missing the fact that there exist two SRLG-disjoint paths (for details see the full version [START_REF] Bermond | Diverse Routing with the star property[END_REF]).

To state precisely our results we use the colored-graph model [START_REF] Coudert | Shared risk resource group: Complexity and approximability issues[END_REF][START_REF] Luo | Diverse routing in WDM optical networks with shared risk link group (SRLG) failures[END_REF][START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF], also called labeled-graph model. In the colored-graph model, the network 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 an edge modeling a network link subject to different SRLGs will be assigned as many colors as SRLGs. In such a model, the star property corresponds to the fact that all the edges with the same color are incident to a common vertex and so form a star. In what follows we denote by ∆ the maximum degree, and by ∆c the maximum colored degree (the number of colors incident to a node).

As main results we show that finding 2 color-disjoint paths in a colored graph (i.e. two SRLG-disjoint paths) with the star property is N P -complete and more generally finding k ≥ 2 color-disjoint paths (for a fixed k) is also N Pcomplete. This last result holds even if ∆ is fixed with ∆ ≥ 6 + k or if the number of colors per arc is at most 2 or the maximum number of arcs having the same color is at most 2; these values correspond to real networks parameters.

On the positive side, we show that the diverse routing 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 or when the maximum degree ∆ ≤ Finally we also consider the problem of finding the maximum number of color-disjoint paths in a colored graph. This problem has been shown to be N P -hard in [START_REF] Li | Fiber span failure protection in mesh optical networks[END_REF]. We prove that it is also N P -hard in colored graphs with the star property even if the number of colors per arc is at most 3 or the maximum number of arcs having the same color is at most 2. Moreover, unless P = N P , such problem cannot be approximated within O(|V |) even if either the number of colors per arc is fixed or if the maximum number of arcs having the same color is fixed. Such inapproximability results hold also when the graph is a Directed Acyclic Graph (DAG).

These results, along with the polynomial cases, give an almost complete characterization of the problem of finding color-disjoint paths in networks with the star property.

Figure 1 :

 1 Figure 1: An example of localized risks. Link l4, for instance, shares risk s2, corresponding to Port 2 failure, with l5 and l6 and shares risk s4, corresponding to the conduit cut, with links l2 and l3.

r 2 r 2 Figure 2 :

 22 Figure 2: Example

4 .

 4 The algorithm for DAGs requires O((|V |∆) 2k ) time where k is the number of color-disjoint paths. The algorithm for fixed |R| and the one for ∆ ≤ 4 require O(|V | + |E|) time.