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

Please help.

  • $\begingroup$ Knowing that in Spielman et al.'s algorithms the probabilities were not fixed. One time the sampling probability of an edge was related to the vertex degree another time to the effective resistance of the edge. $\endgroup$ – Sal Dec 16 '18 at 14:48
  • $\begingroup$ 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. $\endgroup$ – Zach Langley Dec 17 '18 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.