Sampling probabilities for half-sparsification algorithm

63 Views Asked by At

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??