# Sampling probabilities for half-sparsification algorithm

https://dl.acm.org/citation.cfm?id=2948062

In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for spectral sparsification. The idea was to reduce sparsification to half-sparsification problem, in which the output is sparser only by a factor of 2, while being a (1+$$\epsilon/log \rho$$)-spectral approximation of the input graph.

Inspired by the sampling spectral sparsification algorithms of Spielman and his colleagues, they used the process of random sampling in their algorithm1 called half-sparsification.

In this simple algorithm, they have computed a t-bundle spanner $$H$$ for some t. As, for the edges left that are not in $$H$$, they did a random sampling process that assigns a probability 1/4 if the edge is chosen and and 3/4 otherwise.

My problem is with these sampling probabilities, is their some background for how they chose a fixed probability 1/4??

• Is your question about why one can use a fixed probability, or why the fixed probability 1/4 works? Intuitively, a fixed probability works because all the edges of high effective resistance are consumed by the $t$-bundle spanner for a large enough choice of $t$. As for why 1/4, many other values could be made to work, but this one is simple enough. – Zach Langley Dec 17 '18 at 19:00