<p>Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph which can be described using as few as $|V|\operatorname{polylog}|V|$ bits - for every $S\subseteq V$ one can still answer the question: "How many edges in $G$ are in the cut $(S,V-S)$ up to a multiplicative $(1\pm \varepsilon)$?".</p>

<p>You're given a dense graph $G=(V,E)$. Can you produce a sparse graph on the same vertex set, where - only knowing the sparse graph - for every $S\subseteq V$, one can still answer: "How many neighbors does $S$ have in $G$ up to a multiplicative $(1\pm\varepsilon)$?</p>

CC BY-SA 3.0
2015-03-30T00:23:32.437Z
Cut sparsifiers for edge-cuts work by using weights on the sparse graph. It is not clear how this can be done for vertex-cuts. Looking at Julia Chuzhoy's vertex cut sparsifier paper may be useful. http://arxiv.org/abs/1204.2844
Chandra Chekuri
CC BY-SA 3.0
2015-03-30T00:34:43.167Z
Are there restrictions on the edge weight values or other requirements on the sparse graph? Actually, it seems to me that if arbitrary edge weights are allowed (as long as they are reasonably sized), one can encode the original $G$ in the edge weights of a sparse graph? (Though I understand this is not how cut sparsifiers work?)
Joe Bebel
CC BY-SA 3.0
2015-03-30T12:56:12.107Z
I edited the question so it mentions that in the usual definition of sparsifiers the sparse graph indeed has edge weights that can be described using not too many bits. For my question there's no reason to use edge weights.
Dana Moshkovitz
CC BY-SA 3.0
2015-03-31T15:12:09.290Z
Sparsifiers like that cannot exist - think of a complete graph and singleton S's.
Dana Moshkovitz
CC BY-SA 3.0
2015-04-01T11:08:45.007Z
@DanaMoshkovitz: I agree that there are most likely no sparsifiers like this, but I do not see how a clique proves it. You may imagine that your sparsifier, given a clique, outputs a vertex-weighted sparse graph where the weights indicates the number of neighbors.
user
<graph-algorithms><spectral-graph-theory><sparse-matrix>
Are there sparsifiers that approximate vertices rather than edges?
Dana Moshkovitz
# Are there sparsifiers that approximate vertices rather than edges?

(Asked by: username_0 on 2015-03-29)

Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph which can be described using as few as $|V|\operatorname{polylog}|V|$ bits - for every $S\subseteq V$ one can still answer the question: "How many edges in $G$ are in the cut $(S,V-S)$ up to a multiplicative $(1\pm \varepsilon)$?".

You're given a dense graph $G=(V,E)$. Can you produce a sparse graph on the same vertex set, where - only knowing the sparse graph - for every $S\subseteq V$, one can still answer: "How many neighbors does $S$ have in $G$ up to a multiplicative $(1\pm\varepsilon)$?

**Tags:** graph-algorithms, spectral-graph-theory, sparse-matrix

> **Comments:**
> **username_1**: Cut sparsifiers for edge-cuts work by using weights on the sparse graph. It is not clear how this can be done for vertex-cuts. Looking at Julia Chuzhoy's vertex cut sparsifier paper may be useful. http://arxiv.org/abs/1204.2844  
> **username_2**: Are there restrictions on the edge weight values or other requirements on the sparse graph? Actually, it seems to me that if arbitrary edge weights are allowed (as long as they are reasonably sized), one can encode the original $G$ in the edge weights of a sparse graph? (Though I understand this is not how cut sparsifiers work?)  
> **username_0**: I edited the question so it mentions that in the usual definition of sparsifiers the sparse graph indeed has edge weights that can be described using not too many bits. For my question there's no reason to use edge weights.  
> **username_0**: Sparsifiers like that cannot exist - think of a complete graph and singleton S's.  
> **username_3**: @DanaMoshkovitz: I agree that there are most likely no sparsifiers like this, but I do not see how a clique proves it. You may imagine that your sparsifier, given a clique, outputs a vertex-weighted sparse graph where the weights indicates the number of neighbors.  

---

## 0 answers

