An FPT Constant-Factor Approximation Algorithm for Correlation Clustering

Jianqi Zhou, Zhongyi Zhang, Jiong Guo ( ✉ ) {}^{(\textrm{{\char 0\relax}})} · 2025

Read An FPT Constant-Factor Approximation Algorithm for Correlation Clustering by Jianqi Zhou, Zhongyi Zhang, Jiong Guo ( ✉ ) {}^{(\textrm{{\char 0\relax}})} (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00281.txt.

Introduction

Jianqi Zhou, Zhongyi Zhang, and Jiong Guo give a new algorithm for grouping data in a 2025 paper. The problem, correlation clustering, starts with pairs marked as alike or unlike. The goal is to form groups that break as few of those marks as possible. The problem is known to be hard, even on complete data, and rough answers are the norm.

The authors study the case where the pair graph has holes, since real data often lacks some marks. They design a method whose running time stays manageable when the number of misplaced items, the parameter, is small. The method still guarantees an answer within a fixed factor of the best one. Their work extends earlier results that needed a complete graph.

Catalog record

CREATORJianqi Zhou, Zhongyi Zhang, Jiong Guo ( ✉ ) {}^{(\textrm{{\char 0\relax}})}
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00281

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering Thanks: The work has been supported by the National Natural Science Foundation of China (No. 61772314, 61761136017, and 62072275). Jianqi Zhou, Zhongyi Zhang, Jiong Guo ( ✉ ) {}^{(\textrm{{\char 0\relax}})} Abstract The Correlation Clustering problem is one of the most extensively studied clustering formulations due to its wide applications in machine learning, data mining, computational biology and other areas. We consider the Correlation Clustering problem on general graphs, where given an undirected graph (maybe not complete) with each edge being labeled with ⟨ + ⟩ \langle+\rangle or ⟨ − ⟩ \langle-\rangle , the goal is to partition the vertices into clusters to minimize the number of the disagreements with the edge labeling: the number of ⟨ − ⟩ \langle-\rangle edges within clusters plus the number of ⟨ + ⟩ \langle+\rangle edges between clusters. Hereby, a ⟨ + ⟩ \langle+\rangle (or ⟨ − ⟩ \langle-\rangle ) edge means that its end-vertices are similar (or dissimilar) and should belong to the same cluster (or different clusters), and “missing” edges are used to denote that we do not know if those end-vertices are similar or dissimilar. Correlation Clustering is NP-hard, even if the input graph is complete, and Unique-Games hard to obtain polynomial-time constant approximation on general graphs. With a complete graph as input, Correlation Clustering admits a ( 1.994 + ε ) (1.994+\varepsilon) -approximation. We investigate Correlation Clustering on general graphs from the perspective of parameterized approximability. We set the parameter k k as the minimum number of vertices whose removal results in a complete graph, and obtain the first FPT constant-factor approximation for Correlation Clustering on general graphs which runs in 2 O ⁡ ( k 3 ) ⋅ poly ​ ( n ) 2^{O(k^{3})}\cdot\textrm{poly}(n) time. 1 Introduction Due to wide applications in machine learning, data mining, computational biology, and other areas, the Correlation Clustering problem, introduced by Bansal, Blum, and Chawla [ 2 ] , has been extensively studied concerning its computational complexity, approximability, and parameterized complexity. Bansal, Blum, and Chawla [ 2 ] initially defined the Correlation Clustering problem on complete graphs as follows: given a complete, undirected graph of n vertices (items), where each edge is labeled either \langle+\rangle or \langle-\rangle depending on whether its two end-vertices are considered to be similar or dissimilar, the goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we seek for a clustering that maximizes the sum of the number of \langle+\rangle edges within clusters and the number of \langle-\rangle edges between clusters (equivalently, minimizes the number of disagreements: the number of \langle-\rangle edges inside clusters plus the number of \langle+\rangle edges between clusters). Note that the Correlation Clustering problem does not specify the number of clusters in advance. Correlation Clustering with minimizing disagreements and with maximizing agreements are equivalent with respect to classical complexity, and NP-complete on complete graphs [ 2 ] . However, they differ in approximability. For the version of minimizing disagreements on complete graphs, Bansal, Blum and Chawla [ 2 ] gave the first constant-factor approximation algorithm. Charikar, Guruswami and Wirth [ 3 ] improved the approximation factor to 4 by rounding the standard linear programming (LP) relaxation and proved APX-hardness, meaning that the problem does not admit a polynomial-time approximation scheme (PTAS). Ailon, Charikar and Newman [ 1 ] proposed a combinatorial randomized 3-approximation algorithm and a LP-based randomized 2.5-approximation algorithm. Then, Zuylen and Williamson [ 13 ] gave a deterministic 3-approximation algorithm by following the paradigm of Ailon et al. [ 1 ] and using an LP relaxation. Finally, the LP-based pivoting algorithm was further improved to a 2.06-approximation by Chawla et al. [ 5 ] and to a (1.994+\varepsilon) -approximation by Cohen-Addad, Lee and Newman [ 6 ] . For the version of maximizing agreements on complete graphs, Correlation Clustering admits a PTAS [ 2 ] . However, in most real-world applications, we are not able to obtain the similarity information of all item pairs, which results in incomplete graphs as input for Correlation Clustering. A missing edge means that its two end-vertices might be clustered together or be separated in different clusters. With missing edges allowed, we arrive at the Correlation Clustering on general graphs. For the version of minimizing disagreements on general graphs, Charikar, Guruswami and Wirth [ 3 ] and Demaine et al. [ 7 ] independently proposed O(\log n) -approximation even with positively weighted edges. They also proved Correlation Clustering on general weighted (or unweighted) graphs is equivalent to Minimum Multicut on weighted (or unweighted) graphs [ 3 , 7 ] , and thus obtaining polynomial-time constant-factor approximation is Unique-Game hard [ 4 ] . For the version of maximizing agreements on general edge-weighted graphs, Swamy [ 11 ] and Charikar, Guruswami and Wirth [ 3 ] independently derived a 0.766-approximation by rounding semidefinite programs. Our contributions. We focus on the minimizing disagreements version on general unweighted graphs. As mentioned above, obtaining a polynomial-time constant-factor approximation for this version is Unique-Games hard [ 3 , 4 , 7 ] . We aim at designing an FPT constant-factor approximation algorithm. An FPT c -approximation algorithm returns a c -approximative solution in f(k)\cdot|I|^{O(1)} time, where f is a computable function and k is a parameter of the input I . Motivated by the polynomial-time inapproximability and the (1.994+\varepsilon) -approximation algorithm [ 6 ] for Correlation Clustering on complete unweighted graphs, we use the so-called “distance from approximability” concept for designing FPT approximation algorithms, that is, introducing a parameter measuring the distance between the inapproximable and approximable cases and designing approximation algorithms with the exponential running time restricted to the parameter. This concept has been used to design FPT approximation algorithms for TSP on general graphs [ 12 ] . Here, we use a structure parameter k to measure the distance of a general graph from the complete graph. We choose k as the minimum number of vertices whose removal results in a complete graph, in other words, that is the minimum number of vertices to cover the missing edges. Given a general instance, we can apply the search tree algorithms for Verter Cover [ 8 , 9 ] to determine the value of k in O(2^{k}\cdot n^{2}) time. Using k as parameter, we achieve a (\frac{18}{\delta^{2}}+7.3) -approximation for Correlation Clustering on general unweighted graphs with a running time of 2^{O(k^{3})}\cdot\text{poly}(n) , where \delta=\frac{1}{65} . To our best knowledge, this is the first FPT constant-factor approximation algorithm for Correlation Clustering on general graphs. Due to lack of space, most proofs are omitted. 2 Preliminaries We introduce some basic definitions and notations. We consider an undirected graph G=(V,E) on n vertices and let e(u,v) denote the label \langle+\rangle or \langle-\rangle of the edge (u,v) . We call an edge (u,v) “positive” if e(u,v)=\langle+\rangle and “negative” if e(u,v)=\langle-\rangle . If (u,v)\notin E , we call (u,v) an “empty” edge. Let E^{\langle+\rangle}=\{(u,v)\mid e(u,v)=\langle+\rangle\} denote the set of all positive edges, and let G^{\langle+\rangle}=(V,E^{\langle+\rangle}) be the graph induced by E^{\langle+\rangle} . Likewise we define E^{0} and G^{0} for empty edges. Let N^{+}(u)=\{v\mid e(u,v)=\langle+\rangle\} , N^{-}(u)=\{v\mid e(u,v)=\langle-\rangle\} and N^{0}(u)=\{v\mid(u,v)\notin E\} denote the set of the positive, negative

Read the complete text