Node-Differentially Private Estimation of the Number of Connected Components. (arXiv:2304.05890v1 [cs.DS])

We design the first node-differentially private algorithm for approximating
the number of connected components in a graph. Given a database representing an
$n$-vertex graph $G$ and a privacy parameter $\varepsilon$, our algorithm runs
in polynomial time and, with probability $1-o(1)$, has additive error
$\widetilde{O}(\frac{\Delta^*\ln\ln n}{\varepsilon}),$ where $\Delta^*$ is the
smallest possible maximum degree of a spanning forest of $G.$
Node-differentially private algorithms are known only for a small number of
database analysis tasks. A major obstacle for designing such an …

algorithm algorithms analysis database delta design error forest major node parameter privacy private spanning vertex