pipette
ESEspañol

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie, Samson Zhou

Preprint

In the authors' words

We present a fully dynamic algorithm for correlation clustering that supports vertex insertions and deletions while maintaining an approximation in polylogarithmic amortized update time. This resolves an open problem of vertex deletions posed by a recent line of work on dynamic correlation clustering. We adopt the min-disagreement objective for correlation clustering, i.e., given a signed complete graph , we want to minimize the total number of edge crossing clusters and edges within clusters. The input is given in the adjacency list model, where each update inserts or deletes a node along with its full set of neighbors. Our main technical contribution is a fault-tolerant sparse-dense decomposition framework which unlike the existing decomposition-based frameworks allows for structural inconsistencies as long as the induced cost is bounded. We also show a separation between explicitly maintaining the (stronger) sparse-dense decomposition and maintaining a constant-factor approximation to correlation clustering, which may be of independent interest.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.