Distributed Randomized Sampling for Locally Private Independent Sets

Many randomized distributed graph algorithms rely on simple local rules and few communication rounds, making them natural starting points for locally private protocols. We explore this connection through the maximum independent set problem under local edge differential privacy. Previous work shows that an edge-private algorithm that always publishes a valid independent set can select at most one vertex. We therefore allow edges between selected vertices and count each such edge as a defect. We develop a noninteractive $\epsilon$-local edge-private algorithm that samples vertices independently using privately perturbed degrees. For fixed $\epsilon >0$ and $n$-vertex graphs with bounded average degree or degeneracy, the expected output size of our algorithm is ${\Omega }_{\epsilon }(n/\log n)$ and the expected defect count is $O_{\epsilon }(n/{\log }^{2}n)$. Moreover, we also show that the ratio of defects to output size tends to zero with high probability. For a fixed $\epsilon$ and sufficiently large $n$, we also prove that any $\epsilon$-edge-DP or $\epsilon$-edge-LDP algorithm achieving an expected approximation ratio $r\le (n+1)/4$ on every $n$-vertex graph with at most $n$ edges must incur $\Omega (n/r^2)$ expected defects on some graph in this class. For $r=\Theta (\log n)$, the lower and upper bounds on the expected defect count match asymptotically.