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$ Commented Mar 30, 2015 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
    Commented Mar 30, 2015 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$ Commented Mar 30, 2015 at 12:56
  • 1
    $\begingroup$ Sparsifiers like that cannot exist - think of a complete graph and singleton S's. $\endgroup$ Commented Mar 31, 2015 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$
    – user
    Commented Apr 1, 2015 at 11:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.