Difference between revisions of "Open Problems:29"
(Created page with "{{DISPLAYTITLE:Problem 29: Strong Lower Bounds for Graph Problems}} {{Infobox |label1 = Proposed by |data1 = Krzysztof Onak |label2 = Source |data2 = [[Workshops:Kanpur_2009|K...") |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur09 | |
| − | | | + | |who=Krzysztof Onak |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
A large number of streaming papers consider graph problems. Typically, the input stream is an arbitrarily-ordered sequence of edges. For many problems, one can show that solving the problem, even approximately, requires $\Omega(n)$ bits of space. | A large number of streaming papers consider graph problems. Typically, the input stream is an arbitrarily-ordered sequence of edges. For many problems, one can show that solving the problem, even approximately, requires $\Omega(n)$ bits of space. | ||
| Line 15: | Line 10: | ||
McGregor {{cite|McGregor-05}} shows that there is an algorithm that finds a matching of size $(1-\epsilon) \cdot M(G)$ in a number of passes that is a function of only $\epsilon$. It is plausible that for any constant $k$, there is no $k$-pass $\tilde O(n)$-space algorithm that finds a matching of size greater than $(1-\epsilon_k) \cdot M(G)$ times the optimum, where $\epsilon_k$ is a positive constant. In particular, to the best of my knowledge, no one-pass $\tilde O(n)$-space algorithm that finds a $(1-\epsilon)$-approximation for any constant $\epsilon \in (0,1/2)$ is known. Can one prove lower bounds as suggested above? | McGregor {{cite|McGregor-05}} shows that there is an algorithm that finds a matching of size $(1-\epsilon) \cdot M(G)$ in a number of passes that is a function of only $\epsilon$. It is plausible that for any constant $k$, there is no $k$-pass $\tilde O(n)$-space algorithm that finds a matching of size greater than $(1-\epsilon_k) \cdot M(G)$ times the optimum, where $\epsilon_k$ is a positive constant. In particular, to the best of my knowledge, no one-pass $\tilde O(n)$-space algorithm that finds a $(1-\epsilon)$-approximation for any constant $\epsilon \in (0,1/2)$ is known. Can one prove lower bounds as suggested above? | ||
The question generalizes to other problems. | The question generalizes to other problems. | ||
| − | For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see {{cite|DasSarmaGP-08}} and Rina Panigrahy's question). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space? | + | For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see {{cite|DasSarmaGP-08}} and [[Open_Problems:22|Rina Panigrahy's question]]). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space? |
| − | To the best of my knowledge, the only | + | To the best of my knowledge, computing the BFS tree and computing the diameter are the only problems for which an $n^{1+\Omega(1)}$ lower bound for more than one pass is known {{cite|FeigenbaumKMSZ-08}}. |
| + | |||
| + | == Update == | ||
| + | Guruswami and Onak {{cite|GuruswamiO-13}} showed that the following problems require roughly $n^{1+\Omega(1/p)}$ bits of space in $p$ passes: testing if there is a perfect matching, checking if $v$ and $w$ are at distance at most $2(p+1)$, and checking if there is a directed path from $v$ to $w$, where $v$ and $w$ are known to the algorithm in advance. | ||
Latest revision as of 21:14, 26 June 2013
| Suggested by | Krzysztof Onak |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://sublinear.info/29 |
A large number of streaming papers consider graph problems. Typically, the input stream is an arbitrarily-ordered sequence of edges. For many problems, one can show that solving the problem, even approximately, requires $\Omega(n)$ bits of space. For instance, one can relatively easily prove that finding a constant-factor approximation to the maximum matching problem requires $\Omega(n)$ bits of space. Therefore, in many cases, the desired space complexity is of the form $\tilde O(n)$. Despite this relaxation, it is plausible that for some popular problems, there are barriers that cannot be overcome by (approximate) algorithms that use $n^{1+o(1)}$ space and a small number of passes.
For example, let $M(G)$ be the maximum matching size in the input graph $G$. McGregor [McGregor-05] shows that there is an algorithm that finds a matching of size $(1-\epsilon) \cdot M(G)$ in a number of passes that is a function of only $\epsilon$. It is plausible that for any constant $k$, there is no $k$-pass $\tilde O(n)$-space algorithm that finds a matching of size greater than $(1-\epsilon_k) \cdot M(G)$ times the optimum, where $\epsilon_k$ is a positive constant. In particular, to the best of my knowledge, no one-pass $\tilde O(n)$-space algorithm that finds a $(1-\epsilon)$-approximation for any constant $\epsilon \in (0,1/2)$ is known. Can one prove lower bounds as suggested above? The question generalizes to other problems. For instance, the best known $\tilde O(n)$-space algorithms for simulating random walks require a large number of passes (see [DasSarmaGP-08] and Rina Panigrahy's question). Can one prove for these problems that a small number of passes requires $n^{1+\Omega(1)}$ space?
To the best of my knowledge, computing the BFS tree and computing the diameter are the only problems for which an $n^{1+\Omega(1)}$ lower bound for more than one pass is known [FeigenbaumKMSZ-08].
Update[edit]
Guruswami and Onak [GuruswamiO-13] showed that the following problems require roughly $n^{1+\Omega(1/p)}$ bits of space in $p$ passes: testing if there is a perfect matching, checking if $v$ and $w$ are at distance at most $2(p+1)$, and checking if there is a directed path from $v$ to $w$, where $v$ and $w$ are known to the algorithm in advance.
