WorksComputer Science
Improved approximation algorithms for capacitated cluster editing
Abstract
We study the minimum-disagreement cluster editing problem that, from a complete edge-signed graph, where a positive edge represents two vertices agreeing to each other while a negative represents a disagreement, constructs disjoint cliques of upper bounded size such that the total number of negative edges inside cliques and positive edges outside cliques is minimized. When the sizes of the candidate cliques are unbounded, the problem is NP-hard and APX-hard, and many approximation algorithms with improving ratios have been proposed in the literature and the state-of-the-art approximation ratio of . The capacitated variant, in which the candidate cliques have sizes no greater than a given , is less studied and the best approximation ratio is . In this paper, we study the latter problem. We first present a downsizing procedure that achieves an approximation ratio of , based on any -approximation algorithm for the uncapacitated problem. Secondly, we propose a hybrid of cluster-LP sampling and pivoting and show that for every fractional capacitated cluster-LP solution of cost , the hybrid using ordinary pivoting has an expected cost at most \frac 95 L + \frac 1{10} \OPT_k, and the hybrid using conditional pivoting has an expected cost at most \frac {306}{203} L + \frac {50}{203} \OPT_k. A cardinality-constrained adaptation of the approximate dual-separation framework of García-Soriano and Schohn supplies the required fractional solution and yields a randomized -approximation algorithm and a randomized -approximation algorithm, respectively.
Acknowledgments
The research is supported by the NNSF of China (Grants 12471301, 61972329), the China Scholarship Council (Grant No. 202508330173), the GRF grants for Hong Kong Special Administrative Region, China (Grant Nos. CityU 11218423, CityU 11219825), and the NSERC Canada.
Introduction
Correlation clustering, introduced by Bansal et al. [2], constructs a partition from pairwise similarity and dissimilarity information. In the complete unweighted form, every pair of vertices is labelled positive or negative. The objective is to form a partition of the vertices, in which a part is called a cluster, to minimize the number of positive edges between clusters and negative edges within clusters. Equivalently, one seeks to transform the graph of positive edges only into a disjoint union of cliques using as few edge insertions and deletions as possible. Such a formulation is also known as Cluster Editing, which is an NP-hard [25] and APX-hard [10] problem.
We study Capacitated Cluster Editing, in which each candidate cluster contains no more than vertices, where is part of the input and is referred to as the cluster capacity. The problem remains NP-hard for every fixed [20]. On the approximation algorithms, Puleo and Milenkovic [24] developed an algorithm based on a linear program and combinatorial methods, including two proven 7- and 6-approximation algorithms. Il’ev et al. [19] established the APX-completeness for each fixed capacity, with an approximation ratio depending on that capacity. Later, Ji et al. [21] improved the approximation ratio to 5.37, independent on the capacity, based on a linear program formulation and rounding to construct size-bounded clusters. Kononov and Il’ev [23] further obtained better ratios of for and for . In this paper, we aim to design approximation algorithms with improved ratios when is part of the input.
The problem introduced by Bansal et al. [2] is uncapacitated, i.e., a candidate cluster can have arbitrary size. Bansal et al. [2] had presented a constant ratio approximation algorithm, with the ratio being at most . Recent progress for the uncapacitated problem has been driven by the Cluster linear program, which represents a fractional partition by assigning weights to all candidate clusters [7, 17]. The same representation can employed for capacitated variant, and in fact it makes an upper bound on cluster size easy to encode, but subsequently rounding poses a further difficulty. Basically, from a fractional solution, sampling the clusters preserves the size bound, whereas pivoting can create oversized clusters; for the latter oversized clusters, the feasibility can be restored by downsizing which however may increase the disagreement cost. Obtaining strong guarantees therefore requires incorporating downsizing into the rounding analysis.
Our results
We first propose a simple downsizing procedure that converts any uncapacitated partition into a feasible capacitated partition denoted as having a disagreement cost at most twice of plus an optimum. This gives rise to a -approximation algorithm based on the state-of-the-art -approximation for the uncapacitated Cluster Editing problem.
Next, realizing that we can extend the uncapacitated Cluster-LP to capacitated Cluster-LP to achieve a fractional solution of cost arbitrarily close to the optimum, we propose to combine the cluster sampling approach of Cao et al. [7] to obtain a feasible solution , and the ordinary pivot method introduced by Ailon et al. [1] to obtain another uncapacitated solution , so that the better solution between and is a -approximation.
Lastly, we propose to employ the conditional-affine pivoting framework of García-Soriano and Schohn [17] with different vertex admission probabilities for positive neighbors inside the seed, positive neighbors outside the seed, and negative neighbors. Coupling with a weighted disagreement cost analysis, which calculates more accurately the edge errors and thus estimates slightly better than the downsizing argument, we are able to show that the new pivoting method performs better than the ordinary pivoting, and the better solution between and is a -approximation.
Theorem 1 For every fixed rational , the Capacitated Cluster Editing problem admits a randomized expected -approximation algorithm that runs in an expected polynomial time in the input size , bounded by in which the exponent does not depend on the capacity , times a polynomial in the precision encoding length.
Note that . Our main contribution is to combine the rounding methods proposed in the literature with the downsizing procedure and analyze their costs jointly. The improvement from the first pivoting method to the second comes from a better bound on the edge errors together with a weighted disagreement cost analysis.
Related work
Approximation algorithms for uncapacitated correlation clustering have evolved through increasingly expressive linear program (LP) relaxations and rounding procedures. Improving upon Bansal et al. [2]’s large constant ratio, Charikar et al. [10] gave a 4-approximation using LP rounding and region growing. Ailon et al. [1] introduced randomized pivoting method, which repeatedly groups a random unclustered vertex with its positive neighbors, obtaining a 3-approximation. Furthermore, their LP-dependent rounding achieves a ratio of 2.5. Van Zuylen and Williamson [26] also presented deterministic pivoting algorithms with the same two guarantees. Afterwards, Chawla et al. [11] refined the LP-based rounding probabilities in [1] to obtain an improved ratio slightly below 2.06. It is proven that the underlying metric LP using pairwise separation variables constrained by triangle inequalities has an integrality gap lower bound of 2 [10, 11].
In the past few years, uncapacitated correlation clustering has experienced another wave of advancement, mostly stronger relaxations retaining correlations among several clustering decisions. Cohen-Addad et al. [14] combined the Sherali-Adams hierarchy with correlated rounding and a global charging argument to obtain a ()-approximation algorithm. Cohen-Addad et al. [13] introduced pre-clustering, which identifies groups of vertices to be kept together and restricts those pairs to share a cluster; the proposed structure controls correlated-rounding errors and supports a combination of set-based and pivot-based rounding with a guarantee of .
The cluster LP of Cao et al. [7] brings the above ideas into a single relaxation over all candidate clusters, by setting up whole-cluster variables to retain joint membership information beyond pairwise distances. Their fractional partition construction uses pre-clustering and sampling to obtain an explicit feasible solution to the cluster LP of value no more than a fraction of the integral optimum. Subsequently, correlated rounding errors are handled so that the final rounding can work directly with the resulting cluster weights. Combining cluster sampling with LP-dependent pivoting gives a ()-approximation algorithm in their extended full paper [8].
Soon after, García-Soriano and Schohn [17] improved both the computation and the rounding of the cluster LP. Their approximate dual-separation algorithm uses localization and weak regularity to search for violated dual constraints, yielding approximate primal and dual solutions relative to the fractional cluster-LP optimum. Their rounding couples cluster sampling with a conditional affine pivot rule, which uses membership in a sampled cluster to coordinate inclusion around the selected pivot. A variance-based analysis and derandomization yield a deterministic ()-approximation. This second wave of developments supply the cluster LP optimization framework and rounding procedures that we adapt to for our capacitated Cluster Editing.
Besides the above mentioned constant-ratio approximation algorithms for the capacitated Cluster Editing [24, 19, 21, 23], Ji et al. [22] consider a variant in which vertex-specific bounds are imposed on the size of the cluster containing each vertex, i.e., non-uniform capacity constraints, and they presented a bicriteria algorithm achieving a cost at most 4 times the optimum while allowing a factor-2 violation of these bounds. In this paper, we study the problem with prescribed uniform capacity.
Cluster Editing has also been studied from the perspectives of exact and parameterized algorithms. For example, the problem can be parameterized by the edit-cost budget, which has received substantial studies [4, 18, 15, 6, 9, 12], and by jointly the edit-cost budget and the number of output clusters [16]. Practical approaches for uncapacitated Cluster Editing include those that combine data reduction with exact branching and integer programming [5], and that integrate exact optimization with greedy randomized adaptive search and iterated-local-search heuristics [3].
Organization of the paper
In the next section, we introduce a set of terminologies and notations to be used in the rest of the paper, as well as the capacitated Cluster LP formulation. The downsizing procedure is presented in Section 3, followed by what it implies — our first -approximation algorithm building on the state-of-the-art algorithm for uncapacitated problem. In Section 4, we employ the near optimal fractional solution to the Cluster LP, which can be computed in polynomial time, and combine the rounding through sampling by Cao et al. [7] and the ordinary pivoting method by Ailon et al. [1], together with the downsizing procedure, to design an improved approximation algorithm with ratio of . We then replace the ordinary pivoting method by the conditional affine pivoting rule of García-Soriano and Schohn [17] to construct another uncapacitated partition dependent on the fractional solution to the Cluster LP, again together with the downsizing procedure, leading to a further improved -approximation algorithm, where . These results are presented in Section 5. We conclude the paper in Section 6.
Preliminaries
In this paper, we study the Cluster Editing problem. An instance of the problem consists of a complete edge-signed graph , where an edge is called a positive edge or otherwise a *negative edge, and a positive integer when the problem is capacitated or otherwise when the problem is uncapacitated. A partition of the vertex set is a collection of disjoint nonempty subsets (called parts or clusters, used interchangeably) whose union is . For the uncapacitated variant there is no constraint on the size of a part in the partition; for the capacitated variant, every part must have size at most for the partition to be feasible (called -feasible). This parameter is referred to as the (uniform) capacity of the clusters. Note that there is no requirement on the number of parts in a partition.
For a feasible partition , the edge set of is denoted as , which contains all the (positive and negative) edges in the complete subgraphs (called cliques) induced by the parts of , i.e., those edges such that lie in the same part of . The disagreement cost of is
which is the edit distance from the positive edge set to , by deleting certain edges of and inserting certain edges of . The goal of the Cluster Editing problem is to find a feasible partition that minimizes the cost. We use and to denote the optimal (i.e., minimum) cost for the -capacitated and the uncapacitated variants, respectively. One sees that .
In general, for two edge subsets and , their symmetric difference is , and their edit distance is . One sees that is a metric.
Below we give another view for the disagreement cost of a partition . For two disjoint vertex subsets and , let count the number of positive edges with one endpoint in each set; let and count the number of positive and negative edges in the clique induced on , respectively. The cost of using a vertex subset as a part in a partition is
in which represents the number of insertions due to and the number of deletions. Note that the other half of the deletions is attributed to the parts containing the other endpoints of the edges of . This way, we have .
For a vertex , if then is a positive neighbor of ; the positive neighborhood of is containing all its positive neighbors, the closed positive neighborhood of is , and the positive degree of in a vertex subset is . We write .
The capacitated cluster linear program
Let , i.e., all the non-empty vertex subsets of size up to . For any pair of distinct vertices , we denote , i.e., the collection of all subsets in containing both vertices. We also denote for any vertex . Using the definition of cluster cost in (2), we set up a binary variable for including as a part in the partition, followed by the capacitated cluster relaxed linear program (abbreviated as Cluster-LP):
Here, is called the coverage equality for the vertex . As denotes the optimal disagreement for the Cluster-LP, we have .
Given a feasible solution to the Cluster-LP, we define for each edge ,
The vertex coverage equalities imply , and hence too. For a positive edge , the total disagreement across all the clusters containing exactly one endpoint is ; therefore, by Eq. (2) this edge contributes to the objective. Similarly, for a negative edge , the total disagreement across all the clusters containing both endpoints is . It follows that the objective function value of the solution can be written in three ways as
For any three distinct vertices , and , since and for all , we have , and consequently the triangle inequality holds for
A downsizing theorem
Given a partition , we want to downsize every part of size greater than to convert it into a -feasible solution to the capacitated problem. We do this by splitting each part of size , where and , into subsets of size exactly and a subset of size if . Note that there is no requirement on co-memberships for any vertices during the splitting. The achieved partition through such a procedure is denoted as .
Lemma 1 Given a partition , for any -feasible partition .
Proof. We use the -feasible partition to intersect the parts of to obtain a common refinement denoted as . In more details, let be a part of and be a part of ; then becomes a part in the refinement if it is non-empty. is -feasible and its edge set . It follows that
It thus suffices to prove the lemma for only the refinements of , and furthermore independently for each part of .
Let be a part of . If a -feasible refinement of contains two subsets of sizes , then transferring them into a subset of size and, when , another of size , gives rise to a better refinement reducing the distance by . Repeating such a process leads to the -feasible partition . This proves the lemma. □
Theorem 2 (Downsizing). For every partition of the complete edge-signed graph , . Hence a polynomial-time -approximation algorithm for the uncapacitated cluster editing problem yields a polynomial-time -approximation algorithm for the capacitated problem. The same implication holds for performance guarantees in expectation.
Proof. Let be an optimal -feasible partition for the cluster editing problem with capacity and . By Eq. (1), the triangle inequality for the edge set edit distance and Lemma 1, we have
If the performance guarantees are expected, i.e., , then taking expectations and using proves the theorem.
For the running time, one sees that obtaining from can be done in time. □
Corollary 1. For every fixed , the approximation algorithm of García-Soriano and Schohn [17] for the uncapacitated cluster editing problem together with the downsizing procedure gives a -approximation algorithm for the capacitated problem.
Proof. The algorithm of García-Soriano and Schohn [17 Corollary 1.4] can be set to have an approximation ratio of , and runs in time. The resulting algorithm, by Theorem 2, has an approximation ratio of . □
An improved approximation algorithm
Let be the collection of all non-empty subsets of . Replacing in the Cluster-LP in Eq. (3) by becomes the Cluster-LP for the uncapacitated cluster editing problem, which is employed in the works by Cao et al. [7] and García-Soriano and Schohn [17] that contain the state-of-the-art approximation algorithms. Most notably, it is shown that for any rational , one can deterministically compute a feasible solution to the Cluster-LP in time times a polynomial in the precision encoding length, such that has at most positive values all of polynomial encoding length and .
One sees that by setting for each in the Cluster-LP for the uncapacitated cluster editing problem, it reduces to the Cluster-LP in Eq. (3) for the capacitated problem. Therefore, we can use the conclusion for the uncapacitated problem and summarize it in the below theorem.
Theorem 3 (Approximate fractional solution). Given a complete edge-signed graph , an input capacity , and a rational , one can deterministically compute a feasible solution to the Cluster-LP in Eq. (3) in time times a polynomial in the precision encoding length, such that has at most positive values all of polynomial encoding length and .
In the rest of the section, we present a hybrid rounding algorithm for , in Algorithm 1, and prove the rounding guarantee independently of the LP solver for obtaining . Inside the algorithm is used for constructing two partitions.
A high-level description of the algorithm is depicted in Algorithm 1, which constructs two candidate partitions and returns the better one as the final solution. Lines 1–6 constitute the first sampling branch that generates a candidate -feasible partition , which is initialized empty at the beginning. In each iteration, let denote the un-clustered vertices, and denote the collection of subsets such that and contains at least one un-clustered vertex; then each of is selected with probability proportional to its value and then is added to . The branch repeats until every vertex is in a cluster of . Lines 7–11 constitute the second branch that is the ordinary pivot algorithm by Ailon et al. [1]. It generates an uncapacitated partition , which is initialized empty at the beginning. In each iteration, let denote the un-clustered vertices; each vertex is selected uniformly at random as the pivot to form a cluster , i.e., containing and all its positive un-clustered neighbors. The branch repeats until every vertex is in a cluster of , of which is the generated candidate -feasible partition.
| Algorithm 1 | Hybrid rounding a fractional solution. |
| Require: | , , a feasible solution to Cluster-LP in Eq. (3); |
| Ensure: | a partition for . |
| 1: | , ; |
| ▷ Sampling branch; | |
| 2: | while do |
| 3: | and ; |
| 4: | choose with probability ; |
| 5: | add to and update ; |
| 6: | end while |
| 7: | , ; |
| ▷ Ordinary pivoting branch; | |
| 8: | while do |
| 9: | choose with probability ; |
| 10: | add to and update ; |
| 11: | end while |
| 12: | return . |
Table 1.
One sees that either branch has at most iterations, and the -feasibility of the partition is guaranteed. The overall running time of Algorithm 1 is in , using independent random bits in the iterations.
The performance analysis
Recall in Eq. (4) that we define for each edge , where is the collection of subsets of each containing both end-vertices . With respect to the fractional solution , we call the total weight of the clusters containing both end-vertices, and call the total weight of the clusters containing exactly one of the two end-vertices. When we fix the edge for discussion below, we denote . In a -feasible partition, we say are together if they are in the same cluster of the partition, or otherwise separated. The next lemma on the partition produced in the first branch of Algorithm 1 is analogous to the pairwise sampling principle of Cao et al. [7].
Lemma 2 In the partition produced in the first branch of Algorithm 1, for every pair of vertices ,
Proof. Note that are together or separated in is independent of the cluster construction history before any of or is clustered, at that time point every subset of containing either of them still intersects the current un-clustered vertex set , and thus has not changed. That is, for any history the probabilities that the next selected cluster contains both and , or only , or only are , , , respectively. It follows that the probabilities conditioned on one of them being clustered are , , and , respectively, independent of the history. If the selected subset contains both and , then they are in the same cluster . If contains exactly one of and , then that vertex is in while the other vertex appears in a different cluster, i.e., and are separated. This proves the lemma.
Recall that for each positive edge , it contributes towards the objective in the fractional solution . By Lemma 2, we define the slack of the edge , denoted as , as the difference between twice of its contribution towards the objective in the fractional solution , , and its expected contribution towards the objective in the partition , . That is, . Analogously, we can define the slack for a negative edge. We have
and is called the total slack, which measures exactly the total improvement of the partition over the bound and is summarized in the next lemma. One sees that every edge slack is nonnegative.
Lemma 3 For the partition produced in the first branch of Algorithm 1, .
Proof. For each edge , its slack is defined as the difference between twice of its contribution towards the objective in the fractional solution and its expected contribution towards the objective in the partition . Summing over all edges gives , and thus proves the lemma. □
We next use the total slack to bound the disagreement cost of produced in the second branch of Algorithm 1. Noting that for the selected pivot in an iteration and a positive neighbor , bringing in another positive neighbor into the cluster has the risk of introducing an error negative edge ; while not bringing in a negative neighbor into the cluster also has the risk of introducing an error positive edge . Both scenarios involve a bad triangle, which has exactly two positive edges and one negative edge, and plays an important role in the performance analysis.
Lemma 4 For every bad triangle , , where is the edge set of .
Proof. Assume the three vertices in are , , , and is a negative edge. Let , denote the two values and for the positive edges and . By the triangle inequality for in Eq. (5), .
The slack function for positive edges is nondecreasing and convex in , since
Therefore, . It follows that
where the last inequality holds due to . □
Lemma 5 For the uncapacitated partition produced in the second branch of Algorithm 1, .
Proof. Consider a cluster added to at the end of the iteration, in which is the remaining unclustered vertex set at the beginning. Recall that each vertex of is selected as the pivot with an equal probability. We write the cluster formed using . Denote
One sees that counts the number of edge errors decided in this iteration if is selected, and is the total edge slack removed from the remaining instance and thus attributed to .
Consider a negative edge error introduced by . We have , and thus and are positive edges and then these three vertices form a bad triangle. Consider a positive edge error introduced by : We assume without loss of generality that is positive and thus is negative, and then these three vertices form a bad triangle too.
We conclude that for each edge error counted towards , it determines the unique bad triangle on . Conversely, for every bad triangle containing positive edges , and negative edge , it will be discovered when (, , respectively) is the pivot and the edge (, , respectively) is the edge error. In other words, every bad triangle contained in the subgraph induced by contributes exactly 3 edge errors when its three vertices are selected as the pivot.
Let be the number of bad triangles contained in the subgraph induced by . We have
Also for every bad triangle on , the slack of the edge is counted towards since at least one of is in . Therefore, the total slack of the edges of the triangle is included in , i.e.,
where the last inequality is by Lemma 4.
Let denote the expected cost of the partition restricted on , and denote the total slack of the edges in the subgraph induced by . We prove by induction that , for which the equality holds trivially when . When , we have
We then take , and thus prove the lemma.
Theorem 4. Given a fractional solution to the Cluster-LP in Eq. (3), the hybrid rounding Algorithm 1 runs in expected polynomial time in , the number of positive variables in , and the encoding length of , and returns a -feasible partition satisfying
Proof. For the running time, suppose has positive variables and each of them has at most bits. Each iteration of the first and the second branches takes an expected polynomial time in , , for probability generation followed by cluster formation. There are at most iterations in each branch, and thus the overall running time is in expected polynomial time.
For the quality of the returned partition , by Theorem 2 and Lemma 5 we have
Hence, using Lemma 3, we have
This proves the theorem. □
We are ready to present the complete algorithm in Algorithm 2 for the capacitated cluster editing problem, of which an instance consists of a complete edge-signed graph , a capacity , and an approximation tolerance .
| Algorithm 2 | The complete approximation algorithm. |
| Require: | , , a positive rational ; |
| Ensure: | a -feasible partition for . |
| 1: | if then |
| 2: | return the partition of all singletons; |
| 3: | else if (all positive components are cliques of size at most ) then |
| 4: | return the partition of all the components; |
| 5: | end if |
| 6: | ; |
| 7: | use Theorem 3 to compute a solution ; |
| 8: | run Algorithm 1 on to compute a solution ; |
| 9: | return . |
Table 2.
Theorem 5 For every fixed rational , the Capacitated Cluster Editing problem admits a randomized expected -approximation algorithm that runs in an expected polynomial time in the input size , bounded by in which the exponent does not depend on the capacity , times a polynomial in the precision encoding length.
Proof. The first conditional statement (Lines 1–5) of Algorithm 2 is exact, that gives an optimal solution. Otherwise, Theorems 3 and 4, together with , give
The overall running time of the algorithm follows from the running time stated in Theorems 3 and 4, for computing and , respectively. □
An improved pivoting algorithm
In the last section, we adopt the ordinary pivot algorithm of Ailon et al. [1] to first generate an uncapacitated partition , independently from the fractional solution stated in Theorem 3, followed by the splitting procedure to downsize large parts so that a candidate -feasible partition is achieved. Both the algorithmic steps and their performance analysis appear straight, with the most important guarantee , where is the total edge slack and is the -feasible partition produced by the first sampling branch of Cao et al. [7].
In this section, we propose an improved pivoting algorithm to generate directly a -feasible partition using the fractional solution stated in Theorem 3, that replaces the ordinary pivot algorithm in Algorithm 1. We continue to use the notations defined in the previous sections, such as the quantities , , associated with an edge , etc. Nevertheless, the upcoming algorithmic description and the analysis use mostly ’s. We therefore write the edge slack in Eq. (6) as an equivalent function of below.
Let
the slack of edge in Eq. (6) can be re-written as
Given a partition , when it is not -feasible, we have proven in Theorem 2 that downsizing every part of of size greater than by splitting it into a number of parts of size exactly and a possible residual part of size less than , leads to a -feasible partition satisfying . The proof of this inequality uses mostly the triangle inequality of the edge set edit distance. Below we separate the disagreement cost of into two parts and prove a more precise upper bound.
We denote the number of positive edge errors and the number of negative edge errors. Clearly, .
Lemma 6 For every partition , the downsized -feasible partition satisfies
Proof. Let denote the number of edges deleted during the downsizing process, and let be the number of negative edges among these edges.
By Lemma 1, for an optimal -feasible partition , we have , since every positive edge of is an error of and every negative edge is an error counted towards . Since the downsizing process changes the cost by , and , we have
This proves the lemma. □
Lemma 6 together with the edge slacks in Eq. (9) suggest that the second pivoting branch can have better trade-off between positive and negative neighbors when forming a cluster, and that the positive and negative edge errors can be analyzed with unequal weights.
The modified pivoting branch
Our modified pivot rounding algorithm follows the conditional seed-based architecture of García-Soriano and Schohn [17], where a seed is the selected subset containing the chosen pivot and, while positive neighbors inside the seed are surely admitted into the cluster, a different admission rule is set for positive neighbors outside the seed. To this purpose, we set up
One sees that both and are increasing in . The modified pivot rounding algorithm takes in a fractional solution to Cluster-LP in Eq. (3) and returns an uncapacitated partition . The final produced candidate -feasible partition is .
In the algorithm, assume is the current set of un-clustered vertices. It chooses a pivot from uniformly at random, and then select the seed from all those subsets containing , i.e., , with probability (recall the vertex coverage equality in Eq. (3) that ). The to-be constructed cluster initially contains and all its positive un-clustered neighbors in , i.e., ; then for each positive neighbor , it is added to only if and with probability . Every un-clustered negative neighbor is treated the same, that is added to with probability . This forms a new cluster in and the algorithm repeats until all vertices are clustered. A pseudocode of this modified pivot rounding is depicted in Algorithm 3.
Algorithm 3 Modified pivot rounding a fractional solution.
Require: , , a feasible solution to Cluster-LP in Eq. (3);
Ensure: an uncapacitated partition for .
, ;
while do
choose with probability ; ▷ the pivot;
choose with probability ;
;
for (each ) do
if and then
; ▷ positive neighbor inside ;
else if then
with probability ; ▷ positive neighbor outside ;
else
with probability ; ▷ negative neighbor, inside or outside ;
end if
end for
add to and update ;
end while
return .
A weighted performance analysis
Instead of the disagreement cost of , as in Lemma 5, in this section we estimate the quantity , which can be deemed as weighted cost of by assigning twice weight to a negative edge of . We prove the following lemma.
Lemma 7 The partition produced by Algorithm 3 satisfies .
Proof. Consider a cluster added to at the end of the current iteration, which is a subset of the remaining un-clustered vertices in the iteration. Note that each vertex of is selected as the pivot with an equal probability; we write for the random cluster for and denote
Similar to the proof of Lemma 5, counts negative edge errors, counts positive edge errors, but this time is the weighted total error decided in this iteration. Note that is kept the same, which is the total edge slack removed from the remaining instance and thus attributed to the cluster .
We prove the following inequality
where the expectations are conditional on the fixed history leading to the beginning of this current iteration.
From how a positive neighbor is admitted into the cluster, we see that a positive edge is included in with probability , and thus excluded with probability
In particular, when , the edge exclusion probability is exactly .
On the other hand, a negative edge is included in with probability .
Similar to the proof of Lemma 5, we use triangles to prove the joint probabilities of the edges of . We denote if the edge is positive, or otherwise . Consider a triangle on three distinct vertices , and let , followed by . With the selected pivot , the seed (, respectively) has probability (, , , respectively), where . Therefore, the joint probability that both are included in [17] is
It follows that the weighted error made by the edge is
For , as long as one endpoint is included in the cluster , its slack is attributed to , and one sees that such probability is ; the slack contributed by is thus
Since every vertex of the triangle can be chosen as the pivot in the iteration, we denote
and we will validate that for every triangle .
Triangle validation. We use Eqs. (13)–(15) to validate for all four kinds of triangles , which have 3, 2, 1 and 0 positive edges (denoted as -, -, - and -triangle), respectively. Let denote the three unordered values . Recall that . From the vertex coverage equalities of Eq. (3), we have
For a -triangle , order ; Eq. (16) becomes , and is a linear function in . It suffices to check that at and .
For a -triangle , let be the values for two positive edges and the value for the negative edge; Eq. (16) becomes and . The derivative of with respect to is ; hence it suffices to check that at .
For a -triangle, let be the value for the positive edges and be the values for the two negative edges; Eq. (16) becomes and , since one sees that does not appear in .
For each of the above three kinds of triangles, the function is a polynomial and on . The non-negativity of the function can be verified by the exact rational certificate, and thus is proved.
Lastly, for a -triangle, i.e., all three edges of the triangle are negative, we first have because
Then, and
Consequently, . This proves for the last kind of triangles.
It remains to consider the last case where , in which the pivot is an endpoint of the last remaining edge . One sees that either way the slack is attributed to the formed cluster. By Eq. (12), if is positive then it contributes a cost of ; or otherwise it contributes a weighted cost of . We have thus proved that, when , for the last edge its weighted cost is no greater than .
Adding over all triangles and possibly the above inequality for the last edge proves Eq. (11), which gives the conditional one-iteration inequality for the uniformly selected pivot by dividing . Summing the conditional inequalities over at most iterations proves the lemma.
The resulting approximation guarantee
Theorem 6 Given a fractional solution to the Cluster-LP in Eq. (3), the cheaper partition between the -feasible solution by the first branch of Algorithm 1 and the where produced by Algorithm 3 satisfies
The overall running time is in expected polynomial time in , the number of positive values in , and the encoding length of .
Proof. Let . Lemmas 6 and 7 give . Recall that Lemma 3 guarantees . The cheaper cost is no greater than any linear combination of the two costs, and therefore,
The running time of the entire algorithm is similar to the proof of Theorem 4.
Given that a fractional solution can be computed in polynomial time so that , for any positive (Theorem 3), we choose for any positive . Using , Theorem 6 gives
Conclusion
We studied the capacitated Cluster Editing problem where a graph is given, and the goal is to convert it into a collection of cliques of upper bounded size via a minimum number of edge insertions and deletions. The problem has been studied in the literature but not much, with the best approximation algorithm of ratio 5.37. Nevertheless, the uncapacitated variant has received at least two waves of extensive studies with several algorithmic frameworks, and the state-of-the-art approximation ratio of 1.3865.
In this paper, we presented three improved approximation algorithms, each having a distinct role. Our first -approximation algorithm builds on the proposed downsizing procedure, that converts an uncapacitated partition into a feasible one without increasing the cost too much, and it is achieved by calling the state-of-the-art 1.3865-approximation algorithm for uncapacitated problem. The second algorithm employs the near optimal fractional solution to the Cluster LP formulation of the problem, and combines the rounding through sampling by Cao et al. [7] and the ordinary pivoting method by Ailon et al. [1]. Using the downsizing procedure again, the second algorithm is proven to have an approximation ratio of . Replacing the ordinary pivoting method in the second algorithm by the conditional affine pivoting rule of García-Soriano and Schohn [17], again together with the downsizing procedure, the third algorithm is a further improved -approximation algorithm. We remark that the downsizing procedure, despite simple, has its important role in all three algorithms. It is also important to note that we extended the algorithm design and analysis techniques developed for the uncapacitated problem, though not novel but non-trivially. It remains interesting to see further development for either uncapacitated or capacitated cluster editing, and improved lower bounds on the approximation ratios.
References
- [1]N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5):23, 2008.
- [2]N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56:89–113, 2004.
- [3]L. Bastos, L. S. Ochi, F. Protti, A. Subramanian, I. C. Martins, and R. G. S. Pinheiro. Efficient algorithms for cluster editing. Journal of Combinatorial Optimization, 31(1):347–371, 2016.
- [4]S. Böcker, S. Briesemeister, Q. B. A. Bui, and A. Truss. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467–5480, 2009.
- [5]S. Böcker, S. Briesemeister, and G. W. Klau. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316–334, 2011.
- [6]S. Böcker and P. Damaschke. Even faster parameterized cluster deletion and cluster editing. Information Processing Letters, 111(14):717–721, 2011.DOI
- [7]N. Cao, V. Cohen-Addad, E. Lee, S. Li, A. Newman, and L. Vogl. Understanding the cluster linear program for correlation clustering. In Proceedings of STOC 2024, pages 1605–1616, 2024.DOI
- [8]N. Cao, V. Cohen-Addad, E. Lee, S. Li, A. Newman, and L. Vogl. Understanding the cluster LP for correlation clustering. arXiv:2404.17509v3, 2025.DOI
- [9]Y. Cao and J. Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152–169, 2012.
- [10]M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):360–383, 2005.
- [11]S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Proceedings of STOC 2015, pages 219–228, 2015.arxiv.org/abs/1412.0681
- [12]J. Chen and J. Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211–220, 2012.
- [13]V. Cohen-Addad, E. Lee, S. Li, and A. Newman. Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. In Proceedings of FOCS 2023, pages 1082–1104, 2023.
- [14]V. Cohen-Addad, E. Lee, and A. Newman. Correlation clustering with Sherali–Adams. In Proceedings of FOCS 2022, pages 651–661, 2022.
- [15]P. Damaschke. Fixed-parameter enumerability of cluster editing and related problems. Theory of Computing Systems, 46(2):261–283, 2010.
- [16]F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences, 80(7):1430–1447, 2014.DOI
- [17]D. García-Soriano and A. Schoenh. Approximate dual separation for the cluster LP: A 1.387 approximation for correlation clustering. arXiv:2607.27829v2, 2026.
- [18]J. Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science, 410(8–10):718–726, 2009.
- [19]V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya. Graph clustering with a constraint on cluster sizes. Journal of Applied and Industrial Mathematics, 10(3):341–348, 2016.
- [20]V. P. Il’ev and A. A. Navrotskaya. Computational complexity of the problem of approximation by graphs with connected components of bounded size. Prikladnaya Diskretnaya Matematika, 3(13):80–84, 2011.
- [21]S. Ji, Y. Cheng, J. Tan, and Z. Zhao. An improved approximation algorithm for the capacitated correlation clustering problem. International Journal of Foundations of Computer Science, 35(6):757–774, 2024.DOI
- [22]S. Ji, D. Xu, M. Li, and Y. Wang. Approximation algorithm for the correlation clustering problem with non-uniform hard constrained cluster sizes. In Proceedings of AAIM 2019, volume 11640 of Lecture Notes in Computer Science, pages 159–168, 2019.DOI
- [23]A. V. Kononov and V. P. Il’ev. Approximation algorithms for the cluster editing problem with small clusters. Discrete Optimization, 57:100900, 2025.DOI
- [24]G. J. Puleo and O. Milenkovic. Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM Journal on Optimization, 25(3):1857–1872, 2015.arxiv.org/abs/1411.0547
- [25]R. Shamir, R. Sharan, and D. Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144(1–2):173–182, 2004.
- [26]A. van Zuylen and D. P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. Mathematics of Operations Research, 34(3):594–620, 2009.