  Computing the core decomposition of a graph is a fundamental problem that has
recently been studied in the differentially private setting, motivated by
practical applications in data mining. In particular, Dhulipala et al. [FOCS
2022] gave the first mechanism for approximate core decomposition in the
challenging and practically relevant setting of local differential privacy. One
of the main open problems left by their work is whether the accuracy, i.e., the
approximation ratio and additive error, of their mechanism can be improved. We
show the first lower bounds on the additive error of approximate and exact core
decomposition mechanisms in the centralized and local model of differential
privacy, respectively. We also give mechanisms for exact and approximate core
decomposition in the local model, with almost matching additive error bounds.
Our mechanisms are based on a black-box application of continual counting. They
also yield improved mechanisms for the approximate densest subgraph problem in
the local model.
