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

CC BY-SA 3.0
2014-09-01T16:26:09.050Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-09-01T16:31:07.957Z
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)$.
Sasho Nikolov
CC BY-SA 3.0
2014-09-01T18:15:33.513Z
@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
Magellanea
CC BY-SA 3.0
2014-09-01T18:17:10.450Z
@SashoNikolov by Batson, Spielman and Srivastava sparsifiers are your referring to the _Twice-Ramanujan Sparsifiers_ ?
Magellanea
CC BY-SA 3.0
2014-09-01T20:53:56.383Z
Yes, that's the one.
Sasho Nikolov
<graph-theory><spectral-graph-theory>
Graph sparsification
Magellanea
# Graph sparsification

(Asked by: username_0 on 2014-08-31)

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?

**Tags:** graph-theory, spectral-graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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)$.  
> **username_0**: @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  
> **username_0**: @SashoNikolov by Batson, Spielman and Srivastava sparsifiers are your referring to the _Twice-Ramanujan Sparsifiers_ ?  
> **username_1**: Yes, that's the one.  

---

## 0 answers

