Open Problems in Sublinear Algorithms - User contributions [en]

Open Problems:91

2018-07-24T20:06:59Z

176.74.251.242:

{{Header
|title=Cut-Sparsification of Hypergraphs
|source=warwick18
|who=Robert Krauthgamer
}}
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 {{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)$ {{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}}.
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}}. 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 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 sparisifier 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.

Open Problems:91

2018-07-24T20:04:45Z

176.74.251.242:

{{Header
|title=Cut-Sparsification of Hypergraphs
|source=warwick18
|who=Robert Krauthgamer
}}
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 {{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)$ {{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}}.
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}}. 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 considers size to be the number of hyperedges. 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 sparisifier 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.