Editing Open Problems:91
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 15: | Line 15: | ||
'''Question:''' Is it true that for every $n$-vertex hypergraph $H$ and every $\epsilon\in (0,1/2)$, there is a $(1+\epsilon)$-cut-sparsifier $H'$ with at most $O(n/\epsilon^2)$ edges? | '''Question:''' Is it true that for every $n$-vertex hypergraph $H$ and every $\epsilon\in (0,1/2)$, there is a $(1+\epsilon)$-cut-sparsifier $H'$ with at most $O(n/\epsilon^2)$ edges? | ||
β | '''Upper bound:''' The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer {{cite|KoganK-15}}. It is based on the sparsification method of Benczur and Karger | + | '''Upper bound:''' The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer {{cite|KoganK-15}}. It is based on the sparsification method of Benczur and Karger [A. A. Bencz ur and D. R. Karger. Approximating s-t minimum cuts in $O(n^2)$ time. STOC β96]. Another proof can be derived from a paper of Newman and Rabinovich [I. Newman and Y. Rabinovich. On multiplicative Ξ»-approximations and some geometric applications. SIAM Journal on Computing, 42(3):855883, 2013]. |
'''Special cases:''' The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ {{cite|BatsonSS-14}}. | '''Special cases:''' The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ {{cite|BatsonSS-14}}. |