pipette
ENEnglish

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.