WorksComputer Science
Cluster deletion in cographs, permutation graphs, and graphs with bounded clique number
Abstract
The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition problem asks for a partition of the vertex set into cliques that maximizes the number of edges within the parts. We give a simpler proof of a result of Gao, Hare, and Nastos (Discete Mathematics, 2013), that Cluster Deletion is polynomial-time solvable on cographs. In addition, we show that the natural linear programming formulation of Clique Partition is exact on cographs. We then show that Cluster Deletion is NP-complete on permutation graphs, which are a superclass of cographs. This answers an open question of Konstantinidis and Papadopoulos (Algorithmica, 2021). We also exhibit a permutation graph on nine vertices for which the linear programming formulation is not exact. Finally, for graphs with clique number at most , we give a polynomial-time -approximation algorithm for Clique Partition. More generally, the algorithm runs in polynomial time on every graph class for which a maximum clique can be found in polynomial time. For each fixed , we also construct infinitely many examples attaining the stated approximation ratio. The same examples show that, for Cluster Deletion , the algorithm is a -approximation and no better, for every fixed .
Introduction
Graph clustering is a fundamental problem in graph theory with numerous real-world applications, including the identification of functionally related genes in computational biology [5], community detection in social networks [14], image segmentation [33], and machine learning [3, 26]. The goal is to partition the vertices into clusters with many edges within clusters and few edges between clusters. Since a complete graph is the densest possible graph, this motivates the following approach.
Cluster Deletion:
Input: A graph .
Output: A minimum size set of edges such that is a disjoint union of complete graphs.
A disjoint union of complete graphs is also called a cluster graph. Given a graph as input, the CLUSTER DELETION problem is equivalent to maximizing the number of edges in a spanning subgraph of which is a cluster graph. We call the equivalent ‘complementary’ version the CLIQUE PARTITION problem.
Clique Partition:
Input: A graph .
Output: A partition of such that each is a clique of and is maximum.
Whenever we speak of NP-completeness, we refer to the natural decision versions of these problems. Since CLUSTER DELETION has a solution of size at most if and only if CLIQUE PARTITION has a solution of size at least , the two decision problems are equivalent, and both are clearly in NP.
Previous work. Shamir et al. [32] proved that CLUSTER DELETION is NP-hard for general graphs. Despite its computational difficulty, the problem has been extensively explored within the realms of parameterized complexity [4, 7, 9, 16, 19, 22], approximation algorithms [2, 8, 10, 30, 35, 36], and restricted graph classes.
For instance, CLUSTER DELETION is polynomial time solvable on cographs [16], split graphs [6, 25], (proper) interval graphs [6, 25], - and paw-free graphs [21] and graphs with maximum degree at most three [24]. On the other hand, NP-hardness persists on -free graphs with maximum degree four [24], planar graphs [17], chordal graphs [6], -free graphs and -free graphs [16].
Dessmark et al. [10] introduced a simple greedy strategy (which we call GREEDY) of repeatedly choosing maximum cliques, and proved that GREEDY is a 2-approximation for both CLUSTER DELETION and CLIQUE PARTITION. However, GREEDY does not necessarily run in polynomial time, since it requires MAX CLIQUE as a subroutine. Gao et al. [16] proved that GREEDY optimally solves CLIQUE PARTITION (and hence also CLUSTER DELETION) on cographs in polynomial time.
Interestingly, the weighted version of CLUSTER DELETION often exhibits greater computational hardness even on instances where the unweighted version is tractable. For instance, while unweighted CLUSTER DELETION is tractable on split graphs and cographs, the weighted version remains NP-hard on these classes [6]. There are also other popular generalizations of CLUSTER DELETION, including correlation clustering [3, 32], where one is allowed to delete or add edges. In this work, we focus on the unweighted variant of CLUSTER DELETION.
From the perspective of approximation algorithms, there have been a series of results for CLUSTER DELETION with progressively improved guarantees. The first approximation algorithm for CLUSTER DELETION achieved an approximation ratio of 4 using a linear programming (LP) relaxation [8]. Recent work of Balmaseda et al. [2] refined the analysis of two earlier algorithms, improving the approximation ratio from 4 to 3. The state of the art is the 2-approximation of Veldt et al. [36]. However, the LP-based approaches are computationally expensive due to the large number of constraints involved. To address this, recent work has introduced faster algorithms by leveraging alternative LP formulations such as Strong Triadic Closure (STC) labeling [34], resulting in practical 4-approximations [35]. Veldt [35] also proposed the first combinatorial algorithm, MatchFlipPivot, which achieves similar approximation guarantees at significantly reduced runtime.
The approximation status of the vertex version of CLUSTER DELETION, in which vertices rather than edges are deleted, was settled by Aprile et al. [1]. They gave a 2-approximation algorithm, which is best possible assuming the Unique Games Conjecture.
Our contributions. We begin by giving a much simpler proof of correctness of the main result from [16].
Theorem 1.1 ([16]). For every cograph , GREEDY outputs an optimal clique partition of .
The proof in [16] uses a quite subtle induction, which requires carefully extending a given clique partition while controlling the number of parts of the clique partition. We instead use the well-known fact that every cograph is either the disjoint union of two smaller cographs or the join of two smaller cographs. This gives a very clean inductive proof of Theorem 1.1. We also note that Theorem 4 from [16] is a direct consequence of the majorization inequality (Karamata’s inequality [27]). Our method also proves that the natural linear programming formulation is exact on cographs. To be precise, let be the family of all nonempty cliques of , and consider
Theorem 1.2. For every cograph , (LP) has an optimal solution in which every variable is in .
We next analyze CLIQUE PARTITION and CLUSTER DELETION on permutation graphs, which are a superclass of cographs. We prove that both problems are NP-complete on permutation graphs.
Theorem 1.3. CLUSTER DELETION and CLIQUE PARTITION are -complete on permutation graphs.
Theorem 1.3 settles an open question of Konstantinidis and Papadopoulos [25], and suggests that cographs are at the boundary of tractability and intractability for CLUSTER DELETION. The proof is a polynomial reduction from the OPTIMUM COST CHROMATIC PARTITION problem, which Jansen [23] proved to be -complete on permutation graphs. Since permutation graphs are exactly the graphs that are both comparability and cocomparability graphs, Theorem 1.3 also implies that CLUSTER DELETION is -complete on comparability graphs and on cocomparability graphs (Corollary 5.7).
Theorem 1.3 also has consequences for the linear program (LP). Although (LP) has exponentially many variables, it can be solved in polynomial time on permutation graphs via the ellipsoid method, so Theorem 1.3 implies that Theorem 1.2 does not extend to permutation graphs unless . In fact, we give an explicit permutation graph on nine vertices for which (LP) is not exact (Proposition 4.6).
Finally, we introduce another variant of GREEDY. For a graph , we let and be the number of vertices and edges, respectively, in a maximum clique of . The main idea is very simple: if , then a maximum clique partition is just a maximum matching, and hence can be found in polynomial-time via Edmonds’ matching algorithm [12]. Therefore, we propose the following modification of GREEDY. We run GREEDY as long as . Once , we instead use Edmonds’ matching algorithm on the remaining graph and add the maximum matching to the clique partition. We call this algorithm GREEDY EDMONDS. We prove that for every graph , GREEDY EDMONDS is a -approximation algorithm for CLIQUE PARTITION.
Theorem 1.4. For every graph , GREEDY EDMONDS returns a clique partition such that
where is the number of edges in an optimal clique partition of .
Although optimal solutions to CLIQUE PARTITION correspond to optimal solutions to CLUSTER DELETION, it is not necessarily true that an -approximate solution to CLIQUE PARTITION corresponds to an -approximate solution to CLUSTER DELETION. Indeed, for general -vertex graphs, Dessmark et al. [10] proved that there is no polynomial time -approximation algorithm for CLIQUE PARTITION (for some constant ), unless . On the other hand, as already mentioned, there are constant factor approximations for CLUSTER DELETION.
Note that GREEDY EDMONDS runs in polynomial time on any graph class for which a maximum clique can be found in polynomial time. Examples of such graph classes include graphs of bounded treewidth, perfect graphs (which include interval graphs and chordal graphs), distance-hereditary graphs, and graphs with bounded clique number. To our knowledge, for graphs of bounded clique number, GREEDY EDMONDS is the first polynomial-time algorithm that achieves an approximation ratio better than 2 for CLIQUE PARTITION. For general graphs , the best approximation algorithm for CLIQUE PARTITION is the -approximation algorithm from [10].
In view of Theorem 1.3, it is natural to ask for approximation algorithms for CLIQUE PARTITION on permutation graphs. Since maximum cliques and maximum matchings can be computed efficiently in permutation graphs, Theorem 1.4 yields the following corollary.
Corollary 1.5. Given an -vertex permutation graph , GREEDY EDMONDS returns in time a clique partition such that
where is the number of edges in an optimal clique partition of .
Proof. Let be an -vertex permutation graph. A permutation representation of can be found in time [28]. Since a maximum clique in a permutation graph can be found in time from such a representation [15], the greedy portion of GREEDY EDMONDS can be made to run in time. Finally, Rhee and Liang [31] proved that a maximum matching of an -vertex permutation graph can be found in -time. Thus, the total running time is .
Finally, we show that the approximation ratio in Theorem 1.4 is best possible for GREEDY EDMONDS, for every fixed value of the clique number, and that the same examples show that for CLUSTER DELETION the approximation ratio of GREEDY EDMONDS is exactly 2.
Theorem 1.6. For each fixed , there are infinitely many graphs with and clique partitions that can be output by GREEDY EDMONDS such that
where is the maximum number of edges in a clique partition of and is the minimum number of edges whose deletion turns into a cluster graph.
Preliminaries
All graphs in this paper are assumed to be simple and undirected. We use standard graph theoretical notation and terminology (see [11]). For example, we say that a graph is -free, if it does not contain as an induced subgraph. Note that is a cluster graph if and only if is -free, where is a 3-vertex path. A graph is a cograph if it is -free. The complement of a graph is denoted by . The disjoint union of two graphs and is denoted by , and the join is the graph obtained from by adding all edges between and .
A clique in a graph is a set of pairwise adjacent vertices of , and a stable set is a set of pairwise nonadjacent vertices. Thus, the stable sets of are exactly the cliques of . A clique partition of is a partition of into cliques of . If is a clique partition of , we let and denote the set of edges of contained (respectively, not contained) in the cliques of .
For each , we let and denote the set of all permutations of . We write a permutation as a word , and write for the position of the value in this word. The permutation graph associated with , denoted by , has vertex set and edge set
Equivalently, if and , then is an edge. Thus, cliques of are precisely the decreasing subsequences of the word , and stable sets of are precisely the increasing subsequences of . In particular, if is the reverse of , then , so the class of permutation graphs is closed under complementation. A graph is a permutation graph if and only if it is isomorphic to for some permutation . Given a permutation graph, such a permutation can be found in linear time [28]. Permutation graphs were originally introduced by [13] and [29]. A comprehensive overview of their structural and algorithmic properties is provided in [18].
Let . An -approximation algorithm is an algorithm which returns a solution which is within a multiplicative factor of to an optimal solution.
A Greedy Algorithm
In this section we review the algorithm for CLIQUE PARTITION introduced by Dessmark et al. [10]. The algorithm requires MAX CLIQUE as a subroutine, and therefore does not run in polynomial time for general graphs. However, in every graph class for which MAX CLIQUE can be computed in polynomial time, the algorithm runs in polynomial time. We call the algorithm GREEDY, since it proceeds greedily. The description of GREEDY is as follows. Let be a graph and a maximum clique of . GREEDY adds to the clique partition and then recurses on .
Dessmark et al. [10] proved that GREEDY is a 2-approximation algorithm for both CLUSTER DELETION and CLIQUE PARTITION.
Theorem 3.1. For every graph , GREEDY returns a clique partition such that $2\lvert E(\mathcal{X})\rvert \ge \operatorname{OPT}G.
Theorem 3.2. For every graph , GREEDY returns a clique partition such that , where OPT is the number of edges in an optimal solution to CLUSTER DELETION, and are the edges in which are not contained in a clique of .
For completeness, we include proofs of both Theorem 3.1 and Theorem 3.2 in Appendix A.
Input: A graph . Output: A clique partition of .
Set .
While : choose a maximum clique of ; set and .
Return .
Algorithm 1: GREEDY
Cluster deletion in cographs
In this section, we give a simpler proof that GREEDY computes an optimal clique partition in cographs, which was first proved in [16]. We require the following well-known property of cographs.
Lemma 4.1. Every cograph with at least two vertices has a partition of such that either or .
For a clique partition , let be its clique sizes in nonincreasing order, padded by zeros. We say that majorizes a clique partition , whose padded size sequence is , if
Lemma 4.2. If majorizes , then .
Proof. Both size sequences have the same sum, namely . The function is convex on the nonnegative reals, so the majorization inequality (equivalently, Karamata’s inequality [27]) gives
We prove the following statement, which is stronger than optimality.
Theorem 4.3. Let be a cograph. Every clique partition of output by GREEDY majorizes every clique partition of .
Proof. We proceed by induction on . The claim is immediate when . Let be a partition output by GREEDY, and let be any clique partition of . By Lemma 4.1, there is a nontrivial partition of such that or .
First suppose that . Every clique lies wholly in or wholly in . Moreover, the restriction of the greedy run to each side is clearly a greedy run on that side. Thus, the size sequence of is the nonincreasing merge of greedy size sequences and for and . Likewise, the size sequence of is the nonincreasing merge of size sequences and for clique partitions of the two sides. By induction, majorizes and majorizes . For each ,
where the parts of and are ordered by nonincreasing size. Now suppose that . A maximum clique in every induced subgraph of this join is the union of a maximum clique on each nonempty side. Consequently, there are greedy size sequences and for the two sides, padded by zeros, such that the greedy size sequence for is
Both component sequences are nonincreasing, so is also nonincreasing. Order the parts of by nonincreasing size, and put and . The nonempty intersections form clique partitions of and . If and denote the two intersection-size sequences in nonincreasing order, induction gives, for every ,
Thus, majorizes in both cases.
Combining Lemma 4.2 and Theorem 4.3 proves Theorem 1.1.
Remark 4.4. Since the majorization inequality holds for every convex function, Theorem 4.3 gives more than Theorem 1.1. Let be a function on the nonnegative integers with and with nondecreasing in . Extending piecewise linearly to gives a convex function, so Karamata’s inequality applies to integer sequences. Then, for every cograph , every clique partition output by GREEDY maximizes over all clique partitions of . Taking recovers Theorem 1.1. Taking for all shows that GREEDY also uses the minimum possible number of cliques. That is, it also computes the clique cover number of a cograph.
A clique-partition linear program
The preceding majorization argument actually shows that the natural linear programming relaxation of CLIQUE PARTITION is exact on cographs. Recall that is the family of all nonempty cliques of , and that (LP) asks to maximize subject to and for every . If the vertex constraints are instead written as inequalities, their slack can be assigned to singleton cliques without changing the objective. The incidence vector of every clique partition is a feasible solution of (LP), so the optimal value of (LP) is always at least the maximum number of edges in a clique partition of . We say that (LP) is exact for if equality holds.
The feasible region of (LP) is not integral, even for cographs. Indeed, if with vertex set , then
and all other variables zero give a fractional feasible solution. The three positive columns form the matrix
whose determinant is . Thus, this solution is a basic feasible solution. However, we will show that (LP) always has an optimal solution that is -valued when is a cograph.
To prove this statement, we extend majorization to fractional clique partitions. A weighted size profile is a finite family
Let be the decreasing step function in which the value occupies an interval of length , padded by zeros, and define
Equivalently, is the maximum total size obtainable by taking total weight from , allowing a fractional amount of an entry.
Every feasible solution of (LP) has the weighted size profile
The covering constraints imply
Lemma 4.5. Let be a cograph, let be a clique partition output by GREEDY, and let be its clique sizes, padded by zeros. For every feasible solution of (LP) and every ,
where is the step function that takes the value on the interval .
Proof. We proceed by induction on . The claim is immediate when . Choose a nontrivial cograph decomposition as in Lemma 4.1.
First suppose that . Every clique is contained in one side, so is the union of feasible fractional profiles and for the two sides. The restriction of the greedy run to each side is a greedy run; denote its profiles by and . By induction, for every ,
where is the nonincreasing merge of and .
Now suppose that . For every clique of , put and . Using weight on the entries and gives feasible fractional profiles and on the two sides; zero entries may simply be retained. For any choice of total weight , the contribution of the entries is at most the sum of the largest entries from the two component profiles. Hence,
There are greedy profiles and , padded by zeros, such that the greedy profile of the join satisfies
Since both component profiles are nonincreasing, induction gives
This completes the induction.
We are now ready to prove Theorem 1.2.
Proof of Theorem 1.2. Let be any feasible solution, and let be a clique partition output by GREEDY, with size sequence . By Equation (2) and Lemma 4.5, the profile majorizes the weighted profile , and both profiles have total size . The weighted form of Karamata’s inequality (see [27]), applied to the convex function , therefore gives
The incidence vector of is a feasible integral solution of (LP). It is therefore at least as good as every fractional solution, and hence is optimal.
We conclude this section by showing that Theorem 1.2 does not extend to permutation graphs. We used Claude Fable 5.1 to find this example, and to verify by exhaustive computer search that it is the smallest such example.
Proposition 4.6. Let and let be the corresponding permutation graph, depicted in Figure 1. Then the optimal value of (LP) for is , whereas every clique partition of has at most 16 edges.

Figure 1. The permutation graph of , for which (LP) is not exact.
Proof. Recall that the cliques of are the decreasing subsequences of . One checks directly that the maximal cliques of are
and that has 28 edges. Equivalently, is obtained from the complete graph on by deleting the edge and adding two vertices 4 and 5, where 5 is adjacent to 1, 2, 3, 4 and 4 is adjacent to 5, 6, 7, 8, 9. In particular, , and the only 6-cliques are the first two sets above.
Assign to each of the five cliques
and to all other cliques. Every vertex is covered exactly once, so is feasible for (LP), and its objective value is . On the other hand, the dual of (LP) asks to minimize subject to
for every . The vector with
is dual feasible. Indeed, every clique of is contained in one of the five maximal cliques listed above, so it suffices to check that for each such and each , the sum of the smallest values () is at least . For and , the values in nondecreasing order are $1/2,2,2,3,3,9/2$, with partial sums ; for they are , with partial sums ; for $Q={1,2,3,5} they are , with partial sums ; and for the partial sums are . In each case the -th partial sum is at least . Since , linear programming duality shows that the optimal value of (LP) is exactly .
Finally, let be a clique partition of with part sizes . Since and , a direct enumeration of the partitions of 9 into parts of size at most 6 shows that forces , that is, consists of a 6-clique and a disjoint triangle. However, and are not cliques. Hence , and the clique partition shows that this bound is attained.
By Theorem 1.3 below, the failure of exactness on permutation graphs is not an accident. The dual of (LP) can be solved in polynomial time on permutation graphs as follows. Since the cliques of of size are the decreasing subsequences of of length , a minimum -weight clique of each size can be found by dynamic programming, which yields a polynomial-time separation oracle. Thus, (LP) can be solved in polynomial time via the ellipsoid method [20]. Consequently, if (LP) were exact for all permutation graphs, then the optimal value of CLIQUE PARTITION on permutation graphs could be computed in polynomial time, which by Theorem 1.3 is impossible unless .
Cluster deletion in permutation graphs is NP-complete
In this section, we prove Theorem 1.3, which resolves an open problem of Konstantinidis and Papadopoulos [25]. As explained in the introduction, the decision versions of CLIQUE PARTITION and CLUSTER DELETION are equivalent and belong to , so it suffices to show that CLIQUE PARTITION is NP-hard on permutation graphs.
We give a polynomial reduction from the OPTIMUM COST CHROMATIC PARTITION (OCCP) problem.
OPTIMUM COST CHROMATIC PARTITION:
Input: A graph with vertices and nonnegative integers .
Output: A partition of into stable sets of (some of which may be empty) such that is minimum.
In other words, color has cost , and OCCP asks for a proper coloring of of minimum total cost; since has only vertices, allowing colors is not a restriction. We call a partition of into stable sets a coloring of . In the decision version of OCCP, we are additionally given an integer , and the question is whether has a coloring of cost at most . Jansen [23] proved that OCCP is NP-complete on permutation graphs. Moreover, in the instances constructed in his hardness proof, the costs are bounded by a polynomial in (see [23 Section 4]). We only use this restricted form of Jansen’s result.
Theorem 5.1 (Jansen [23]). There is a constant such that the decision version of OCCP is NP-hard when restricted to instances in which is a permutation graph and .
Scores
It is convenient to measure clique partitions by a slightly different quantity than the number of edges. For a clique partition of a graph , we define the score of to be
Since , we have
Thus, maximizing is the same as maximizing , and for every integer , has a clique partition with at least edges if and only if has a clique partition of score at least .
The construction
Fix an instance of OCCP, where is a graph with vertex set of size , and are nonnegative integers. Put
Note that . Let be pairwise disjoint sets of vertices, disjoint from , with for all , and let
where denotes the complete graph with vertex set . Explicitly, ; two vertices of are adjacent in if and only if they are nonadjacent in ; every vertex of is adjacent to every vertex of ; each is a clique of ; and there are no edges between and for . Finally, put
We record two simple observations. First, since there are no edges between distinct sets and , and since the cliques of are the stable sets of , we have the following description of the cliques of .
Fact 5.2. The cliques of are exactly the sets of the form , where for some and is a stable set of . In particular, no clique of meets two of the sets .
Second, . Hence, if , then and , so can be constructed in time polynomial in .
For a coloring of , we define
Lemma 5.3. For every coloring of , is a clique partition of , and
Proof. Each is a clique of by Fact 5.2, and these sets partition . Using , we compute
The next lemma shows that, as far as maximum scores are concerned, we may restrict our attention to clique partitions of the form .
Lemma 5.4. Let be a clique partition of of maximum score. Then for some coloring of . Consequently, for every clique partition of there is a coloring of with .
Proof. We first show that each is contained in a single part of . Suppose not, and let and be distinct parts of that both meet . By Fact 5.2, and , where and are disjoint nonempty subsets of , and are stable sets of . By symmetry, we may assume that . Let be obtained from by replacing and by and (and discarding if it is empty). By Fact 5.2, is a clique of , so is a clique partition of , and
since , and . This contradicts the maximality of .
Hence, for each there is a unique part of containing , and by Fact 5.2 we can write with a stable set of . The parts are distinct, since by Fact 5.2 no clique of meets two of the sets , and every other part of is a nonempty subset of . Suppose that there is such a part . Then , so for some , that is, . By Fact 5.2, is a clique of , and replacing the two parts and by the single part increases the score by , again contradicting the maximality of .
Therefore, , where is a coloring of . The last assertion follows since a clique partition of maximum score exists.
We are now ready to establish the correctness of the reduction.
Theorem 5.5. has a coloring of cost at most if and only if has a clique partition of score at least .
Proof. Suppose first that is a coloring of with . By Lemma 5.3,
Conversely, suppose that has a clique partition of score at least . By Lemma 5.4, there is a coloring of with . By Lemma 5.3,
Since and are integers, it follows that .
The same computation shows that the reduction maps optimal solutions to optimal solutions. Indeed, let be a clique partition of of maximum score. By Lemma 5.4, for some coloring of , and if some coloring of had , then Lemma 5.3 would give , a contradiction. Thus, is a minimum cost coloring of (in fact, one maximizing among all minimum cost colorings).
Preserving permutation graphs
It remains to show that the reduction preserves the property of being a permutation graph. This also follows from the facts that the class of permutation graphs is closed under complementation, disjoint unions and joins (see [18]), but we give an explicit permutation.
Lemma 5.6. If is a permutation graph, then so is . Moreover, given a permutation with , a permutation with can be computed in time polynomial in .
Proof. We may assume that and for a permutation of . Put and for , so that and . Let be the following permutation of ,
written as a word:
That is, begins with the reverse of with all values shifted by , followed by decreasing runs, the -th of which consists of the values in . We identify the vertex with the value , and the set with the set of values in , and claim that under this identification . Recall that two values are adjacent in if and only if the smaller value appears later in the word .
Let be vertices of . Then appears later than in if and only if appears earlier than in , that is, if and only if and are nonadjacent in . Hence .
Let and . Then and appears later than in , so and are adjacent in .
Let be values in . If for some , then appears later than (the -th run is decreasing), so and are adjacent. If and with , then , and appears earlier than , so and are nonadjacent.
Therefore, . Clearly, can be written down in time polynomial in .
We can now complete the proof of Theorem 1.3.
Proof of Theorem 1.3. As noted above, the decision versions of CLIQUE PARTITION and CLUSTER DELETION are in NP and are polynomially equivalent, so it suffices to show that CLIQUE PARTITION is NP-hard on permutation graphs. Let be an instance of OCCP with a permutation graph and , where is the constant from Theorem 5.1. Construct the graph and the integer as in (4), and put . A permutation with can be found in linear time [28], so since , Lemma 5.6 shows that the permutation graph (together with a permutation representing it) can be computed in polynomial time. By Theorem 5.5 and (3), has a coloring of cost at most if and only if has a clique partition with at least edges. By Theorem 5.1, CLIQUE PARTITION is NP-hard on permutation graphs.
Since the permutation graphs are precisely the graphs that are simultaneously comparability graphs and cocomparability graphs (see [18]), Theorem 1.3 immediately yields hardness for these two well-studied superclasses. Note that both classes contain natural subclasses on which CLUSTER DELETION is polynomial-time solvable. Bipartite graphs are comparability graphs (and on triangle-free graphs CLUSTER DELETION is just a maximum matching problem), while interval graphs are cocomparability graphs, and CLUSTER DELETION is polynomial-time solvable on interval graphs [6, 25].
Corollary 5.7. CLUSTER DELETION and CLIQUE PARTITION are NP-complete on comparability graphs and on cocomparability graphs.
An improved approximation algorithm
In this section we present an improved approximation algorithm for CLIQUE PARTITION. The description of the algorithm is simple. While the current graph has clique number at least 3, we compute a maximum clique , put into the clique partition, and delete . Once the remaining graph has clique number at most 2, an optimal clique partition consists of a maximum matching together with singleton cliques. We call the algorithm GREEDY EDMONDS.
Let be a graph, be a clique partition of , and . We let be the collection of nonempty sets of the form , where . Note that is a clique partition of . Recall that is the number of edges in a maximum clique of .
We now show that GREEDY EDMONDS is a -approximation algorithm for every graph . We first require the following lemma.
Input: A graph .
Output: A clique partition of .
Set .
While : choose a maximum clique of ; set and .
Compute a maximum matching of .
Add the edges of as two-vertex cliques and all uncovered vertices as singleton cliques.
Return .
Algorithm 2: GREEDY EDMONDS
Lemma 6.1. Let be a graph, be a clique partition of , , and be a subset of of size . If , then there exists an ordering of such that lies in a largest part of for all .
Proof. We proceed by induction on . The assertion is immediate for . Suppose , and let attain . We first show that contains a vertex in a largest part of . If it does not, choose and choose in a largest part of . Put and . In the partition , the part containing has its original maximum size, say , whereas the part containing has size at most . Deleting a vertex from a part of size removes exactly retained edges. Therefore,
contrary to the choice of .
Choose such a vertex , put , and let . The set minimizes among all -subsets ; otherwise, adjoining to a better set would contradict the minimality of . The induction hypothesis applied to gives an ordering with the required property. Prepending completes the proof.
Theorem 6.2. For every graph , GREEDY EDMONDS returns a clique partition such that
where is the number of edges in an optimal clique partition of .
Proof. We proceed by induction on . Put
and
Let . If , then GREEDY EDMONDS is optimal, so assume . Let be the partition returned by GREEDY EDMONDS, let be an optimal clique partition, and let and be the numbers of parts of size in and , respectively.
All cliques of size chosen by the algorithm occur before any smaller chosen clique. Let be their union, put , and set
Then , and is an output of GREEDY EDMONDS on . The induction hypothesis, together with the fact that decreases with , gives
For this uses , since has clique number at most 2 and the algorithm is optimal.
Choose an -element set minimizing . Since is also an -element set,
The set meets every part of of size ; otherwise that part would be an -clique in . In particular, . By Lemma 6.1, the vertices of can be removed successively from a currently largest part of . The first removals therefore meet distinct parts of size , and no part of size remains in .
If , then
and we are done. We may therefore let be the largest size of a part in the nonempty partition . Then .
The greedy deletion order supplied by Lemma 6.1 first reduces every original part of size greater than to size . This uses
vertices. The remaining deletions reduce of the resulting parts of size to size (when , they remove those singleton parts). Consequently,
This makes explicit the part sizes of determined by the deletion order supplied by Lemma 6.1.
By (5) and the choice of ,
Our goal is . Because , the terms with indices in (6) already have a sufficiently large coefficient. Thus, it is enough to prove
Since ,
Here we used . The coefficient is nonnegative: as a function of , its numerator is minimized at , where it equals .
It remains to check, for , that
Indeed, summing with weights gives (7). Clearing the positive denominator shows that the sign of is the sign of
For fixed , this is a concave quadratic in , because its leading coefficient is . Hence it suffices to check the endpoints and . Direct simplification gives
Moreover, , where
As a polynomial in , has positive leading coefficient and roots
For , we have , since
hence every lies at or to the left of both roots. For , we have , since
and ; so the open interval between the roots contains no integer. In either case, , and hence , for every integer . This proves and completes the induction.
Remark 6.3. By Theorem 1.3, GREEDY EDMONDS cannot compute an optimal clique partition of every permutation graph, unless . There are also small explicit examples. Let be the permutation graph of , depicted in Figure 2. The maximum cliques of are and . If GREEDY EDMONDS chooses in its first iteration, then the remaining graph has only the two edges and , so a maximum matching of it has one edge, and the algorithm outputs a clique partition with edges. However, the clique partition has 5 edges.
!Permutation graph of [2, 5, 4, 1, 7, 3, 6] bbox=0.36,0.06,0.63,0.15
Figure 2. The permutation graph of [2, 5, 4, 1, 7, 3, 6], on which GREEDY EDMONDS can return a nonoptimal clique partition.
We now give a family of graphs which shows that the approximation ratio from Theorem 6.2 is best possible. Moreover, the same family shows that the improved guarantee of Theorem 6.2 does not carry over to CLUSTER DELETION on these graphs.
Theorem 6.4. For every integer , there are infinitely many graphs with and clique partitions that can be output by GREEDY EDMONDS such that
where OPT is the maximum number of edges in a clique partition of , and is the minimum number of edges whose deletion turns into a cluster graph.
Proof. Fix , let , and let be any positive multiple of . Begin with pairwise disjoint row sets , each containing vertices. We recursively define disjoint sets . Put . As long as
choose to consist of vertices in distinct rows and put . Choose these vertices from the largest current rows, breaking ties so that, after deleting , the numbers of remaining vertices in the rows differ by at most one (this is possible since ). Let be the last index produced by this procedure.
Define on the vertices by making every row a clique, making every a clique, and adding no other edges. See Figure 3 for a depiction of .

Figure 3. The graph , with , , , , , . Vertices of the same (non-white) color form a clique in the graph.
We first record the clique structure of this graph. If a clique contains vertices from two different rows, then those two vertices must lie in a common . Since the sets are disjoint and each meets each row in at most one vertex, every other vertex of the clique must also lie in that same . Consequently, every clique of is contained in a row or in one of the sets . In particular,
After have been deleted, the remaining row sizes differ by at most one and have sum . Their maximum size is therefore . The future sets have nonincreasing sizes , and the preceding
::: clique-structure observation remains valid in the induced graph. Thus, is a maximum clique at iteration , and GREEDY EDMONDS can choose in that order.
At termination, . Just before the last deletion there were more than vertices, and , so . The remaining row sizes are therefore all 1 or 2. There are exactly rows of size 2, and a maximum matching in the remaining graph has edges. Hence this run of GREEDY EDMONDS outputs a partition with
The row partition shows that . The reverse inequality follows from . If a clique partition has part sizes , then
Therefore,
It remains to evaluate (8). This can be done exactly because is divisible by every . Initially . While decreases from to , we have . This phase consists of exactly steps, each deleting vertices. Inducting downwards from to shows that occurs exactly times and that . Therefore, (8) gives
Together with (9), this yields the exact equality
Finally, we count the deleted edges. The edge set of is the disjoint union of the edge sets of the row cliques and of the cliques , so by the computation above,
Hence, by (9), the minimum number of edges whose deletion turns into a cluster graph is
whereas the run of GREEDY EDMONDS above deletes
edges. There are infinitely many positive multiples of , so this gives infinitely many examples.
Since every run of GREEDY EDMONDS is also a run of GREEDY, Theorem 6.4 also shows that the factor 2 in Theorem 3.2 is best possible for GREEDY on graphs of any fixed clique number .
Proofs of the greedy approximation theorems
Proof of Theorem 3.1. Let be the sequence of cliques constructed by GREEDY, where is a maximum clique of . We proceed by induction on . If , then . Thus, we may assume . Let be an optimal clique partition of . Let , , , and be the number of edges in an optimal clique partition of . Let . For each vertex in , let be the unique cluster of such that . Define . Since is a maximum size clique of , for all . Therefore,
We also clearly have
By induction, . Since , the preceding two inequalities give , as required.
Proof of Theorem 3.2. Let be the sequence of cliques constructed by GREEDY, where is a maximum clique of . We induct on . The case is immediate. Let be an optimal clique partition, and put
omitting empty parts. Write for any clique partition . By induction,
Since is the disjoint union of and , it follows that
Let
Put and . Because every is a clique and is a maximum clique, , and hence
Here consists precisely of the edges of the clique whose ends lie in different parts of . Moreover, and are edge-disjoint subsets of : the former contains edges with both ends outside , while the latter contains edges with both ends inside . Using (10), we obtain
Funding
Tony Huynh is supported by the Institute for Basic Science (IBS-R029-C1). Nicola Galesi was partly supported by PRIN 2022 project "Logical methods in combinatorics", 2022BXH4R5, MIUR (Italian Ministry of University and Research).
AI Declaration
The main ideas of the proof of Theorem 1.3 were found by ChatGPT 5.6 Sol. We remark that the ChatGPT proof of Theorem 1.3 contained some serious errors, and has been completely rewritten by the authors. The example in Proposition 4.6 was found by a computer search carried out with the assistance of Anthropic Claude. All other results in this paper were obtained by humans. OpenAI Codex and Anthropic Claude were also used for language editing, proof checking, and to search for additional references. After using these tools, the authors reviewed and edited the content as needed and take full responsibility for the content of the article.
References
References
- [1]Aprile, M., Drescher, M., Fiorini, S., Huynh, T., 2023. A tight approximation algorithm for the cluster vertex deletion problem. Math. Program. 197, 1069–1091. URL: https://doi.org/10.1007/s10107-021-01744-w, doi:10.1007/s10107-021-01744-w.
- [2]Balmaseda, V., Xu, Y., Cao, Y., Veldt, N., 2024. Combinatorial approximations for cluster deletion: Simpler, faster, and better, in: Proceedings of the 41st International Conference on Machine Learning, pp. 2586–2606.arxiv.org/abs/2404.16131
- [3]Bansal, N., Blum, A., Chawla, S., 2004. Correlation clustering. Mach. Learn. 56, 89–113. URL: https://doi.org/10.1023/B:MACH.0000033116.57574.95, doi:10.1023/B:MACH.0000033116.57574.95.
- [4]Bathie, G., Bousquet, N., Cao, Y., Ke, Y., Perron, T., 2022. (sub)linear kernels for edge modification problems toward structured graph classes. Algorithmica 84, 3338–3364. URL: https://doi.org/10.1007/s00453-022-00969-1, doi:10.1007/s00453-022-00969-1.
- [5]Ben-Dor, A., Shamir, R., Yakhini, Z., 1999. Clustering gene expression patterns. J. Comput. Biol. 6, 281–297. URL: https://doi.org/10.1089/106652999318274, doi:10.1089/106652999318274.
- [6]Bonomo, F., Durán, G., Valencia-Pabon, M., 2015. Complexity of the cluster deletion problem on subclasses of chordal graphs. Theor. Comput. Sci. 600, 59–69. doi:https://doi.org/10.1016/j.tcs.2015.07.001.
- [7]Böcker, S., Damaschke, P., 2011. Even faster parameterized cluster deletion and cluster editing. Inf. Process. Lett. 111, 717–721. doi:https://doi.org/10.1016/j.ipl.2011.05.003.
- [8]Charikar, M., Guruswami, V., Wirth, A., 2005. Clustering with qualitative information. J. Comput. Syst. Sci. 71, 360–383. doi:https://doi.org/10.1016/j.jcss.2004.10.012.
- [9]Damaschke, P., 2009. Bounded-degree techniques accelerate some parameterized graph algorithms, in: Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, pp. 98–109.DOI
- [10]Dessmark, A., Jansson, J., Lingas, A., Lundell, E.M., Person, M., 2007. On the approximability of maximum and minimum edge clique partition problems. Int. J. Found. Comput. Sci. 18, 217–226. URL: https://doi.org/10.1142/S0129054107004656, doi:10.1142/S0129054107004656.
- [11]Diestel, R., [2025] ©2025. Graph theory. volume 173 of Graduate Texts in Mathematics. Sixth ed., Springer, Berlin.
- [12]Edmonds, J., 1965. Paths, trees, and flowers. Can. J. Math. 17, 449–467. doi:10.4153/CJM-1965-045-4.DOI
- [13]Even, S., Pnueli, A., Lempel, A., 1972. Permutation graphs and transitive graphs. J. ACM 19, 400–410. URL: https://doi.org/10.1145/321707.321710, doi:10.1145/321707.321710.
- [14]Fortunato, S., 2010. Community detection in graphs. Phys. Rep. 486, 75–174. doi:https://doi.org/10.1016/j.physrep.2009.11.002.
- [15]Fredman, M.L., 1975. On computing the length of longest increasing subsequences. Discrete Math. 11, 29–35. doi:10.1016/0012-365X(75)90103-X.DOI
- [16]Gao, Y., Hare, D.R., Nastos, J., 2013. The cluster deletion problem for cographs. Discrete Math. 313, 2763–2771. URL: https://doi.org/10.1016/j.disc.2013.08.017, doi:10.1016/j.disc.2013.08.017.
- [17]Golovach, P.A., Heggernes, P., Konstantinidis, A.L., Lima, P.T., Papadopoulos, C., 2018. Parameterized Aspects of Strong Subgraph Closure, in: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), pp. 23:1–23:13. doi:10.4230/LIPIcs.SWAT.2018.23.arxiv.org/abs/1802.10386
- [18]Golumbic, M.C., 2004. Algorithmic graph theory and perfect graphs. volume 57. Elsevier.
- [19]Gramm, J., Guo, J., Hüffner, F., Niedermeier, R., 2005. Graph-modeled data clustering: Exact algorithms for clique generation. Theory Comput. Syst. 38, 373–392. URL: https://doi.org/10.1007/s00224-004-1178-y, doi:10.1007/s00224-004-1178-y.
- [20]Grötschel, M., Lovász, L., Schrijver, A., 1993. Geometric Algorithms and Combinatorial Optimization. volume 2 of Algorithms and Combinatorics. Second ed., Springer-Verlag, Berlin. doi:10.1007/978-3-642-78240-4.DOI
- [21]Grüttemeier, N., Komusiewicz, C., 2020. On the relation of strong triadic closure and cluster deletion. Algorithmica 82, 853–880. doi:https://doi.org/10.1007/s00453-019-00617-1.
- [22]Italiano, G.F., Konstantinidis, A.L., Papadopoulos, C., 2025. Structural parameterization of cluster deletion. Algorithmica 87, 961–981. doi:10.1007/s00453-025-01303-1.DOI
- [23]Jansen, K., 2000. Approximation results for the optimum cost chromatic partition problem. Journal of Algorithms 34, 54–89. URL: https://www.sciencedirect.com/science/article/pii/S0196677499010222, doi:https://doi.org/10.1006/jagm.1999.1022.
- [24]Komusiewicz, C., Uhlmann, J., 2012. Cluster editing with locally bounded modifications. Discrete Appl. Math. 160, 2259–2270. doi:https://doi.org/10.1016/j.dam.2012.05.019.
- [25]Konstantinidis, A.L., Papadopoulos, C., 2021. Cluster deletion on interval graphs and split related graphs. Algorithmica 83, 2018–2046. doi:10.1007/s00453-021-00817-8.DOI
- [26]Li, P., Puleo, G., Milenkovic, O., 2020. Motif and hypergraph correlation clustering. IEEE Trans. Inf. Theory 66, 3065–3078. doi:10.1109/TIT.2019.2940246.DOI
- [27]Marshall, A.W., Olkin, I., Arnold, B.C., 2011. Inequalities: Theory of Majorization and its Applications. Springer Series in Statistics. second ed., Springer, New York. doi:10.1007/978-0-387-68276-1.DOI
- [28]McConnell, R.M., Spinrad, J.P., 1999. Modular decomposition and transitive orientation. Discrete Math. 201, 189–241. doi:10.1016/S0012-365X(98)00319-7.DOI
- [29]Pnueli, A., Lempel, A., Even, S., 1971. Transitive orientation of graphs and identification of permutation graphs. Can. J. Math. 23, 160–175. doi:10.4153/CJM-1971-016-5.DOI
- [30]Puleo, G.J., Milenkovic, O., 2015. Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J. Optim. 25, 1857–1872. URL: https://doi.org/10.1137/140994198, doi:10.1137/140994198.
- [31]Rhee, C., Liang, Y.D., 1995. Finding a maximum matching in a permutation graph. Acta Inform. 32, 779–792. URL: https://doi.org/10.1007/s002360050033, doi:10.1007/s002360050033.
- [32]Shamir, R., Sharan, R., Tsur, D., 2004. Cluster graph modification problems. Discrete Appl. Math. 144, 173–182. doi:https://doi.org/10.1016/j.dam.2004.01.007.
- [33]Shi, J., Malik, J., 2000. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905. doi:10.1109/34.868688.DOI
- [34]Sintos, S., Tsaparas, P., 2014. Using strong triadic closure to characterize ties in social networks, in: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1466–1475. doi:10.1145/2623330.2623664.DOI
- [35]Veldt, N., 2022. Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds, in: Proceedings of the 39th International Conference on Machine Learning, pp. 22060–22083.arxiv.org/abs/2111.10699
- [36]Veldt, N., Gleich, D.F., Wirth, A., 2018. A correlation clustering framework for community detection, in: Proceedings of the 2018 World Wide Web Conference, pp. 439–448. doi:10.1145/3178876.3186110.DOI