Difference between revisions of "Open Problems:101"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{Header |title=Effective Support Size Estimation in the Dual Model |source=wola19 |who=Sorrachai Yingchareonthawornchai }} In this question, the input is the underlying grap...")
 
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Effective Support Size Estimation in the Dual Model
+
|title=Vertex connectivity in the LOCAL model
 
|source=wola19
 
|source=wola19
 
|who=Sorrachai Yingchareonthawornchai
 
|who=Sorrachai Yingchareonthawornchai

Revision as of 21:45, 7 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)$?