I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph has bounded degree or at least an expected bounded degree?

  • 1
    $\begingroup$ I think the question needs a lot of clarification. 1) What kind of object should the sparsified graph be (a subgraph of the original? weighted subgraph?) 2) What property of the original graph should it preserve? (cuts? the spectrum of the Laplacian?) 3) What is "expected degree"? (what do you take the expectation over? a random vertex? the randomness of the algorithm?) If I assume you want a weighted subgraph of the input that preserves all cuts up to $1\pm \varepsilon$, the star graph shows that you cannot achieve bounded degree. $\endgroup$ – Sasho Nikolov Sep 1 '14 at 16:26
  • $\begingroup$ On the other hand if I assume you mean expected degree to mean average degree over the vertices, the spectral sparsifiers of Batson, Spielman, and Srivastava have average degree $O(1/\varepsilon^2)$. $\endgroup$ – Sasho Nikolov Sep 1 '14 at 16:31
  • $\begingroup$ @SashoNikolov Sorry I missed a lot of clarifications as what I really wanted was to know the literature related to this topics and try to see which fits the problem I'm working on, as an answer to your question I think the sparsified graph should be a weighted subgraph of the original graph, and by the expected degree, yes I mean the average degree over the vertices of the resultant graph. Thanks $\endgroup$ – Magellanea Sep 1 '14 at 18:15
  • $\begingroup$ @SashoNikolov by Batson, Spielman and Srivastava sparsifiers are your referring to the Twice-Ramanujan Sparsifiers ? $\endgroup$ – Magellanea Sep 1 '14 at 18:17
  • $\begingroup$ Yes, that's the one. $\endgroup$ – Sasho Nikolov Sep 1 '14 at 20:53

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.