Capacitated Cluster Editing: Approximation Ratio Improved to 1.7537

Cluster Editing is a classic problem in computational biology and social network analysis. The goal is to partition a signed graph into several disjoint cliques by making the minimum number of edge modifications. When clique sizes are unconstrained, the problem has been shown to be both NP-hard and APX-hard, and the currently best approximation ratio is 1.3865+ε. However, in many practical scenarios, clique sizes need to be bounded—for example, protein complexes have limited sizes in protein complex identification, and social circles have a cap on the number of members in social circle partitioning. This capacitated variant, called Capacitated Cluster Editing, has received relatively little study, and the previous best approximation ratio was only 5.37. A recent paper proposes new downsizing techniques and a hybrid sampling method, significantly improving the approximation ratio to 1.7537+ε and setting a new benchmark for this problem.

Problem Definition and Background

Capacitated Cluster Editing takes a complete signed graph as input, where a positive edge indicates that two vertices agree with each other and a negative edge indicates disagreement. The goal is to construct a set of disjoint cliques of size at most a given k, minimizing the total number of negative edges inside cliques plus positive edges outside cliques. The problem is NP-hard when unconstrained and has been shown to be APX-hard, which means no polynomial-time approximation scheme (PTAS) exists unless P=NP. Previously, the best approximation ratio for the uncapacitated version was α=1.3865+ε, while the best for the capacitated version was only 5.37. The introduction of capacity constraints makes the problem more challenging, because simple clustering methods may violate size limits, while forcibly splitting clusters increases the editing cost.

Approximation Ratio and APX-hardness: The approximation ratio is the core metric for evaluating approximation algorithms, defined as the ratio of the algorithm's objective value to the optimal objective value (for minimization problems, the ratio is typically required to be ≥1). If a polynomial-time algorithm can be designed whose approximation ratio is arbitrarily close to 1 (i.e., a (1+ε)-approximation algorithm for any ε>0), the problem is said to admit a polynomial-time approximation scheme (PTAS). APX-hard is a stronger complexity characterization than NP-hard: if a problem is APX-hard, then unless P=NP, it admits no PTAS. Capacitated Cluster Editing has been shown to be APX-hard, meaning researchers can only pursue constant approximation ratios and cannot approach the optimal solution arbitrarily closely. The large gap between the previous best ratio of 1.3865+ε for the uncapacitated version and 5.37 for the capacitated version reflects the theoretical difficulty of this problem.

Downsizing Technique: From Uncapacitated to Capacitated

The paper first proposes a downsizing process that, based on any α-approximation algorithm for the uncapacitated problem, constructs an α_k=2α+1 approximation algorithm for the capacitated problem. Specifically, the process first clusters the graph into cliques without capacity constraints, then splits or adjusts oversized cliques to satisfy the size upper bound. This technique directly links the approximation ratio of the capacitated problem to the best approximation ratio of the uncapacitated problem, providing a foundational framework for subsequent improvements. Although the 2α+1 ratio, approximately 3.773 when α=1.3865, already improves upon the previous 5.37, the authors do not stop there and further explore a more powerful LP sampling method.

Hybrid Sampling: cluster-LP and pivoting

The core innovation of the paper is a hybrid method combining cluster-LP sampling and pivoting techniques. For any fractional capacitated cluster-LP solution with cost L, the authors prove that the hybrid method using ordinary pivoting has expected cost at most (9/5)L + (1/10)OPT_k, while the hybrid method using conditional pivoting has expected cost at most (306/203)L + (50/203)OPT_k. Here OPT_k denotes the optimal solution cost of the capacitated problem. The key to these bounds is that, through random sampling and pivoting, the algorithm can guarantee near-optimal solution quality in expectation while satisfying capacity constraints. Conditional pivoting further reduces the coefficients, yielding a better final approximation ratio.

Linear Programming (LP) Relaxation and Randomized Rounding: Many combinatorial optimization problems can be formulated as integer programs. Relaxing the integer constraints to continuous variables in the interval [0,1] yields a linear programming relaxation. The LP relaxation can be solved in polynomial time, and its optimal value L is a lower bound on the optimal value OPT of the original problem (L≤OPT for minimization problems). Randomized rounding uses the probabilistic information of the LP fractional solution to construct an integer solution and analyzes the expected cost. The cluster-LP in this paper is an LP formulation designed specifically for cluster editing, with variables describing whether pairs of vertices are assigned to the same clique. Pivoting is a random sampling technique that relies on the LP fractional solution: it selects a "pivot" vertex with probability proportional to the fractional value, groups it with some vertices into a clique, and then recursively processes the remaining vertices. The hybrid method combines LP sampling and pivoting; through a carefully designed probability distribution, the expected cost is bounded by a linear combination of L and OPT_k, yielding a constant approximation ratio.

Approximation Ratio Results and Significance

Using a cardinality-constrained adaptation of the approximate dual separation framework of García-Soriano and Schohn, the authors obtain the required fractional solution and derive a randomized (1.9+ε)-approximation algorithm and a randomized (1.7537+ε)-approximation algorithm, respectively. The latter is the current best approximation ratio for Capacitated Cluster Editing, a significant improvement over the previous 5.37. This result not only narrows the gap between the capacitated and uncapacitated versions (the uncapacitated version being 1.3865+ε) but also provides a new technical route for future research. The paper's method is general and may inspire algorithm design for other constrained clustering problems.

Approximate Dual Separation Framework: Approximate dual separation is a dual method for analyzing the integrality gap of LP relaxations. It constructs an approximate dual solution to the primal problem to prove an upper bound on the gap between the optimal value of the LP relaxation and the integer optimum. The framework of García-Soriano and Schohn was originally designed for uncapacitated clustering problems; this paper adapts it to the case of cardinality constraints (i.e., each clique has size at most k), thereby obtaining a fractional solution to the capacitated cluster editing LP. This fractional solution is the input to the subsequent hybrid sampling algorithm, and the relationship between its cost L and OPT_k directly determines the final approximation ratio. The introduction of cardinality constraints requires the dual separation process to additionally handle clique size limits, which is one of the main technical challenges.

Practical Applications and Future Directions

Capacitated Cluster Editing has broad applications in bioinformatics (e.g., protein complex identification) and social network analysis (e.g., community detection). Better approximation algorithms mean that more reasonable clustering results can be obtained at a smaller editing cost in these scenarios. Future work may include further improving the approximation ratio, reducing algorithm complexity, and extending the method to more general constraints (such as overlapping cliques or hierarchical structures). In addition, the hybrid sampling technique in the paper may also be borrowed for other combinatorial optimization problems.

One-line Summary

A new algorithm improves the approximation ratio for Capacitated Cluster Editing from 5.37 to a randomized 1.7537+ε.

Paragraph Summary

Capacitated Cluster Editing requires partitioning a signed graph into cliques of size at most k to minimize editing cost; the previous best approximation ratio was only 5.37. This paper proposes a downsizing technique that, based on an α-approximation algorithm for the uncapacitated problem, achieves a 2α+1 approximation ratio; it further combines cluster-LP sampling with pivoting in a hybrid method, proving that the expected cost with ordinary pivoting is at most (9/5)L+(1/10)OPT_k and with conditional pivoting at most (306/203)L+(50/203)OPT_k. Using a cardinality-constrained adaptation of the approximate dual separation framework to obtain a fractional solution, the authors ultimately derive randomized (1.9+ε)-approximation and (1.7537+ε)-approximation algorithms, significantly narrowing the gap with the uncapacitated version's 1.3865+ε and providing a general technical route for constrained clustering.