Difference between revisions of "Open Problems:101"
m (Krzysztof Onak moved page Waiting:Vertex connectivity in the LOCAL model to Open Problems:101 without leaving a redirect) |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=wola19 | |source=wola19 | ||
|who=Sorrachai Yingchareonthawornchai | |who=Sorrachai Yingchareonthawornchai | ||
}} | }} | ||
| − | |||
In this question, the input is the underlying graph $G=(V,E)$, as well as parameters $\nu,k$ and vertex $v\in V$. The goal is to output either $\bot$ or a subset $S\subseteq V$, such that | In this question, the input is the underlying graph $G=(V,E)$, as well as parameters $\nu,k$ and vertex $v\in V$. The goal is to output either $\bot$ or a subset $S\subseteq V$, such that | ||
| − | + | * if $\bot$ is the output, there is no $S$ such that $v\in S$ with $|S| \leq \nu$ and $|N(S)| < k$; | |
| − | + | * if the output is a set $S$, then $|N(S)| < k$. | |
It is known that this problem can be solved with $O(\nu k)$ queries, and either time $O(\nu^{3/2} k)$ (deterministic) or $O(\nu k^2)$ (randomized) {{Cite|NanongkaiSY-19a|NanongkaiSY-19b|ForsterY-19}}. | It is known that this problem can be solved with $O(\nu k)$ queries, and either time $O(\nu^{3/2} k)$ (deterministic) or $O(\nu k^2)$ (randomized) {{Cite|NanongkaiSY-19a|NanongkaiSY-19b|ForsterY-19}}. | ||
'''Question:''' Can one achieve time $O(\nu k)$? | '''Question:''' Can one achieve time $O(\nu k)$? | ||
Latest revision as of 18:36, 26 August 2019
| Suggested by | Sorrachai Yingchareonthawornchai |
|---|---|
| Source | WOLA 2019 |
| Short link | https://sublinear.info/101 |
In this question, the input is the underlying graph $G=(V,E)$, as well as parameters $\nu,k$ and vertex $v\in V$. The goal is to output either $\bot$ or a subset $S\subseteq V$, such that
- if $\bot$ is the output, there is no $S$ such that $v\in S$ with $|S| \leq \nu$ and $|N(S)| < k$;
- if the output is a set $S$, then $|N(S)| < k$.
It is known that this problem can be solved with $O(\nu k)$ queries, and either time $O(\nu^{3/2} k)$ (deterministic) or $O(\nu k^2)$ (randomized) [NanongkaiSY-19a,NanongkaiSY-19b,ForsterY-19].
Question: Can one achieve time $O(\nu k)$?
