B Kouakou
email: kouakou@univ-paris1.fr

On-line algorithm for the minimal b-clique cover problem in interval graphs

Keywords: on-line algorithm, clique cover problem, interval graphs, competitive ratio

In this paper we study the on-line b-clique cover problem in interval graphs. In our model the n vertices of the final instance-graph are revealed one-by-one, and we want to find a clique cover with the additional requirement that every clique cannot contain more than b vertices, where b is an integer. We first give a result which can be seen as a reduction of the on-line b-clique cover problem into the on-line clique cover problem. Then, we derive hardness results showing limits of every algorithm solving the on-line b-clique cover problem.

Introduction

In on-line computation, an algorithm has to solve a combinatorial optimization problem with the constraint that the instance is not a priori completely known before the resolution begins. In other words, the data-set is revealed step-by-step and one has, at the end of each step, to irrevocably decide on the final solution dealing with this step. Each decision must be made based of past data without information about the future. An on-line problem is defined by: a combinatorial optimization problem; a set of rules R describing how the final instance will be revealed; a set of rules R defining what kind of decisions are allowed.

In this paper, we deal with the on-line minimal b-clique cover problem for interval graphs. A clique cover of a graph G = (V, E) is a collection of cliques W 1 , • • • , W r , such that r i=1 W i = V . A clique cover of the smallest cardinality, r, is called a minimal clique cover; and in this case r is denoted by k(G). The problem of finding, in a graph G, a clique cover of smallest cardinality r is called the minimal clique cover problem, CC. A specific case of this problem consists of minimizing the number of cliques in the cover, under the restriction that every clique must not have more than b nodes, where b is a given integer. This problem is called the b-clique cover problem and denoted by b-CC. Throughout this study, graphs under consideration are interval graphs. Golumbic [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] defined this class of graphs as follows: let F be a family of nonempty sets. The intersection graph of F is obtained by representing each set in F by a vertex and connecting two vertices of F by an edge if and only if their corresponding sets intersect. The intersection graph of a family of intervals on a linear ordered set (like the real line) is called an interval graph. The class of interval graphs have been intensively studied, in particular because of their practical applications (e.g., in memory allocation and in organizing records in databases [START_REF] Booth | Testing for consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms[END_REF]). Let us consider the following application [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] of interval graphs.

Application [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF] Suppose that c 1 , c 2 , • • • , c n are chemical compounds which must be refrigerated under closely monitored conditions. If compound c i must be kept at a constant temperature between t i and t i degrees, how many refrigerators will be needed to store all the compounds? Let G be an interval graph with vertices c 1 , c 2 , • • • , c n and connect two vertices whenever the temperature intervals of their corresponding compounds intersect.

If c i1 , c i2 , • • • , c i k is a clique of G, then the intervals [t ij , t ij ] corresponding to each compound c ij , j = 1, 2, • • • ,
k}, will have a common point of intersection, say t. A refrigerator set at a temperature of t will be suitable for storing all of them. An optimal storing will be found by solving the minimal clique cover problem. If each refrigerator cannot contain more than b compounds, then we have to solve the minimal b-clique cover problem. Moreover, if these compounds are produced by a manufacturer along the year and one has to regularly (say as soon as compounds are produced) store them in refrigerators, we obtain the on-line version of the minimal b-clique cover problem. The off-line version of the minimal clique cover is solved in polynomial time for chordal graphs [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Gavril | Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph[END_REF], consequently for interval graphs. This same problem is also solved in polynomial time for circular arc graphs (given their representations as families of arcs) [START_REF] Gavril | Algorithms on circular-arc graphs[END_REF], for comparability graphs [START_REF] Golumbic | The complexity of comparability graph recognition and coloring[END_REF] and for the more general class of "perfect graphs", [START_REF] Grotschel | Polynomial algorithms for perfect graphs[END_REF]. Whereas it is N P -hard for general graphs, see [START_REF] Garey | Computers and intractability. a guide to the theory of N Pcompleteness[END_REF].

For the off-line b-clique cover problem, we have the following results:

1. If b = 2, the problem reduces to finding a maximum cardinality matching in the graph G = (V, E). Jack Edmond [START_REF] Edmonds | Paths, trees, and flowers[END_REF] derives an efficient algorithms which is based on augmenting paths for constructing matchings. Given a (partial) matching M in a graph G, an augmenting path P is a path of edges where every odd-numbered edge (including the first and last edge) is not in M, while every even-numbered edge is.

k b (G) = min B∈B(G,b) |B| .
In this paper, we study an on-line model of the minimum b-clique cover problem. We denote it by b-LCC. Section 1 is devoted to generalities on competitive analysis and also presents our on-line model. In section 2 we derive a competitive ratio for the n-steps version of b-LCC where intervals are presented one-by-one. Finally, section 3 brings to the fore an hardness result showing limits of every algorithm which solves b-LCC.

On-line models and competitive analysis

We denote by LCC the on-line version of the minimal clique cover problem and recall that b-LCC denotes the on-line minimal b-clique cover problem. b-LCC can be defined by the quadruplet (b-CC, R, R ) where R and R describe how the final instance is revealed and how the solution is constructed. Given a problem, we can pass from an on-line version to another by changing only the rules R and R . For b-LCC we consider the following model: R: the interval graph G = (V, E) is revealed in n steps, where n = card(V ). At each step, a vertex (an interval) of G is revealed together with the edges linking this vertex and already revealed vertices. Consequently, all the vertices revealed from the first step to a step i form the graph G[V i ],

i.e., the subgraph induced by

v 1 • • • , v i .
R : at each step, one irrevocably decides whether the new vertex is introduced in the solution.

The quality of an on-line algorithm is expressed by the competitive ratio defined below.

Definition 1. Let us consider a minimization on-line problem P , an instance σ of P and an algorithm LA for P . Furthermore, we consider a function c LA (n) (n denotes the order of the instance). Let LA(σ) denote the value of the solution of P computed by the algorithm LA and σ the solution returned by an optimal algorithm knowing beforehand the final instance. The algorithm LA is said to guarantee the competitive ratio c A (n) if, for any instance σ of P :

c LA (n) × LA(σ) ≤ σ (c LA (n) × σ ≤ LA(σ) for a maximization problem).
The minimum clique cover problem is related to the graph-coloring problem which consists of assigning the fewest possible colors to the vertices of a graph so that adjacent vertices receive different colors. Here, we will use the same notations as in [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]: χ(G) denotes the chromatic number of G: the fewest number of colors needed to properly color vertices of G, or equivalently, the fewest number of independent sets needed to cover the vertices of G. α(G) is the stability number of G: the size of the largest stable set of G. k(G), denotes the clique cover number : the fewest number of complete subgraphs (cliques) needed to cover the vertices of G. w(G) is the clique number of G: the size of the largest clique of G. For all graph (so for interval graphs), we have k(G) = χ( Ḡ) and α(G) = w( Ḡ), where Ḡ is the graph complement of G . There is a number of strong results related to on-line coloring algorithms for interval graphs; see e.g. [START_REF] Kierstead | Recursive and on-line graph coloring[END_REF][START_REF] Kierstead | Coloring interval graphs with First Fit[END_REF][START_REF] Slasurek | A coloring algorithm for interval graphs[END_REF][START_REF] Slasurek | Optimal on-line coloring of circular arc graphs[END_REF]. For the on-line coloring of general graphs, the interested reader can see [START_REF] Halldórsson | Online coloring known graphs[END_REF][START_REF] Halldórsson | Lower bounds for on-line graph coloring[END_REF]. One can also see [START_REF] Hansen | Bounded vertex colorings of graphs[END_REF] for bounded coloring. Since the complements of interval graphs are not in general interval graphs, the relation k(G) = χ( Ḡ) does not help to solve the minimal clique cover problem via coloring. In [START_REF] Gyarfas | A First Fit on-line coloring[END_REF], Gyarfas and Lehel derives an absolute competitive ratio for the on-line minimal clique cover problem, LCC, on chordal graphs. They proved that if G is a chordal graph then, the value k F F (G) of the solution returned by the First Fit algorithm satisfies

k F F (G) ≤ 2α(G) -1.
Let us now focus our attention on the on-line b-clique cover problem. In this section, we consider the on-line clique cover problem where for every interval graph G = (V, E), its n vertices are revealed one-by-one (Such instance will be called an n-steps instance). The on-line algorithm has to irrevocably assign a clique to each vertex as soon as it is revealed.

To

λ b (G) ≤ χ b (G) + λ(G) ≤ χ b (G) + 1 C LA k(G), (2)
where the last inequality of expression (2) holds since LA is C LA -competitif. Let us also note that, for a given instance graph G, every solution of b-LLC is a feasible solution of LLC. Therefore, as they are minimization problems, we have k(G) ≤ χ b (G). Relation (2) becomes:

λ b (G) ≤ χ b (G) + 1 C LA χ b (G) i.e λ b (G) ≤ (1 + 1 C LA )χ b (G)
Corollary 1. b-LCC admits an asymptotic 1 3 -competitive algorithm for chordal graphs, so for interval graphs.

Proof. In what follows a clique C i is compatible with an interval I j if all intervals in C i intersect I j . The classical First Fit (F F ) algorithm used to solve the Bin-Packing problem [START_REF] Johnson | Fast algorithms for bin packing[END_REF][START_REF] Johnson | Near-optimal bin packing algorithms[END_REF] can be adapted to the minimum clique cover problem as follows: FF : Start with no clique and insert interval I j (j = 1, • • • , n) in the clique which has the lowest index i and is compatible with I j . If no such a clique exists, then open a new clique to pack I j . In [START_REF] Gyarfas | A First Fit on-line coloring[END_REF], Gyarfas and Lehel proved that F F is 1/2-competitive for LCC on chordal graphs. Then applying Theorem (1), the result of corollary 1 immediately follows.

For the sequel, we need to recall the following definition used in [START_REF] Finke | Batch processing with interval graph compatibilities between tasks[END_REF].

Definition 2. Let us denote by G k the on-line graph induced by the first k elements {v

i , • • • , v k } of V . Assume that C is a clique that is already in use after processing G k . The range r k [C] of C at phase k is defined as follows: r k [C] = {v j : 1 ≤ j ≤ k, A(v j ) = C}, i.e., r k [C]
is the intersection of all the intervals (vertices) put in the clique C after revealing the first k vertices of G.

3 Hardness result for the on-line minimum b-clique cover in interval graphs.

We consider an interval graph G = (V, E) of which the n vertices will be revealed (one-by-one) as we progress with the resolution. One can think of an on-line problem as a game between two players. One player, the adversary, generates requests on-line according to some specified mechanism and is charged a cost for its selections according to some specified rules. For example, for a minimization problem, the adversary is charged the minimum (off-line) cost to perform any request sequence it generates. The other player is the algorithm, which responds to requests by making a decision, and incurs some total cost over the course of the game. In our model, the adversary has complete knowledge of the algorithm and it can first decide how many requests it wants to generate; then, it internally simulates the algorithm on each possible sequence of that length to find the sequence that maximizes the ratio between the on-line algorithm's cost and the adversary's cost. We emphasize that, as we deal with a minimization problem, the adversary's goal is to maximize the ratio of the algorithm's cost to the adversary's cost, while the on-line algorithm's goal is to minimize it. We have the following result. Case 1: algorithm b-LA is greedy: at a step j of the on-line process, b-LA does never construct a new clique for a revealed interval I j if I j can be put in an existing clique C i , with i ≤ j; for example algorithm First Fit is greedy. In this case the adversary adopt the following strategy: 1. The adversary first reveals one-by-one a sequence of N = 2k intervals as follows (each interval The figure 1 illustrates a solution returned by a non-greedy algorithm b-LA. When no ambiguity occurs, an interval I j will also be identified to its index j. In figure 1

(i) For i = 1, 2, • • • , 2k -1, interval I i is linked to I i+1 , but for i = 1, 2, • • • , k -1, intervals I 2i-
I i , i = 1, • • • , 2k will be denoted by [a i , b i ]): (i) for i = 1, 2, • • • , k, interval I 2i-1 is linked to I 2i , but, for i = 1, 2, • • • , k -1, I 2i is linked to I 2i+1 if

Conclusion

This work points out two results related to the on-line b-cliques cover problem on interval graphs: we first proved that the on-line clique cover problem, LCC, reduces to its bounded version called b-LCC, where each clique is of size at most b. This reduction leads us to a 1/3-competitive algorithm for b-LCC on chordal graphs. Then, we derive a hardness result for b-LCC on intervals graphs: we show that if the vertices of an interval graph are revealed one-by-one, then the b-LCC problem cannot be solved strictly better than 1/2-competitively. It seems appropriate to analyze the competitive behavior of an on-line algorithm which adheres to the First Fit principle. Such an algorithm puts, at each step j, the revealed interval in the unsaturated clique which has the lowest index i and is compatible with I j . If no such a clique exists, then a new clique is opened to pack I j . The model of b-LCC where intervals are revealed by cluster seems also to be an interest research area that one can explore.

1 .

 1 If b = 2, this problem is equivalent to the on-line maximum-cardinality matching problem which is solved by a 1/2-competitive algorithm. Let us now consider the on-line version of the b-clique cover problem, with b ∈ {3, • • • , n}. 2 The n-steps on-line minimal b-clique cover problem, (b-LCC)

Theorem 1 . 1 )

 11 our knowledge, it is the first time that one considers this on-line problem. In what follows, a clique C i containing exactly b nodes (or intervals) is said to be saturated, i.e |C i | = b; in the opposite case, |C i | < b, and C i is unsaturated. We first prove that b-LCC reduces to LCC. Indeed, if LA is an algorithm for LCC, then one can transform every clique C i returned by LA into Ci b saturated cliques and probably one unsaturated clique. With such away every solution of LCC can be transformed into a solution of b-LCC. The question is how to exploit the competitive ratio guaranteed by an algorithm for LCC to derive results for (b-LCC)? Let us consider an algorithm LA solving LCC. We propose below an algorithm called b-LA which solves b-LCC. Algorithm b-LA: use LA to solve the graph-instance I. Let LA(I) = C 1 , C 2 , • • • , C λ be the solution returned by LA. Then, we form a solution for b-LCC by clustering each clique C i into Ci b saturated cliques and possibly one unsaturate clique. The following theorem holds. If an on-line algorithm LA guarantees the competitive ratio C LA for the minimum clique cover problem, then its corresponding algorithm b-LA, for b-LCC, guarantees the competitive ratio C LA 1+C LA . Proof. Let us consider Algorithm b-LA solving b-LCC. Let N s be the number of saturated cliques returned by b-LA and N u the number of unsaturated cliques. Then, the total number λ b (G) of cliques returned by b-LA satisfies: λ b (G) = N s + N u (Let denote by χ b (G) (resp. λ(G)) the optimal value for the b-clique cover problem (resp. the number of cliques returned by LA for LLC). χ b (G) can also be defined as the b-bounded cochromatic number. Then, we have N u ≤ λ(G) and N s ≤ χ b (G). Moreover, relation (1) implies (recall that k(G) denotes the minimal clique number of G):

Theorem 2 .

 2 No on-line algorithm for b-LCC can guarantee a competitive ratio c LA > 1/2 on interval graphs. Proof. Let b-LA be an on-line algorithm for b-LCC. Let us consider an interval graph G of which vertices (or intervals) are revealed one-by-one. The adversary first reveals, one-by-one, a sequence of N = 2k intervals (or nodes). Two main situations may occur:

2 .

 2 [START_REF] Booth | Testing for consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms[END_REF] and I 2i+1 are not connected. Moreover, for i = 2, • • • , k, intervals I 2i-2 and I 2i do not also intersect. Clearly, this first sequence of 2k intervals form a path. (ii) Let denote byE 1 , E 2 , • • • E k the set of k edges (k ≥ 1) selected by the greedy algorithm, E i = (I 2i-1 , I 2i ), i = 1, • • • , k. Then,the adversary reveals one-by-one a number of M = (b -2)(k + 1) + 2 intervals such that: b -1 intervals form a clique C 0 with I 1 and no interval of C 0 different from I 1 is connected to another interval which is out of C 0 . For each i ∈ {1, 2 • • • , k -1}, b -2 intervals form a clique C i with both intervals I 2i and I 2i+1 . Moreover these b -2 intervals do not intersect another interval out of the clique C i . The last b -1 intervals form a clique C k+1 with I 2k and no interval of C k+1 different from I 2k is connected to an interval out of C k+1 .Case Algorithm b-LA does not adhere to the greedy principle. In this case:

2 .

 2 and only if algorithm b-LA has selected I 2i-1 and I 2i in the same clique.(ii) If at some moment the algorithm puts I 2i-1 and I 2i in a same clique, then the next two intervals, I 2i+1 and I 2i+2 , to be revealed are such that a 2i < a 2i+1 ≤ b 2i < b 2i+1 and b 2i < a 2i+2 ≤ b 2i+1 < b 2i+2 . In this case and only for this first sequence of N intervals, every interval I j , j > 2i, to be revealed has to satisfy b 2i-1 < a j . (iii) For i = 1, 2, • • • , k, if at some moment, Algorithm b-LA does not select both intervals I 2i-1 and I 2i in a same clique, then the remaining intervals, {I j , j = 2i + 1, • • • , 2k}, to be revealed in this first sequence are such that b j < a 2i-1 . We emphasize that if I 2i-1 and I 2i are put in two different cliques, and if before I 2i-1 and I 2i the algorithm has put intervals I 2t-1 and I 2t , (t < i) in the same clique, then every interval I j , j > 2t, to be revealed in this first sequence of N intervals satisfies b 2t-1 < a j . If after revealing this sequence of N intervals, no edge is selected by the algorithm, then the game stops. In the opposite case, let denote by E 1 , E 2 , • • • E p the set of P edges selected by b-LA. Then, the adversary reveals one-by-one a number of M = (b -2)(p + 1) + 2 intervals (see bold intervals in Figure1) such that: b -1 intervals form a clique C 0 with the initial endpoint I i,1 of E 1 and these b -1 intervals have no link with the others intervals different from I i,1 in the final graph-instance. For j ∈ {1, 2 • • • , p -1}, b -2 intervals form a clique with the terminal endpoint, I t,j , of E j and the initial endpoint, I i,j+1 , of E j+1 . Moreover, except these two endpoints, the b -2 intervals have no connexion with the others intervals of the final graph G. The last b -1 intervals form a clique with the terminal endpoint of E p and they are not linked to another interval of G.

  , intervals {1, 2, • • • , 12} constitute the first sequence of revealed intervals (they are revealed one-by-one). Let us consider that b-LA first forms cliques {1, 2} and {3, 4}. So, the initial endpoints of intervals {I j , j = 5, • • • , 12} are greater than the terminal endpoint of I 3 . Now let us assume that b-LA puts intervals 5 and 6 in two different cliques. In this case, all intervals {I j , j = 7, • • • , 12} to be revealed are such that their terminal endpoint are lower than the initial endpoint of interval 5. Algorithm b-LA also puts 7 and 8 in two different cliques. That justifies the position of intervals {9, • • • , 12} in figure1. Finally, for this first sequence of 12 intervals, we consider that b-LA forms cliques {9, 10} and {11, 12}. After these 12 intervals, the adversary reveals one-by-one the second sequence of intervals, i.e., {13, 14, • • • , 19} (they are represented into bold font in figure1).

Fig. 1 . 1 =

 11 Fig. 1. An interval-representation of the final instance, with b = 3

  The best algorithm known for general matching runs in O( |V ||E|) [19]. 2. For b ∈ {3, • • • , n}, this problem is N P -Hard for general graphs [2]. On the other hand, Finke et al. solved in [7] the minimum b-clique cover (b-CC) in polynomial time for interval graphs. Using notations of [7], we recall that a b-clique in a graph G is a clique Q of G with size |Q| ≤ b. A b-clique cover of the graph G = (V, E) is a family B of b-cliques that cover V . Its size is |B| . Let B(G, b) denote the set of all b-cliques covers of G, the optimum objective value of the problem (b-CC) is: