Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

Summary: Input perturbation enables reuse of a non-private MST algorithm to yield a private MST under DP; experiments validate. Link to Top-k Selection yields privacy-utility lower bound for MST under approximate DP; O~(n^{3/2}) error is optimal up to logs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1974
Venue: PODS
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,352 | 27.99%
DOI: 10.1145/3725240

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3,325	Shortest Paths and Distances with Differential Privacy	2016	PODS	7.2211576e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,727	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB	4.1945683e-05
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196
8,234	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	4.5535352e-05
10,383	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD	4.1945683e-05
11,264	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	4.1945683e-05
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
4,794	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB	5.9161511e-05
5,366	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD	5.5460085e-05
11,164	Node-Differentially Private Estimation of the Number of Connected Components	2023	PODS	4.1945683e-05
3,325	Shortest Paths and Distances with Differential Privacy	2016	PODS	7.2211576e-05