← 研踪 PaperTrailarXiv:2611.10184 · v1
Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time
首次提交 2026-11-07 04:02
版本更新 2026-11-07 04:02
雷达观测 2026-11-10 10:11
摘要
We present a fully dynamic algorithm for correlation clustering that supports \emph{vertex} insertions and deletions while maintaining an $O(1)$ 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 $G=(V,E^+\cup E^-)$, 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 04:02 · 最新观测版本
Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time
We present a fully dynamic algorithm for correlation clustering that supports \emph{vertex} insertions and deletions while maintaining an $O(1)$ 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 $G=(V,E^+\cup E^-)$, 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.
查看此版本解读 →查看此版本原文 ↗