domain: info math

text:
Flavia Bonomo
email: fbonomo@dc.uba.ar

Guillermo Duran
email: gduran@dm.uba.ar

Mario Valencia
email: valencia@lipn.univ-paris13.fr

Mario Valencia-Pabon

Complexity of the cluster deletion problem on subclasses of chordal graphs and cographs *

Keywords: Block graphs, Cliques, Edge-deletion, Cluster deletion, Interval graphs, Split graphs, Submodular functions, Chordal graphs, Cographs, NP-completeness

published or not. The documents may come

Complexity of the cluster deletion problem on some subclasses of chordal graphs

Introduction

Clustering is an important task in process of data analysis which can be viewed as a data modeling technique that provides an attractive mechanism to automatically find the hidden structure of large data sets. The input to the problem is typically a set of elements and pairwise similarity values between elements. The goal is to partition the elements into subsets, which are called clusters, so that two meta-criteria are satisfied: Homogeneity-elements inside a cluster are highly similar to each other; and separation-elements from different clusters have low similarity to each other. In the graph theoretic approach to clustering, one builds from the raw data a similarity graph whose vertices corresponds to elements and there is an edge between two vertices if and only if the similarity of their corresponding elements exceeds a predefined threshold [START_REF] Hansen | Cluster analysis and mathematical programming[END_REF][START_REF] Hartigan | Clustering algorithms[END_REF]. Cluster graphs have been used in a variety of applications whenever clustering of objects is studied or when consistent data is sought among noisy or error-prone data [START_REF] Bansal | Correlation clustering[END_REF][START_REF] Charikar | Clustering with qualitative information[END_REF]. Ideally, the resulting graph would be a cluster graph, that is, a graph in which every connected component is a clique (i.e. a complete subgraph). In practice, it is only close to being such, since similarity data is experimental and thus, error-prone.

The cluster deletion problem asks for the minimum number of edges that can be removed from an input graph to make the resulting graph a cluster graph. There exist several results for the cluster deletion problem (see for example [START_REF] Böcker | Even faster parametrized cluster deletion and cluster editing[END_REF][START_REF] Shamir | Cluster graph modification problems[END_REF][START_REF] Komusiewicz | Cluster editing with locally bounded modifications[END_REF] and references therein). The cluster deletion problem is known to be NP-complete [START_REF] Shamir | Cluster graph modification problems[END_REF] for general graphs. Moreover, Shamir et al. [START_REF] Shamir | Cluster graph modification problems[END_REF] showed that it remains NP-hard when enforcing that the input graph should be clustered into exactly d ≥ 3 components. They also showed that when the input graph should be clustered into exactly 2 components, the problem is polynomial-time solvable. Komusiewicz et al. [START_REF] Komusiewicz | Cluster editing with locally bounded modifications[END_REF] proved that cluster deletion is hard for C 4 -free graphs with maximum degree 4, and they gave a O(n 1.5 log 2 n) time algorithm for solving cluster deletion on graphs with maximum degree 3. Based on results obtained by Demaine et al. [START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF] concerning a variant of a clustering problem, Dessmark et al. [START_REF] Dessmark | On the approximability of maximum and minimum edge clique partitions problems[END_REF] provided a polynomial O(log n)-approximation algorithm for the edge-weighted version of the cluster deletion problem. They also showed that for the edge-unweighted version of cluster deletion on general graphs, the greedy algorithm that finds iteratively maximum cliques gives a 2-approximation algorithm to the optimal cluster deletion. The complexity of such an algorithm relies on the complexity of iteratively finding maximum cliques, so it is a polynomial-time approximation algorithm for certain graph classes. Recently, Gao et al. [START_REF] Gao | The cluster deletion problem for cographs[END_REF] showed that the greedy algorithm that finds iteratively maximum cliques, gives an optimal solution for the class of graphs known as cographs. It implies that the cluster deletion problem is polynomial-time solvable on unweighted cographs. Moreover, Gao et al. [START_REF] Gao | The cluster deletion problem for cographs[END_REF] showed that the cluster deletion problem is NP-hard on (C 5 , P 5 )-free graphs, on (2K 2 , 3K 1 )-free graphs and on (C 5 , P 5 , bull, 4-pan, fork, co-gem, co-4-pan)-free graphs. For weighted graphs, the cluster deletion problem can be solved in polynomial time on the class of triangle-free graphs, since it is equivalent to maximum weighted matching [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF]. The cluster deletion problem has been studied extensively in the scope of fixed-parameter tractability (FPT). Many of the recently-developed FPT algorithms rely on being able to solve cluster deletion in polynomialtime on restricted graph structures [START_REF] Böcker | Even faster parametrized cluster deletion and cluster editing[END_REF].

This paper is organized as follows. In Section 2, we prove that the weighted cluster deletion problem is NP-complete in a subclass of split graphs and even under certain restrictions for the weights, and that it is polynomial-time solvable for unweighted split graphs. In Section 3, we prove that the unweighted cluster deletion problem is NP-complete in a subclass of chordal graphs, namely P 5 -free chordal graphs. In Section 4, we prove that the weighted cluster deletion problem is polynomial-time solvable on block graphs, when the weights are nonnegative. In Section 5, we show that the weighted cluster deletion problem is NP-complete on interval graphs and, moreover, on complete split graphs. On the positive side, we show that the unweighted problem is polynomial-time solvable for proper interval graphs, and that the weighted cluster deletion problem is polynomial-time solvable on a subclass of proper interval graphs known as paths of cliques. As a corollary of the complexity on complete split graphs, it is shown that the weighted cluster deletion problem is NP-complete on cographs, in contrast to the polynomial-time algorithm given in [START_REF] Gao | The cluster deletion problem for cographs[END_REF] for the unweighted case.

We conclude this introduction with some definitions. Let G = (V, E) be a graph. For each vertex v ∈ V , we denote by N (v) = {u : vu ∈ E} the set of neighbors of v in G. Two vertices v and w are called true twins if N (v) ∪ {v} = N (w) ∪ {w}. A graph G is called weighted if there is a weight function w : E → R + associated with it. For the algorithms involving weighted graphs, we will assume that the weights are rational (or belong to any ordered field in which we can perform the operations algorithmically). An unweighted graph is a graph in which each edge has a weight equal to 1. A graph is chordal, if and only if it does not contain a cycle of length at least four as an induced subgraph. Given a vertex partition S = C 1 , . . . , C k of a graph G, we call the weight of S to the sum of the weight of all edges e = uv such that u ∈ C i , v ∈ C j , with i = j. The cluster deletion problem of a (un)weighted graph G can be redefined as the problem of finding a clique partition of G with minimum weight.

Split graphs

A graph G = (V, E) is a split graph, if and only if there is a partition of the vertices V of G into a clique K and an independent set I. Another necessary and sufficient condition for a graph G to be a split graph is that G and its complement G are chordal graphs (see [START_REF] Földes | Split graphs[END_REF]).

In this section we prove the NP-completeness of the weighted cluster deletion problem for split graphs by reduction from the exact cover by 3-sets problem (X3C problem for short). The formal definition of the X3C problem can be stated as follows:

Instance: A set X with 3q elements and a collection C of 3-element subsets of X.

Question: Does C contain an exact cover for X? In other words, is there a subset C ⊆ C, such that every element of X occurs in exactly one member of C ?

The X3C problem is known to be NP-complete [START_REF] Garey | Computers and Intractability[END_REF].

We analyze in this section a subclass of the split graphs, namely the class of those split graphs where each vertex of the independent set I is adjacent to exactly p vertices of the clique K. We call these graphs the p-split graphs, where p ≥ 1.

Theorem 1 (NP-completeness on weighted 3-split graphs). The cluster deletion problem is NPcomplete for weighted 3-split graphs, even if the weight of all the internal edges of the clique is 1 and the weight of the edges between the clique and the stable set is uniform.

Proof. It is not hard to see that the cluster deletion problem is in NP, since we can easily verify in polynomial time whether a vertex partition of a graph is a clique partition or not, and if it has weight less that a given value k. Let X = {x 1 , . . . , x 3q } and C = {c 1 , . . . , c m } be an instance of the X3C problem, where each element c i ∈ C is a 3-element subset of X, with m ≥ q ≥ 1. We want to know if there exists a subset C ⊆ C with size q such that each element in X belongs to exactly one of the elements in C . We will construct an edge-weighted split graph G = (K X ∪ I C , E), where K X induces a clique with 3q vertices and I C induces an independent set with m vertices. In fact, for each element x i ∈ X there is a vertex v x i in K X and for each 3-subset c j ∈ C there is a vertex v c j ∈ I C . The edge set E is formed as follows:

E = E X ∪ E C , where E X = {v x i v x j : i = j, v x i , v x j ∈ K X } and E C = {v c j v x j 1 , v c j v x j 2 , v c j v x j 3 : v c j ∈ I C , v x j 1 , v x j 2 , v x j 3 ∈ K X , c j ∈ C and c j = {x j 1 , x j 2 , x j 3 }}.
Finally, the weight of each edge in E X is equal to 1 and the weight of each edge in E C is equal to β, where β = 3q. Clearly, G is an split graph and its construction is done in polynomial time. Let W = 3q 2 -3q + 3(m -q)β. We will show that there exists a subset C ⊆ C, with |C | = q, exactly covering X if and only if G has a clique partition where the sum of the weights of edges outside the cliques is at most W . In other words, there exists a solution for the X3C problem if and only if there exists an optimal solution for the cluster deletion problem for G with weight at most W .

Assume first that there exists C ⊆ C, with C = {c 1 , . . . , c q } such that c i ∩ c j = ∅ whenever i = j, and c j ∈C c j = X. The clique partition for G can be constructed as follows: for each c j ∈ C , with c j = {x j 1 , x j 2 , x j 3 }, choose the clique {v c j , v x j 1 , v x j 2 , v x j 3 } in G. Each one of the remaining m -q vertices in I C form a clique with size one. It is easy to see that the sum of the edge weights outside those cliques is exactly equal to W .

Conversely, assume that G has a clique partition with weight at most W . We should to prove that there exists C ⊆ C, with |C | = q, such that C is an exact cover for X. For this, we analyze first the structure of the optimal solutions of the cluster deletion problem for G.

Claim 1. Let S be a clique partition of G which is an optimal solution for the cluster deletion problem in G. If there exists a clique in S formed only by vertices in K X then, there is no solution to the X3C problem.

First, notice that it is not possible to have two cliques, say A 1 , A 2 ∈ S, formed only by vertices in

K X . Otherwise, set S = S \ {A 1 , A 2 } ∪ {A 1 ∪ A 2 }. Clearly, the weight of S is |A 1 |.|A 2 | ≥ 1
less than the weight of S, which is a contradiction to the optimally of S. On the other hand, every clique of S contains at most one vertex of I, so there are m cliques (possibly singletons) containing one vertex of I each. Let S = A 1 , B 1 , . . . , B m be the clique partition of G and let W S be the weight of S. Assume that the clique A 1 is formed only by vertices in K X . Clearly, each clique B j , 1 ≤ j ≤ m, contains a vertex in I C and zero, one, two or three vertices in K X . We consider the following cases:

• Suppose there exists B j = {v c j , v x j 1 , v x j 2 } in S such that there is v y ∈ A 1 with v y be adjacent to v c j , where v c j ∈ I C and v y , v x j 1 , v x j 2 ∈ K X . Let S be the clique partition obtained by setting B j ← B j ∪{v y } and

A 1 ← A 1 \{v y }, where S = S\{A 1 , B j }∪{A 1 , B j }. Let W S be the weight of S . It is not difficult to see that W S = W S -(β + 2) + (|A 1 | -1) = W S + |A 1 | -β -3.
However, β = 3q and |A 1 | ≤ 3q -2. Therefore, W S < W S , which contradicts the optimality of S.

• Similarly to the previous case, suppose there exists

B j = {v c j , v x j 1 } (resp. B j = {v c j }) in S such that there is v y ∈ A 1 with v y be adjacent to v c j , where v c j ∈ I C and v y , v x j 1 ∈ K X (resp. v y ∈ K X ) . By setting B j ← B j ∪ {v y } and A 1 ← A 1 \ {v y }, we obtain a new clique partition S = S \ {A 1 , B j } ∪ {A 1 , B j } which weight W S = W S + |A 1 | -β -2 < W S (resp. W S = W S + |A 1 | -β -1 < W S )
, which is a contradiction to the optimality of S.

As S is an optimal solution, no vertex in I C is adjacent to any vertex in A 1 , but by construction, it implies that X is not covered by C, and thus, there is no solution for the X3C problem. This ends the proof of this claim. ♦ By the previous claim, if c j ∈C c j = X then, an optimal solution S for the cluster deletion problem of G must be of the form B 1 , . . . , B m , where each clique B j contains exactly one vertex v c j ∈ I C , for 1 ≤ j ≤ m. Now, we can deduce the following result on S.

Claim 2. Let S = B 1 , . . . , B m be an optimal solution of the cluster deletion problem for G. Let m = t 1 + t 2 + t 3 + t 4 , with t i ≥ 0, for 1 ≤ i ≤ 4, where t 1 (resp. t 2 , t 3 , t 4 ) represents the number of cliques B j in S formed by a vertex in I C and by three (resp. two, one, zero) vertices in K X . Then, (i)

t 1 > 0; (ii) Let v c j be a vertex in I C such that it belongs to a clique B j of S with |B j | = k, with 1 < k ≤ 3. Then, for each vertex x ∈ N (v c j ) such that x ∈ B j , we have that x must belong to another clique B i of S with |B i | > k. Suppose that t 1 = 0. If t 2 = 0 then, there is a clique B j = {v c j , v x j 1 , v x j 2 } in S. By construction, v c j has another neighbor v y ∈ K X . If v y ∈ B i , with |B i | = 3 (resp. |B i | = 2) then, we can construct another clique partition S by setting B j ← B j ∪ {v y } and B i ← B i \ {v y } and where S = (S \ {B i , B j })∪{B j ∪B i }. Notice that the weight W S of S is equal to W S -(β+2)+β+1 = W S -1 < W S (resp. W S -(β + 2) + β = W S -2 < W S ) which contradicts the optimality of S. If t 1 = t 2 = 0 then, there are B j , B i , B s ∈ S such that B j = {v c j , v x j }, B i = {v c i , v x i } and B s = {v cs , v xs } where {v x j , v x i , v xs } are the three neighbors of v c j . By setting B j ← B j ∪ {v x i , v x j }, B i ← B i \ {v x i }, B s ← B s \{v xs }, and by constructing the partition S = S \{B j , B i , B s }∪{B j , B i , B s } we have that the weight W S of S is equal to W S -(2β + 3) + 2β = W S -3 < W S ,
which is again a contradiction to the optimality of S. Therefore, t 1 > 0 and thus (i) holds. In an analogous way, we can show (ii), which ends the proof of this claim. ♦ Now, let S = B 1 , . . . , B m be an optimal clique partition of G with weight W S . By Claim 1 we know that each clique B i in S contains exactly one vertex in I C and that there are t 1 (res. t 2 , t 3 , t 4 ) cliques in S having exactly three (resp. two, one, zero) vertices in K X . By Claim 2, we know that t 1 > 0 and t 2 , t 3 , t 4 ≥ 0. Therefore, the weight W S of S can be written as:

W S = 3q 2 -(3t 1 + t 2 ) + (t 2 + 2t 3 + 3t 4 )β. Moreover, m = t 1 + t 2 + t 3 + t 4 and 3q = 3t 1 + 2t 2 + t 3 . It is not difficult to see that 3(m -q) = t 2 + 2t 3 + 3t 4 and that 3t 1 + t 2 = 3q -t 2 -t3 which implies that 3q ≥ 3t 1 + t 2 . Therefore, W ≤ W S with equality only if t 2 = t 3 = 0 in which case, t 1 = q.
Therefore, if S has weight W then, there is a solution to the X3C problem which ends the proof of this theorem.

For the unweighted case, we will show next that the problem can be easily solved on split graphs.

Theorem 2 (Polynomiality on unweighted split graphs). The cluster deletion problem is polynomial-time solvable for unweighted split graphs. Indeed, if (K, I) is a split partition of the graph G such that K is a maximal clique of G, then {K} ∪ {{v} : v ∈ I} is an optimal solution unless there is a vertex v 1 in I adjacent to all but one vertex w in K, and that vertex w has a neighbor v 2 in I. In that case, an optimal solution is {{v

1 } ∪ (K -{w}), {w, v 2 }} ∪ {{v} : v ∈ I, v = v 1 , v 2 }.
Proof. Let G be a split graph and let (K, I) be a split partition of G such that K is a maximal clique of G. We can see the problem as the problem of maximizing the internal edges in a clique partition S (it is equivalent to the problem of minimizing the edges joining distinct cliques of S). In order to break ties, we will maximize the internal edges that join two vertices of K in G. We will call the standard partition to S 0 = {K} ∪ {{v} : v ∈ I}.

Suppose that we have an optimal solution S with respect to the criterion that is strictly better than S 0 . If S contains a clique A K such that |A| = a ≥ 1 and a clique B containing one vertex of I and b ≥ 1 vertices of K, then S = S \ {A, B} ∪ {A ∪ (B ∩ K), B ∩ I}, with respect to S, has ab new internal edges that join two vertices of K in G and looses b edges that join vertices of K with vertices of I, so it is either strictly better than S or it is preferable by the breaking ties criterion, a contradiction to the optimality of S. So, we may assume that every clique of S contains a vertex of I.

Suppose now that the clique A has a vertex of I and a ≥ 2 vertices of K, and the clique B has a vertex of I and b ≥ 2 vertices of K. Then S = S \ {A, B} ∪ {(A ∩ K) ∪ (B ∩ K), A ∩ I, B ∩ I}, with respect to S, has ab new internal edges that join two vertices of K in G and looses a + b edges that join vertices of K with vertices of I, so as a and b are at least 2, S is either strictly better than S or it is preferable by the breaking ties criterion, a contradiction to the optimality of S.

Suppose now that there are three cliques A, B, C having a vertex of I each and a, b, c ≥ 1 vertices of K, respectively. Then

S = S \ {A, B, C} ∪ {(A ∩ K) ∪ (B ∩ K) ∪ (C ∩ K), A ∩ I, B ∩ I, C ∩ I},
with respect to S, has ab + ac + bc new internal edges that join two vertices of K in G and looses a + b + c edges that join vertices of K with vertices of I, so as ab ≥ a, bc ≥ b, and ca ≥ c, S is either strictly better than S or it is preferable by the breaking ties criterion, a contradiction to the optimality of S.

Then S has exactly two cliques containing vertices of K, each of them contains a vertex of I, and at least one of them has only one vertex of K. So, there is a vertex v 1 in I adjacent to all but one vertex w in K, and that vertex w has a neighbor v 2 in I, and

S = {{v 1 }∪(K -{w}), {w, v 2 }}∪{{v} : v ∈ I, v = v 1 , v 2 }.

Chordal graphs

Chordal graphs form an extensively studied class of graphs, as their peculiar clique-based structure allows an efficient solution for algorithmic problems. A very nice survey by Blair and Peyton on chordal graphs properties can be found in [START_REF] Blair | An introduction to chordal graphs and clique trees[END_REF].

In order to prove the main result of this section, we will show first a simple general lemma.

Lemma 1 (True twins). Let G be graph and v, w be true twins in G. Then, for every optimal solution of the unweighted cluster deletion problem, v and w belong to the same clique of the partition.

Proof. Suppose, on the contrary, that there is an optimal clique partition S such that v belongs to a clique C 1 and w to a different clique C 2 . Without loss of generality, we may assume

|C 1 | ≤ |C 2 |.
But then S = S \{C 1 , C 2 }∪{C 1 \{v}, C 2 ∪{v}} has strictly less weight than S, a contradiction.

Theorem 3 (NP-completeness on unweighted chordal graphs). The cluster deletion problem is NP-complete for unweighted P 5 -free chordal graphs.

Proof. The proof of this theorem is similar to the proof of Theorem 1. The reduction is done again from the X3C problem. Let X = {x 1 , . . . , x 3q } and C = {c 1 , . . . , c m } be an instance of the X3C problem, where each element c i ∈ C is a 3-element subset of X, with m ≥ q ≥ 1. We want to know if there exists a subset C ⊆ C with size q such that each element in X belongs to exactly one of the elements in C . We construct a graph G = (V, E) as follows. The set of vertices V is formed by the subsets K X , K c 1 , . . . , K cm , where K X = {v x i : x i ∈ X} is the subset of vertices representing the elements of X. Let β = 3q. For each 3-subset c i ∈ C, we construct a set of vertices

K c i = {v c i,1 , . . . , v c i,β } with cardinality β.
The set of edges is constructed as follows: K X induces a clique of size β, and also each K c i induces a clique of size β, for 1 ≤ i ≤ m. Finally, for each c i ∈ C such that c i = {x i 1 , x i 2 , x i 3 }, we add all the edges between the vertices of the clique K c i to the vertices

v x i 1 , v x i 2 , v x i 3 ∈ K X .
Clearly, this construction is done in polynomial time and the obtained graph G is an unweighted P 5 -free chordal graph. Now, since for each 1 ≤ i ≤ m, all the β vertices of the clique K c i are true twins, by Lemma 1 they must belong to the same clique in an optimal partition S. Therefore, we can contract each clique K c i , with 1 ≤ i ≤ m, into a single vertex c i and replace each subset of β edges between K c i and the vertex v x i j ∈ K X by a single edge with weight β, where 1 ≤ j ≤ 3 and x i j ∈ c i . This is exactly the weighted split graph used in Theorem 1.

Block graphs

A graph G is a block graph if it is a connected graph and every block (i.e. maximal 2-connected component) is a clique. Block graphs are a subclass of chordal graphs. The first result in this section concerns weighted 1-split graphs, a particular subclass of block graphs. We will use submodular functions minimization in order to solve the cluster deletion problem on 1-split graphs, and then we will reduce the problem on weighted block graphs to the problem on weighted 1-split graphs.

Given a finite nonempty set V of cardinality n, a function f defined on all the subsets of V is called

submodular if it satisfies f (X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ),
for every X, Y ⊆ V . In [START_REF] Iwata | A combinatorial strongly polynomial algorithm for minimizing submodular functions[END_REF] and [START_REF] Schrijver | A combinatorial algorithm minimizing submodular functions in strongly polynomial time[END_REF] are presented combinatorial polynomial-time algorithms for finding a minimizer of a general submodular function, provided that an oracle for evaluating the function value is available. The number of oracle calls is bounded by a polynomial in the size of the underlying set.

Theorem 4 (Polynomiality on weighted 1-split graphs). Cluster deletion is polynomial time solvable for weighted 1-split graphs, provided that the weights of the internal edges of the clique are nonnegative.

Proof. In the cluster deletion problem of a 1-split graph whose split partition is (K, I), the solution has at most one clique K 1 that has no intersection with I, some pairs {v, u} with v ∈ K and u ∈ I, and some isolated vertices from I. Each vertex of I has at most one neighbor in K, and if {v, u} belongs to the solution, then u is one of the neighbors of v in I maximizing the weight of the edge vu. Indeed, we can preprocess the graph, identifying a subset of vertices of I that will be trivial cliques in the solution, and leaving a graph in which each vertex of K has at most one neighbor in I. If the subset K 0 of vertices of K having no neighbors in I is nonempty, it will be part of the clique K 1 in the solution. We will name the set K \ K 0 as {v 1 , . . . , v r } and their respective neighbors in I as {u 1 , . . . , u r }. So, a candidate solution is totally determined by the subset S of {1, . . . , r} such that the solution is {{v i , u i }} i ∈S ∪ {K 1 ∪ {v i : i ∈ S}} ∪ {{u i }} i∈S . The subset S is not necessarily a proper subset of {1, . . . , r} and it could be empty. We will prove that the function f that assigns to S the difference of weight between the candidate solution associated with S and the solution associated with the empty set is submodular, and thus the set S that minimizes that function can be found in polynomial time. The function f can be computed in polynomial time for a subset S, and is defined as

f (S) = i∈S w(v i u i ) - i,j∈S w(v i v j ) - i∈S,z∈K 0 w(v i z)
Let S, T ⊆ {1, . . . , r}. We will show that f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ), provided that the weights of the edges joining two vertices of K are nonnegative. It is easy to see that

i∈S w(v i u i ) + i∈T w(v i u i ) = i∈S∪T w(v i u i ) + i∈S∩T w(v i u i ) and that i∈S,z∈K 0 w(v i z) + i∈T,z∈K 0 w(v i z) = i∈S∪T,z∈K 0 w(v i z) + i∈S∩T,z∈K 0 w(v i z). So we have to show that i,j∈S w(v i v j ) + i,j∈T w(v i v j ) ≤ i,j∈S∪T w(v i v j ) + i,j∈S∩T w(v i v j ), but i,j∈S∪T w(v i v j ) + i,j∈S∩T w(v i v j ) -i,j∈S w(v i v j ) -i,j∈T w(v i v j ) = i∈S\T,j∈T \S w(v i v j ) ≥ 0.
If the weight of the internal edges is 1, the algorithm is very simple. We name the vertices in K \ K 0 as {v 1 , . . . , v r } and their respective neighbors in I as {u 1 , . . . , u r }, in such a way that w(v 1 u 1 ) ≤ • • • ≤ w(v r u r ). Then the only sets that are candidates to minimize f are the empty set and the sets {1, . . . , j}, for 1 ≤ j ≤ r.

Based on the solution of cluster deletion for weighted 1-split graphs, we will solve the problem for weighted block graphs, when the weight of the edges is nonnegative.

Theorem 5 (Polynomiality on weighted block graphs). Cluster deletion is polynomial time solvable for weighted block graphs, when the weight of the edges is nonnegative.

Proof. Let G = (V, E) be a weighted block graph, such that the weight w of the edges is nonnegative. An end-block of a graph is a block containing exactly one cut-vertex. It is known that every connected graph that is not 2-connected has an end-block. Inductively, the blocks of G can be enumerated as B 1 , . . . , B r in such a way that B i is an end-block of the graph induced by B i ∪ B i+1 ∪ • • • ∪ B r . We will process the blocks in that order by solving each time a subproblem and reducing iteratively the graph to a simpler graph. Then we will reconstruct the solution for the original graph based on the solution of each subproblem and the recursive solution of the reduced graph.

By the way of choosing the order of the blocks, when processing the block B i for i < r, it will have exactly one cut-vertex v joining B i with non-processed blocks. The graph G 0 will be G, we will create a graph G i from G i-1 by replacing the connected component of G i-1 \ {v} that contains B i \ {v} by a vertex u adjacent to v and we will assign to the edge vu a suitable weight. It means, inductively, that when processing block B i , the connected component H of G i-1 \ {v} that contains B i \ {v} is a 1-split graph, and so is the graph induced by V (H) ∪ {v}. We will define w(uv) = y∈H,vy∈E w(vy) + w(S H ) -w(S H∪{v} ), where S H∪{v} and S H are optimal solutions for the cluster deletion problem on the 1-split graph induced by V (H) ∪ {v}, and H, respectively. Notice that we can find S H∪{v} and S H by Theorem 4. Claim 3. Let S i be an optimal solution of the cluster deletion problem for G i . If {u, v} ∈ S i , then S i \ {{u, v}} ∪ S H∪{v} is an optimal solution for G i-1 . If {u, v} ∈ S i , then S i \ {{u}} ∪ S H is an optimal solution for G i-1 .

Let S i-1 be an optimal solution of the cluster deletion problem for G i-1 . Let S 1 i-1 the subset of cliques of S i-1 containing vertices of H and

S 2 i-1 = S i-1 \ S 1 i-1 . We have that either v belongs to a clique in S 1 i-1 or not. As v is a cut-vertex of G i-1
, it is clear that in the first case S 1 i-1 is an optimal solution for the cluster deletion problem on the graph induced by V (H) ∪ {v}, while in the second case S 1 i-1 is an optimal solution for the cluster deletion problem on the graph H. On the other hand, in the first case, S 2 i-1 ∪ {v, u} will be a feasible solution for G i , with weight w(S i-1 ) -w(S H∪{v} ), while in the second case, S 2 i-1 ∪ {u} will be a feasible solution for G i , with weight w(S i-1 ) -w(S H ) -y∈H,vy∈E w(vy) + w(uv) = w(S i-1 ) -w(S H∪{v} ). So, if S i is an optimal solution of the cluster deletion problem for G i , then w(S i ) ≤ w(S i-1 ) -w(S H∪{v} ), which implies w(S i ) + w(S H∪{v} ) ≤ w(S i-1 ). Now, let us see that the weight of the solutions proposed for G i-1 in each case is exactly w(S i ) + w(S H∪{v} ), which makes them respectively optimal.

If {u, v} ∈ S i , it is easy to see that w(S i \{{u, v}}∪S H∪{v} ) = w(S i )+w(S H∪{v} ). If {u, v} ∈ S i , when considering S i \{{u}}∪S H in G i-1 , we do not have to delete the edge uv, but we have to delete every edge joining v with vertices in H, so w(S i \{{u}}∪S H ) = w(S i )-w(uv)+ y∈H,vy∈E w(vy)+ w(S H ) = w(S i ) + w(S H∪{v} ). This ends the proof of this claim. ♦ Finally, when processing block B r , the graph G r-1 is completely reduced to a 1-split graph, so we can also apply the algorithm of Theorem 4 in order to obtain an optimal partition for G r-1 , and then recursively construct the solution for the graph G 0 = G, following the ideas in the Claim.

If the graph G is unweighted, then the 1-split graphs in which we need to solve the subproblems have weight 1 in every internal edge. In that case, as we noticed in Theorem 4, the algorithm is very simple.

Interval graphs

Other interesting subclasses of chordal graphs are interval graphs. A graph G is an interval graph if G is the intersection graph of a finite family of intervals of the real line, and it is a proper interval graph if it admits an intersection model in which no interval properly contains another. A unit interval graph is the intersection graph of a finite family of intervals of the real line, all of the same length. Proper interval graphs and unit interval graphs coincide, and they are exactly the claw-free interval graphs [START_REF] Roberts | Indifference graphs[END_REF] (the claw is the complete bipartite graph K 1,3 ).

A restricted subclass of unit interval graphs is the class of paths of cliques. A graph is a path of cliques if after identifying true twins into a single vertex, the resulting graph is a single path. That is, its vertex set can be partitioned into sets A 1 , . . . , A n in such a way that for each pair of vertices v, w, such that v ∈ A i and w ∈ A j , they are adjacent if and only if either i = j or i = j + 1 or i = j -1. They also appear in the literature as line graphs of multipaths.

We will prove the next result with an approach similar to the proof od Theorem 4. We will define an initial solution and then we will code every other solution by a subset of a set. Finally, we will show that the function that assigns to every subset the difference of weights between its associated solution and the initial one is submodular.

Theorem 6 (Polynomiality on weighted paths of cliques). The cluster deletion problem is polynomial-time solvable for weighted paths of cliques, when the weights are nonnegative.

Proof. Let A 1 , . . . , A n be the vertex set partition of a path of cliques G. Without loss of generality we can assume that n is even, by adding if necessary a set A n+1 with only one vertex adjacent to every vertex in A n with edges of weight zero. Let n = 2r and define the initial solution as the cliques A 2k-1 ∪ A 2k for 1 ≤ k ≤ r. Every vertex of A i , for 1 < i < n, has two possibilities. Either it will be part of a clique contained in A i-1 ∪ A i or it will be part of a clique contained in A i ∪ A i+1 . So, an arbitrary solution is completely defined by the subset S of V (G) \ (A 1 ∪ A n ) that, from the initial solution, are moved into a clique contained in A 2j ∪ A 2j+1 for some integer 1 ≤ j ≤ r -1. We will define f (S) for a subset S of V (G) \ (A 1 ∪ A n ) as the difference between the weight of the solution associated with S and the weight of the initial solution. The optimal solution will be given by the subset S that minimizes function f . We will show now that S is a submodular function and so a minimizer can be found in strongly polynomial time.

The function f can be expressed as f (S) = 1≤k≤r f k (S), where

f k (S) = v∈S∩A 2k u∈A 2k-1 w(vu) + v∈S∩A 2k-1 u∈A 2k w(vu) + v∈S∩A 2k-1 u∈A 2k-1 \S w(vu) + v∈S∩A 2k u∈A 2k \S w(vu) - v∈S∩A 2k u∈S∩A 2k+1 w(vu) - v∈S∩A 2k-1 u∈S∩A 2k w(vu)
where in order to simplify the expression, we let A 2r+1 = ∅. Notice that the last term in the sum avoids the double counting of the first two terms.

For each value of k, define f k 1 (S), . . . , f k 6 (S) as the six terms of f k (S). It is easy to see that for i = 1, 2 and S, T subsets of

V (G) \ (A 1 ∪ A n ), it holds f k i (S) + f k i (T ) = f k i (S ∪ T ) + f k i (S ∩ T
). We will prove that, for i = 3, . . . , 6,

f k i (S) + f k i (T ) ≥ f k i (S ∪ T ) + f k i (S ∩ T ). For S, T subsets of V (G) \ (A 1 ∪ A n ),
f k 3 (S) + f k 3 (T ) -f k 3 (S ∪ T ) -f k 3 (S ∩ T ) = 2 v∈(S\T )∩A 2k-1 u∈(T \S)∩A 2k-1
w(vu) ≥ 0 because the weights are nonnegative, so f k 3 is submodular. The proof for f k 4 is identical. Recall that f k 5 (S) = -v∈S∩A 2k ,u∈S∩A 2k+1 w(vu). By using again the decomposition S as (S \ T ) ∪ (S ∩ T ) (resp. T as (T \ S) ∪ (S ∩ T )); and S ∪ T as (S \ T ) ∪ (T \ S) ∪ (S ∩ T ), it can be see that because the weights are nonnegative, so f k 5 is submodular. The proof for f k 6 is identical. Finally, the sum of submodular functions is submodular, and this completes the proof.

f k 5 (S) + f k 5 (T ) -f k 5 (S ∪ T ) -f k 5 (S ∩ T ) =
A split graph is called complete if each vertex of the stable set is adjacent to all vertices of the clique. By slightly modifying the proof of Theorem 1, we can prove the following.

Theorem 7 (NP-completeness on weighted complete split graphs). The cluster deletion problem is NP-complete for weighted complete split graphs, even if the weight of all the internal edges of the clique is 1.

Proof. We will reduce once more time the X3C problem. Let X = {x 1 , . . . , x 3q } and C = {c 1 , . . . , c m } be an instance of the X3C problem, where each element c i ∈ C is a 3-element subset of X, with m ≥ q ≥ 1. We want to know if there exists a subset C ⊆ C with size q such that each element in X belongs to exactly one of the elements in C . We will construct an edge-weighted complete split graph G = (K X ∪ I C , E), where K X induces a clique with 3q vertices and I C induces an independent set with m vertices. In fact, for each element x i ∈ X there is a vertex v x i in K X and for each 3-subset c j ∈ C there is a vertex v c j ∈ I C . The edge set E is formed as follows:

E = E X ∪ E C ∪ E C , where E X = {v x i v x j : i = j, v x i , v x j ∈ K X }, E C = {v c j v x j 1 , v c j v x j 2 , v c j v x j 3 : v c j ∈ I C , v x j 1 , v x j 2 , v x j 3 ∈ K X , c j ∈ C and c j = {x j 1 , x j 2 , x j 3 }},
cliques consist of consecutive vertices, and let i minimum such that either i < m(B 1 ) and v i ∈ B 1 , or m(B j-1 ) < i < m(B j ) but v i ∈ B j , for some j. Let j such that v i ∈ B j . Then, by the choice of i, all the vertices of B j have subindex greater than i and j > j so m(B j ) > m(B j ). Since v i is adjacent to v m(B j ) and G is a proper interval graph with canonical ordering v 1 , . . . , v n , the vertices v i , . . . , v m(B j ) form a clique and, in particular, B j ∪ {v m(B j ) } is a clique and v i is adjacent to v m(B j ) . So, independently of i being greater os less than the minimum index of a vertex in B j , B j ∪ {v i } is a clique. Then, either |B j | ≥ |B j | and S \ {B j , B j } ∪ {B j ∪ {v i }, B j \ {v i }} is a solution strictly better than S, or |B j | < |B j | and S \ {B j , B j } ∪ {B j \ {v m(B j ) }, B j ∪ {v m(B j ) }} is a solution strictly better than S, a contradiction in both cases.

Theorem 9 (Polynomiality on unweighted unit interval graphs). The cluster deletion problem can be solved in polynomial time on unweighted unit interval graphs. Proof. By using Lemma 2, we can easily develop a dynamic programming algorithm. For i = 0, 1, . . . , n, let f (i) be the value of an optimal cluster deletion solution for the subgraph of G induced by v 1 , . . . , v i . Then f (0) = f (1) = 0 and, for i > 1, f (i) will be the minimum over all the possible cliques containing v i , i.e., {v j , . . . , v i } where either j = i or v j v i ∈ E(G), of f (j -1) plus the amount of vertices joining {v 1 , . . . , v j-1 } with {v j , . . . , v i } (this is 0 if j = 1). By keeping also the number j realizing the minimum f (i), we can also reconstruct the partition itself. General interval graphs do not have the same clique structure as unit interval graphs. And for weighted unit interval graphs, Lemma 2 does not hold. An example of this is the graph P 2 6 , whose vertices are v 1 , . . . , v 6 and v i is adjacent to v j if and only if 1 ≤ |i -j| ≤ 2. It is easy to see that the only possible canonical orderings for P 2 6 are v 1 , . . . , v 6 or v 6 , v 5 , . . . , v 1 . Let w be defined on the edges of P 2 6 such that w(v 2 v 4 ) = w(v 3 v 5 ) = 100 and w(e) = 1 for every other edge e. Any solution to the cluster deletion problem that does not contain {v 2 , v 4 } and {v 3 , v 5 } as cliques has weight at least 100, so the optimal solution is to have {v 2 , v 4 }, {v 3 , v 5 }, and isolated vertices, with a weight equal to 7.

The example shows that the idea of Theorem 9 cannot be generalized in a straightforward way. It remains as an open question the computational complexity of the cluster deletion problem on unweighted interval graphs and on weighted unit interval graphs.

Complete split graphs are also cographs (i.e. P 4 -free graphs, that are not necessarily chordal as they may contain C 4 as induced subgraph). The cluster deletion problem on unweighted cographs was solved in polynomial time by Gao et al. in [9]. As a corollary of Theorem 7, we have this complexity result for the weighted case.

Corollary 2 (NP-completeness on weighted cographs). The cluster deletion problem is NPcomplete for weighted cographs.

Further results and open problems

We showed in Theorem 1 that the cluster deletion problem is NP-complete for weighted 3-split graphs even if the weight of all the internal edges of the clique is 1 and the weight of the edges between the clique and the stable set is uniform. We have seen also in Theorem 4 that the cluster deletion problem is polynomial-time solvable for weighted 1-split graphs. As for 2-split graphs, we will show next that, under the conditions of Theorem 1 (the weight of all the internal edges of the clique is 1 and the weight of the edges between the clique and the stable set is uniform) the problem is polynomial-time solvable.

Theorem (Polynomiality on restricted weighted 2-split graphs). The cluster deletion problem is polynomial-time solvable for weighted 2-split graphs, if the weight of all the internal edges of the clique is 1 and the weight of the edges between the clique and the stable set is uniform.

Proof. Let G be a 2-split graph with split partition (K, I), and β be the weight of the edges between K and I. Let us create a graph G with vertex set K , where K is the subset of vertices of K that have at least one neighbor in I, and such that two vertices are adjacent in G if they have a common neighbor of I in G. Minimizing the sum of the external edges of a clique partition of G is equivalent to maximizing the sum of the internal edges of the clique partition. There are three possible class of cliques in G: those containing one vertex of I and two vertices of K, those containing one vertex of I and one vertex of K, or those completely included in K, and by optimality, there is just one of such cliques. Then the sum of internal edges will be a( 2β + We leave as an open problem the computational complexity of the cluster deletion problem in general weighted 2-split graphs, or even when the weight of all the internal edges of the clique is 1 but the weight of the edges between the clique and the stable set is arbitrary and not necessarily uniform.

  and by decomposing S as (S \ T ) ∪ (S ∩ T ) (resp. T as(T \S)∪(S ∩T )); V (G)\S as (T \S)∪(V (G)\(S ∪T )) (resp. V (G)\T as (S \T )∪(V (G)\(S ∪T ))); S ∪ T as (S \ T ) ∪ (T \ S) ∪ (S ∩ T ); and V (G) \ (S ∩ T ) as (T \ S) ∪ (S \ T ) ∪ (V (G) \ (S ∪ T )), it can be see that

  v∈(S\T )∩A 2k u∈(T \S)∩A 2k+1 w(vu) + v∈(T \S)∩A 2k u∈(S\T )∩A 2k+1 w(vu) ≥ 0

  1) + bβ + c(c -1)/2 ( * ), where 0 ≤ a ≤ ν(G ) (ν(G ) is the value of a maximum matching of G ), 0 ≤ b ≤ |K | -2a, and c = |K| -2a -b. It is easy to see that in an optimal solution, either a = ν(G ) or b = 0. In the first case, after the substitution a = ν(G ), the coefficient of b in the expression ( * ) is positive, so the maximum is attained either by b = 0 or by b = |K | -2ν(G ). In the second case, after the substitution b = 0, the coefficient of a in the expression ( * ) is positive, so the maximum is attained either by a = 0 or by a = ν(G ). So the problem is reduced to solve maximum matching in G and then compute the value of ( * ) for the three possible optimal solutions a = 0, b = 0; a = ν(G ), b = 0; and a = ν(G ), b = |K | -2ν(G ).

* Partially supported by MathAmSud Project 13MATH-07 (Argentina-Brazil-Chile-France), UBACyT Grant 20020100100980, CONICET PIP 112-200901-00178 and 112-201201-00450CO and ANPCyT PICT 2012-1324 (Argentina), FONDECyT Grant 1140787 and Millennium Science Institute "Complex Engineering Systems" (Chile).

and E C = {v c j v x i : v c j ∈ I C , v x i ∈ K X , i ∈ {j 1 , j 2 , j 3 }, c j ∈ C and c j = {x j 1 , x j 2 , x j 3 }}. Finally, the weight of each edge in E X ∪ E C is equal to 1, and the weight of each edge in E C is equal to β = 3q 2 + 3m(q -1) + 1. Clearly, G is a complete split graph and its construction is done in polynomial time. Let W = 3q 2 -3q + 3(m -q)β + 3m(q -1). We will show that there exists a subset C ⊆ C, with |C | = q, exactly covering X if and only if G has a clique partition where the sum of the weights of edges outside the cliques is at most W . In other words, there exists a solution for the X3C problem if and only if there exists an optimal solution for the cluster deletion problem for G with weight at most W .

Assume first that there exists C ⊆ C, with C = {c 1 , . . . , c q } such that c i ∩ c j = ∅ whenever i = j, and c j ∈C c j = X. The clique partition for G can be constructed as follows: for each

Each one of the remaining m -q vertices in I C form clique with size one. It is easy to see that the sum of the edge weights outside those cliques is exactly equal to W .

Conversely, assume that G has a clique partition with weight at most W . We should to prove that there exists C ⊆ C, with |C | = q, such that C is an exact cover for X. For this, we analyze first the structure of such a solution. Notice that β is greater than the sum of the weights of all the edges in E X ∪ E C , so a solution with weight W should delete exactly 3(m -q) edges of E C . It cannot delete less than 3(m -q) because each vertex of K X can be in the same clique with at most one vertex of I C . So, every vertex of K X is in a clique with one vertex of I C , and joined to that vertex by an edge of the set E C . Than means that all the edges of E C are deleted and that each clique contains at most three vertices of K X . By the value of W , we can see that each clique should contain exactly three vertices of K X , and following the lines of the proof of Theorem 1, such a solution corresponds to a solution of the X3C instance, which ends the proof of this theorem.

Complete split graphs are also interval graphs, but (in general) they are not unit interval graphs, as if the stable set is of size at least three and the complete set is nonempty, they contain a claw (the complete bipartite graph K 1,3 ), that is not a unit interval graph. So, we have the following corollary.

Corollary 1 (NP-completeness on weighted interval graphs). The cluster deletion problem is NPcomplete for weighted interval graphs.

For unweighted unit interval graphs instead, we will show that the cluster deletion problem is polynomial-time solvable. First, we need to state some known results and show a lemma describing the structure of an optimal solution. Theorem 8 (Roberts, 1969 [15]). A graph G is a unit interval graph if and only if its vertices can be linearly ordered such that, for each clique M of G, the vertices contained in M are consecutive.

Such an ordering is called a canonical ordering of the vertices.

Lemma 2 (Consecutiveness for unweighted unit interval graphs). Let G be an unweighted unit interval graph and v 1 , . . . , v n be a canonical ordering of the vertices of G. Then there is an optimal solution of the cluster deletion problem for G, such that each clique of the solution consists of consecutive vertices in that ordering.

Proof. Let us define, for each clique B of the optimal solution S, m(B) = max{j : v j ∈ B}. Now, let B 1 , . . . , B k be the cliques of the solution ordered by m increasingly. Suppose that not all the


text:
Flavia Bonomo
email: fbonomo@dc.uba.ar

Guillermo Duran
email: gduran@dm.uba.ar

Amedeo Napoli
email: amedeo.napoli@loria.fr

Mario Valencia
email: valencia@lipn.univ-paris13.fr

Mario Valencia-Pabon

Keywords: Cliques, Edge-deletion, Cluster deletion, Sum coloring, P 4 -sparse, Integer sequences

teaching and research institutions in France or abroad, or from public or private research centers.

A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4 -sparse graphs

A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P 4 -sparse graphs *

Introduction

A cluster graph is a graph in which every connected component is a clique (i.e. a complete subgraph).

Cluster graphs have been used in a variety of applications whenever clustering of objects is studied or when consistent data is sought among noisy or error-prone data [START_REF] Bansal | Correlation clustering[END_REF]. The cluster deletion problem asks for the minimum number of edges that can be removed from an input graph to make the resulting graph a cluster graph. There exist several results for the cluster deletion problem (see for example [START_REF] Böcker | Even faster parametrized cluster deletion and cluster editing[END_REF][START_REF] Shamir | Cluster graph modification problems[END_REF][START_REF] Komusiewicz | Cluster editing with locally bounded modifications[END_REF] and references therein). The cluster deletion problem is known to be NPcomplete [START_REF] Shamir | Cluster graph modification problems[END_REF]. Recently, Gao et al. [START_REF] Gao | The cluster deletion problem for cographs[END_REF] have shown that the greedy algorithm that finds iteratively maximum cliques, gives an optimal solution for the class of graphs known as cographs. It implies that the cluster deletion problem is polynomial-time solvable on cographs.

A vertex coloring of a graph is an assignment of positive integers to the vertices of the graph such that adjacent vertices receive different integers. The sum of a vertex coloring of a graph is the sum of the integers assigned to the vertices. The minimum sum coloring problem ask for the 1 smallest sum that can be achieved by any vertex coloring of an input graph. The minimum sum coloring problem is motivated by applications in scheduling [START_REF] Bar-Noy | On chromatic sums and distributed resource allocation[END_REF][START_REF] Halldórsson | Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs[END_REF] and VLSI design [START_REF] Szkaliczki | Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete[END_REF]. In [START_REF] Kubicka | An introduction to chromatic sums[END_REF] it is shown that the problem is NP-hard in general, but polynomial time solvable for trees. The dynamic programming algorithm for trees can be extended to partial k-trees, block graphs and cographs [START_REF] Jansen | Complexity results for the optimum cost chromatic partition problem[END_REF]. Recently, Bonomo and Valencia-Pabon [START_REF] Bonomo | Minimum Sum Coloring of P 4 -sparse graphs[END_REF][START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] have shown that the minimum sum coloring problem can be solved in polynomial time on a wide subclass of P 4 -sparse graphs.

A graph is P 4 -sparse if every 5-vertex subset contains at most one P 4 . The family of P 4 -sparse graphs generalize the family of cographs (i.e. P 4 -free graphs) and they can be recognized in linear time [START_REF] Jamison | Recognizing P 4 -sparse graphs in linear time[END_REF].

If G 1 and G 2 are two vertex disjoint graphs, then their union

G 1 ∪ G 2 is the graph with vertex set V (G 1 ∪ G 2 ) = V (G 1 ) ∪ V (G 2 ) and edge set E(G 1 ∪ G 2 ) = E(G 1 ) ∪ E(G 2 ). Similarly, their join G 1 ∨G 2 is the graph with V (G 1 ∨G 2 ) = V (G 1 )∪V (G 2 ) and E(G 1 ∨G 2 ) = E(G 1 )∪E(G 2 )∪{(x, y) : x ∈ V (G 1 ), y ∈ V (G 2 )}.
A spider is a graph whose vertex set can be partitioned into S, C and R, where S = {s 1 , . . . , s k } (k ≥ 2) is an independent set; C = {c 1 , . . . , c k } is a complete set; s i is adjacent to c j if and only if i = j (a thin spider ), or s i is adjacent to c j if and only if i = j (a thick spider ); R is allowed to be empty and if it is not, then all the vertices in R are adjacent to all the vertices in C and non-adjacent to all the vertices in S. Clearly, the complement of a thin spider is a thick spider, and vice-versa. The triple (S, C, R) is called the spider partition, and can be found in linear time [START_REF] Jamison | Recognizing P 4 -sparse graphs in linear time[END_REF]. The sets S, C and R are called the legs, body and head of the spider, respectively. The size of the spider will be |C|. P 4 -sparse graphs have a nice decomposition theorem as follows.

Theorem 1. [START_REF] Jamison | A tree representation for P 4 -sparse graphs[END_REF] If G is a non-trivial P 4 -sparse graph, then either G or G is not connected, or G is a spider.

To each P 4 -sparse graph G one can associate a corresponding decomposition rooted tree T in the following way. Each non-leaf node in the tree is labeled with either "∪" (union-nodes), or "∨" (join-nodes) or "SP" (spider-partition-nodes), and each leaf is labeled with a vertex of G. Each non-leaf node has two or more children. Let T x be the subtree of T rooted at node x and let V x be the set of vertices corresponding to the leaves in T x . Then, each node x of the tree corresponds to the graph G x = (V x , E x ). An union-node (join-node) corresponds to the disjoint union (join) of the P 4 -sparse graphs associated with its children. A spider-partition-node corresponds to the spider with spider-partition (S, C, R) where G[S], G[C], and G[R] are its children. Finally, the P 4 -sparse graph associated with the root of the tree is just G, the P 4 -sparse graph represented by this decomposition tree. The decomposition tree associated to a P 4 -sparse graph can be computed in linear time [START_REF] Jamison | A tree representation for P 4 -sparse graphs[END_REF].

Maximal sequences and optimal solutions

The following approach was used by Bonomo and Valencia-Pabon [START_REF] Bonomo | Minimum Sum Coloring of P 4 -sparse graphs[END_REF][START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] in order to deal with the minimum sum coloring (MSC) problem on P 4 -sparse graphs. A k-coloring of a graph G = (V, E) is a partition of the vertex set V into k independent sets S 1 , . . . , S k , where each vertex in S i is colored with color i, for 1 ≤ i ≤ k. So, for any such k-partition of V into independent sets, we can associate a non-negative sequence p such that p[i] = |S i | for i = 1, . . . , k and p[i] = 0 for i > k. In the sequel, we deal with finite-support non-negative integer sequences only. Let |p| = max{i : p[i] > 0}.

Definition 1. Let p and q be two integer sequences. We say that p dominates q, denoted by p q, if for all t ≥ 1 it holds that 1≤i≤t p

[i] ≥ 1≤i≤t q[i].
Let p be a sequence. We denote by p the sequence that results from p when we order it in a non-decreasing way. Clearly, p p.

The following lemma is the key for study the MSC problem on graphs.

Lemma 1 (Lemma 3 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF]). Let p and q be two sequences and let n = max{|p|, |q|}. If p q and

1≤i≤n p[i] = 1≤i≤n q[i], then it holds that 1≤i≤n i.p[i] ≤ 1≤i≤n i.q[i].
Notice that if the sequences represent partitions of the vertex set of a graph into independent sets, where the value of the i-th element of the sequence represents the size of the i-th independent set in the partition, then for the sum-coloring problem on graphs we can restrict us to study maximal sequences w.r.t. the partial order .

A similar approach has been used by Gao et al. [START_REF] Gao | The cluster deletion problem for cographs[END_REF] in order to deal with the cluster deletion problem on cographs. In fact, notice that an optimal solution of the cluster deletion problem in a graph G is a partition of the vertex set V into cliques M 1 , . . . , M t . So, for any partition of V into t cliques, we can associate a sequence p such that p [START_REF] Gao | The cluster deletion problem for cographs[END_REF] show the following result.

[i] = |M i | for i = 1, . . . ,
Theorem 2 (Theorem 4 in [START_REF] Gao | The cluster deletion problem for cographs[END_REF]). Let p and q be two integer partitions of some positive integer n, with p = q. If p q, then |p| ≤ |q|, and

|p| i=1 p[i] 2 > |q| i=1 q[i] 2 .
By Theorem 2, we can also restrict us to study maximal sequences w.r.t. the partial order in order to solve the cluster deletion problem on graphs. Notice also that maximal sequences for both problems (MSC and cluster deletion) are non-increasing sequences.

Clearly, there is a one-to-one correspondence between the maximal sequences corresponding to partitions of the vertex set of G into cliques and the maximal sequences corresponding to partitions of the vertex set of G into independent sets. Thus, by Theorem 2 and Lemma 1, there is a one-toone correspondence between the potentially optimal solutions for the cluster deletion problem of a graph G and the potentially optimal solutions for the minimum sum coloring of the complement graph G.

Nevertheless, when a graph G has more than one maximal sequence corresponding to partitions of its vertex set into cliques, the optimal solution for the cluster deletion problem of G and the optimal solution for the minimum sum coloring of its complement G may not correspond to the same sequence. We will provide an example of this in the next section.

This suggest that the computational complexity of the cluster deletion problem on a graph class G and the computational complexity of the minimum sum coloring problem on the class co-G (the class of complement graphs of graphs in G) can be different. But, to the best of our knowledge, there are not known examples of this behaviour.

Maximal sequences in P 4 -sparse graphs

The following results can be obtained directly from the definitions of union and join of graphs, and from the definition of a spider graph (see Section 1).

Proof. The results follows by Lemma 3 and by Lemma 12 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] concerning maximal sequences for the minimum sum coloring of thin spiders without head. Proof. The results follows by Lemma 3 and by Lemma 13 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] concerning maximal sequences for the minimum sum coloring of thick spiders without head.

Notice also that the trivial graph has only one maximal sequence p, with |p| = 1, where p[1] = 1. Therefore, we have the following two theorems whose proofs are similar to the ones of Theorem 2 and Theorem 3 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF], respectively. Theorem 3. Let G be a P 4 -sparse graph such that in its modular decomposition there are no thin spiders (S, C, R) with |C| ≥ 3 and R = Then, 1. G has a unique maximal sequence and an optimal solution for the cluster deletion problem of G can be computed from its modular decomposition in polynomial time.

2. In such an optimal solution, each M i is a maximum clique of G \ 1≤j<i M j .

Theorem 4. Let G be a P 4 -sparse graph on n vertices. Let t be the number of thin spiders (S, C, R) with |C| ≥ 3 and R = ∅ in the modular decomposition of G. Then, the number of maximal sequences of G is at most 2 t , and an optimal solution for the cluster deletion problem of G can be computed in 2 t P (n) time, where P (n) is a polynomial in n.

Notice that a cograph is a P 4 -sparse graph without spiders. Moreover, P 4 -sparse graphs having only spiders whose spider partition (S, C, R) is of size equal to 2 (i.e. |S| = |C| = 2) are known as P 4 -reducible graphs. The class of P 4 -reducible graphs was introduced by Jamison and Olariu [START_REF] Jamison | P 4 -reducible graphs -a class of uniquely tree-representable graphs[END_REF] as a generalization of cographs: a graph is P 4 -reducible if every vertex belongs to at most one P 4 . Finally, notice that thin spiders with size 2 are isomorphic to thick spiders with size 2. Therefore, by Theorem 3, we have the following corollary which generalizes the result by Gao et al. [START_REF] Gao | The cluster deletion problem for cographs[END_REF].

Corollary 1. Let G be a P 4 -reducible graph. Then, 1. G has a unique maximal sequence and an optimal solution for the cluster deletion problem of G can be computed from its modular decomposition in polynomial time.

2. In such an optimal solution, each M i is a maximum clique of G \ 1≤j<i M j .

Finally, we provide an example of a P 4 -sparse graph G having more than one maximal sequence and such that the optimal solution for the cluster deletion problem of G and the optimal solution for the minimum sum coloring of its complement G do not correspond to the same sequence.

Let N 3 be a thin spider of size 3 with no head (also known as net), and let G = (N 3 ∪N 3 )∨(K 1 ∪ K 1 ). By the theorems above, G has three different maximal sequences, namely p 1 = [3, 3, 2, 2, 2, 2], p 2 = [4, 3, 2, 2, 1, 1, 1], and p 3 = [4, 4, 1, 1, 1, 1, 1, 1]. The internal edges in the partition into cliques induced by each maximal sequence are, respectively, 10, 11 and 12. So, the number of removed edges are, respectively, 26, 25 and 24, being p 3 the sequence realizing the optimal solution. As for G, the sums of the colorings induced by each maximal sequence are, respectively, 45, 42 and 45, being in this case p 2 the sequence realizing the optimal solution.

Lemma 10 .

 10 Let G = (S, C, R) be a thin spider such that |C| ≥ 3 and R = ∅. Then, G has only two maximal sequences p 1 and p 2 , with |p 1 | = |C| and |p 2 | = |C| + 1, where p 1 [i] = 2 for 1 ≤ i ≤ |C|, and p 2 [1] = |C| and p 2 [i] = 1 for 2 ≤ i ≤ |C| + 1.

  t and p[i] = 0 for i > t. Notice that if M = (|M 1 |, . . . , |M t |) is an integer sequence associate to a partition into cliques of the set V , such that |M 1 | ≥ |M 2 | ≥ . . . ≥ |M t |, then M is an integer partition of the integer |V |. Gao et al.

Partially supported by UBACyT Grant 20020100100980, CONICET PIP 112-200901-00178 and 112-201201-00450CO and ANPCyT PICT 2012-1324 (Argentina), FONDECyT Grant 1140787 and Millennium Science Institute "Complex Engineering Systems" (Chile), and MathAmSud Project 13MATH-07 (Argentina-Brazil-Chile-France).

Lemma 2. Let G 1 and G 2 be graphs. Then,

Lemma 3. Let SP be a spider and (S, C, R) its spider partition. If SP is a thin (resp. thick) spider then, SP is a thick (resp. thin) spider with partition (C, S, R).

By Lemmas 2 and 3 we have that if G is a P 4 -sparse graph, then the complement graph G is also a P 4 -sparse graph. In fact, by using the tree decomposition of these graphs, we can deduce that union-nodes (resp. join-nodes) in G correspond to a join-nodes (resp. union-nodes) in G, and that thin spiders (resp. thick spiders) in G correspond to thick spiders (resp. thin spiders) in G.

The following operations between sequences were defined in [START_REF] Bonomo | Minimum Sum Coloring of P 4 -sparse graphs[END_REF][START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF]: Let p and q be two sequences.

• The join of p and q, denoted by p q, is the sequence that results by ordering in a non-increasing way the concatenation of sequences p and q.

• The sum of p and q, denoted by p + q, is the sequence such that its i-th value is equal to

• p and q are non-comparable, denoted by p||q, if p q and q p.

Moreover, in [START_REF] Bonomo | Minimum Sum Coloring of P 4 -sparse graphs[END_REF][START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] the following two lemmas have been obtained.

Lemma 4 (Lemma 4 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF]). Let p, p and q be sequences. If p p then p q p q.

Lemma 5 (Lemma 6 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF]). Let p, p and q be sequences. Then, p p if and only if p + q p + q.

In the sequel, maximal sequences of a graph G will correspond to potential solutions of the cluster deletion problem on G. Lemma 6. Let G 1 , G 2 be two vertex disjoints graphs, and let G = G 1 ∨ G 2 . Then, every maximal sequence p of G can be expressed as p = p 1 + p 2 , where p i is a maximal sequence of G i , for i = 1, 2.

Proof. The results follows by induction on |G|, by Lemma 2 on G, and by Lemma 7 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] concerning maximal sequences for the minimum sum coloring of the union of two graphs. Lemma 7. Let G 1 , G 2 be two vertex disjoints graphs, and let G = G 1 ∪ G 2 . Then, every maximal sequence p of G can be expressed as p = p 1 p 2 , where p i is a maximal sequence of G i , for i = 1, 2.

Proof. The results follows by induction on |G|, by Lemma 2 on G, and by Lemma 8 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] concerning maximal sequences for the minimum sum coloring of the join of two graphs. Lemma 8. Let G = (S, C, R) be a spider such that R = ∅. Then, the number of maximal sequences of G is equal to the number of maximal sequences of G[R]. Moreover, for each maximal sequence q of G[R] there exists only one maximal sequence q of G with |q | = |q|+|S| and where q

Proof. Notice that the spider G is a P 4 -sparse graph and so, G[R] (i.e. the subgraph of G induced by R) is also a P 4 -parse graph. Then, the result follows by induction on |G|, by Lemma 3 on G, and by Lemma 11 in [START_REF] Bonomo | On the Minimum Sum Coloring of P 4 -sparse graphs[END_REF] concerning maximal sequences for the minimum sum coloring of spiders.