Many fast graph algorithms begin by preprocessing the graph to improve its sparsity. A common form of this is spectral sparsification, which involves removing and reweighting the edges of the graph while approximately preserving its spectral properties. This task has a more general linear algebraic formulation in terms of approximating sums of rank-one matrices. This article considers a more general task of approximating sums of symmetric, positive semidefinite matrices of arbitrary rank. We present two deterministic, polynomial time algorithms for solving this problem. The first algorithm applies the pessimistic estimators of Wigderson and Xiao, and the second involves an extension of the method of Batson, Spielman, and Srivastava. These algorithms have several applications, including sparsifiers of hypergraphs, sparse solutions to semidefinite programs, sparsifiers of unique games, and graph sparsifiers with various auxiliary constraints.

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph (n, p). For all p(n) ∊ [0,1], we show that, with high probability T is precisely the minimum between δ and ⌊m/(n – 1)⌋, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals ⌊m/(n – 1)⌋ and A equals ⌈m/(n – 1)⌉; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k → ∞.