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

  • $\begingroup$ 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. arxiv.org/abs/1204.2844 $\endgroup$ – Chandra Chekuri Mar 30 '15 at 0:23
  • $\begingroup$ 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?) $\endgroup$ – Joe Bebel Mar 30 '15 at 0:34
  • $\begingroup$ 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. $\endgroup$ – Dana Moshkovitz Mar 30 '15 at 12:56
  • 1
    $\begingroup$ Sparsifiers like that cannot exist - think of a complete graph and singleton S's. $\endgroup$ – Dana Moshkovitz Mar 31 '15 at 15:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Edouard Bonnet Apr 1 '15 at 11:08

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.