Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering

Thanks for your thoughtful review. Please find our responses for each question in the following:

Since your lower bound proofs (for both the pseudometric CC and CCC) are based on integrality gaps, I assume one could not hope for better rounding algorithms based on these LPs, am I correct?

Response: We apologize for causing such confusion. The lower bound provides that the pivot-based algorithm with an arbitrary rounding function cannot bypass that value. The best-known integrality gaps for pseudometric-weighted CC and CCC are still 3 and 2, respectively. However, when it comes to the case of pseudometric-weighted CC, since the selected rounding functions meet the lower bound of 10/3, we hypothesize the integrality gap for the LP as 10/3 and leave it as future work.

If yes, then do you believe the more recent correlation clustering LPs, e.g., the one in “Understanding the Cluster LP for Correlation Clustering” [STOC’24] will be helpful for further improvements?

Response: Thank you for your insightful comment. Indeed, both variants can be easily formulated as variants of cluster LP, which would provide an algorithm with an approximation factor less than 2 by accounting for the cluster-based algorithm as well, as long as the (near-)optimal solution for the LP is provided. The main challenge for using the cluster LP framework for those variants is obtaining a near-optimal solution for those new LPs.

I do not understand Figure 1. Here, what are the x and y axes? What does the figure want to say? I hope it could give some insights for the choice of the intricate constants.

Response: $x$ refers to the LP value corresponding to the pivot edge (i.e., one of the endpoints is a pivot vertex) whose color differs from the color under execution of the pivot-based algorithm, while $y$ refers to the corresponding probability not to contain the edge in a single cluster. The plot shows the choice of our $f^\circ$, and the region of $(x,y)$ such that: The triple-based analysis in Section 5 cannot guarantee an $\alpha=2.15$-approximation if the value $x$ is assigned to the probability of $y$ by the rounding function $f^\circ$.

Overall, the computation of the region acts as a primary test for our construction of $f^\circ$: Once the proposed function doesn’t intersect with the region, we can attempt to validate the approximation factor of $2.15$.

We’ve added the explanation in Section 4.2 regarding the comment.

Notations $E^\circ$ and $f^\circ$ were used before being defined.

Response: Thank you for pointing out the typo. We’ve added a detailed explanation in Section 3 regarding the comment.

Missing parentheses for equation (13) on the caption of Figure 1.

Response: Thank you for pointing out the typo. We’ve revised regarding the comment.

In the appendix, you used tables to show that by the choice of $\alpha$, we have $\alpha\cdot LP-ALG\geq 0$. The captions of these tables are “caption” – change this.

Response: Thank you for pointing out the typo. We’ve revised regarding the comment.

Thank you for your follow-up questions.

Can you give more details about the LP?

Response: In the original cluster LP, the variable $z_S\,(S\subseteq V)$ indicated if $S$ exists as an exact cluster in the clustering. This has induced a relation with the variables in the standard LP as $\sum_{S\ni uv}z_S=1-x_{uv}$ and the covering property $\sum_{S\ni u}z_S = 1$.

For the pseudometric-weighted CC, all the variables and constraints for the cluster LP remains the same; the only difference is the objective function is now changed from $\sum_{uv\in E^+}x_{uv}+\sum_{uv\in E^-}(1-x_{uv})$ to $\sum_{uv\in E^+}w_{uv}\cdot x_{uv}+\sum_{uv\in E^-}w_{uv}\cdot (1-x_{uv})$.

For the CCC, on the other hand, the value of $z_S$ is now partitioned as $\sum_{c\in L}z_S^c$, where $z_S^c$ indicates if $S$ exists as an exact cluster of color c in the clustering. Therefore, using relations $\sum_{S\ni u}z_S^c=1-x_{u}^c$ and $\sum_{S\ni uv}z_S^c=1-x_{uv}^c$ as well as the covering property $\sum_{S\ni u}\sum_{c\in L}z_S^c=1$, all the constraints from standard LP for CCC can be verified. The objective function is the same as those from standard LP for CCC, since the relation between $z_S$ variables and $x_{uv}$ variables is already developed above.

Also, what is the main barrier to solving that LP? If we are only interested in polynomial-time algorithms, can we simply run some Ellipsoid algorithms?

Response: The main barrier for solving the cluster LP is that the number of variables $z_S$ (or $z_S^c$ for CCC) is exponential to $|V|$. Using general LP solving algorithms such as the Ellipsoid algorithm would thus take $2^{O(|V|)}$ (multiplied by $\text{poly}(|L|)$ for CCC) time, which is undesirable. Therefore, it is important to find an alternative way to (approximately) solve the cluster LP in polynomial time by exploiting properties of the CC problem, which was one of the main discussions in [STOC’25].

Thanks for your thoughtful review. Please find our responses for each question in the following:

The methods and ideas are not so novel. The improvement has been possible via a detailed case analysis and careful selection of rounding functions. The resulting algorithm may give improved quality guarantee but it is not so novel and not so elegant.

Response: This paper differs from previous papers in the following ways:

1. To the best of our knowledge, this paper presents the earliest theoretical inspection particularly on the pseudometric-weighted CC problem, whose significance is discussed in Section 2.1.
   Moreover, since the lower bound of the approximation factor for the pivot-based algorithm is a fractional value of 10/3 and is achievable (which is quite unusual), it can also be hypothesized that the integrality gap of the pseudometric-weighted standard LP is also 10/3. This is slightly higher than the integrality gap of 3 for the easier problem: A CC whose presenting edges form a k-partite graph. Providing such an integrality gap of 10/3 would indicate that there are more features from pseudometric compared to ultrapseudometric (i.e., a pseudometric retaining cluster-like features) as a weight that affects the hardness of the LP or the problem.

2. This paper also emphasizes the applicability and the effectiveness of the rounding technique that was explicitly used only for the original CC before (as far as we know). Whenever the triple-based analysis is involved, one can think of fitting the rounding functions, which is simple yet likely to be effective, as in the result of the paper.
   Despite its simplicity, it is also important to check the extent of its applicability and to check if the overall procedure is analyzable. For example, while designing the algorithm for CCC, we had to define an additional sign of ‘$\circ$’ with the corresponding rounding function; while analyzing the performance for pseudometric-weighted CC, the ideas that the tuple $(w_{uv},w_{vw},w_{wu})$ satisfying triangle inequality forms a convex cone and that $\alpha\cdot LP-ALG$ is affine with respect to the tuple were crucial in reducing uncountable cases for analysis to only 3 cases consisting extremal rays of the cone.

The methods rely on LP relaxation, which is not so practical. Overall, this is a theory paper and there are no experiments.

Response: Although solving the LP might be a limitation on the practicality, recent work on solving cluster LP implies that the near-optimal solution for the LP can be constructed in $\tilde{O}(2^{\text{poly}(1/\varepsilon)}|V|)$ time using multiplicative weight update (MWU) method if the framework is generalizable to each variant.
Moreover, since the state-of-the-art algorithm for CC uses both pivot-based and cluster-based algorithms, the proposed rounding functions can behave as a good initial choice of rounding functions for the pivot-based algorithm in the mixed algorithm for variants.

In terms of presentation, it is not always so clear when the authors refer to the problem where all the edges are present (clique) and when the edges may be missing (no + or - signs, or no color labels).

Response: Thank you for pointing out the ambiguity. In every case, all the edges are present; missing edges can only be encoded as arbitrary-signed edges with zero weight for pseudometric-weighted CC. We’ve made a clarification regarding the comment.

Thanks for your thoughtful review. Please find our responses for each question in the following:

1. What is the time complexity of the proposed algorithm?

Response: Solving the LP takes $\text{poly}(|V|,|L|)$ time (e.g., $\tilde{O}(|V|^{6.5}|L|^{2.5})$ using Vaidya's algorithm, or can be made significantly faster by exploiting the sparsity of the constraint matrix in practice).
The following pivot-based algorithm for pseudometric-weighted CC takes $O(|V|^2)$ time, while for CCC takes $O(|V||L|+\sum_{c\in L}|S_c|^2)=O(|V|(|L|+|V|))$ ($S_c$ is a set of vertices such that $c$ is a color of strict majority).

Although solving the LP is the bottleneck, this can be addressed if the $\tilde{O}(2^{\text{poly}(1/\varepsilon)}|V|)$ time algorithm via the multiplicative weight update (MWU) method for solving the cluster LP [STOC’25] is generalizable to each variant.

2. Can we extend the proposed algorithms to solve other variants of correlation clustering problems and achieve improved approximation guarantees? If no, what are the difficulties?

Response: As long as the problem possesses both a standard LP and a theoretically guaranteed pivot-based algorithm, the technique is still valid to make the approximation factor closer to the known integrality gap.