Difference between revisions of "Open Problems:91"
(adding some references) |
|||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=warwick18 | |source=warwick18 | ||
|who=Robert Krauthgamer | |who=Robert Krauthgamer | ||
| Line 18: | Line 17: | ||
'''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 {{cite|BenczurK-96}}. Another proof can be derived from a paper of Newman and Rabinovich {{cite|NewmanR-13}}. | '''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 {{cite|BenczurK-96}}. Another proof can be derived from a paper of Newman and Rabinovich {{cite|NewmanR-13}}. | ||
| − | '''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)$ | + | '''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}}. |
This bound easily extends to $\rank(H)=3$, because every hyperedge in $H$ can be replaced by a triangle (3 edges of cardinality 2) with edge weights $1/2$. For intermediate values of $\rank(H)$, the known upper bound is $O((\rank(H)+\log n) n/\epsilon^2)$ {{cite|KoganK-15}}. | This bound easily extends to $\rank(H)=3$, because every hyperedge in $H$ can be replaced by a triangle (3 edges of cardinality 2) with edge weights $1/2$. For intermediate values of $\rank(H)$, the known upper bound is $O((\rank(H)+\log n) n/\epsilon^2)$ {{cite|KoganK-15}}. | ||
| − | Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$ | + | Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow {{cite|Pogrow-17}}. Note that this family clearly contains all ordinary graphs. |
| − | '''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. | + | '''Lower bound:''' The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges {{cite|AndoniCKQWZ-16}}. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan {{cite|CarlsonKST-17}}. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$). |
| − | '''Remark:''' The above | + | '''Remark:''' The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparsifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger. |
Latest revision as of 04:32, 20 August 2019
| Suggested by | Robert Krauthgamer |
|---|---|
| Source | Warwick 2018 |
| Short link | https://sublinear.info/91 |
Informally, a cut-sparsifier of a hypergraph $H$ is a sparse hypergraph $H'$ on the same vertex set, whose cuts approximate those of $H$. The two “competing” quantities are the approximation factor and the size of the sparsifier $H'$ (for worst-case hypergraph $H$ on $n$ vertices). More formally, Let $H=(V,E,w)$ be an edge-weighted hypergraph. The weight of the cut $(S,\bar S)$ (i.e., for nontrivial $S\subset V$) is defined as $$ w_H(S,\bar S) := \sum_{e\in E: e\cap S\neq\emptyset, e\cap\bar S \neq\emptyset} w(e) . $$ A $(1+\epsilon)$-cut-sparsifier of $H$ is a hypergraph $H'=(V,E',w')$ (on the same vertex-set) such that $$ \forall S\subset V, \qquad w_{H'}(S,\bar S) \in (1\pm\epsilon) w_H(S,\bar S) . $$
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 [KoganK-15]. It is based on the sparsification method of Benczur and Karger [BenczurK-96]. Another proof can be derived from a paper of Newman and Rabinovich [NewmanR-13].
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)$ [BatsonSS-14]. This bound easily extends to $\rank(H)=3$, because every hyperedge in $H$ can be replaced by a triangle (3 edges of cardinality 2) with edge weights $1/2$. For intermediate values of $\rank(H)$, the known upper bound is $O((\rank(H)+\log n) n/\epsilon^2)$ [KoganK-15]. Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow [Pogrow-17]. Note that this family clearly contains all ordinary graphs.
Lower bound: The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges [AndoniCKQWZ-16]. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan [CarlsonKST-17]. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
Remark: The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparsifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.
