Open Problems:101 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Vertex connectivity in the LOCAL model to Open Problems:101 without leaving a redirect

2019-08-26T18:36:22Z

Krzysztof Onak moved page Waiting:Vertex connectivity in the LOCAL model to Open Problems:101 without leaving a redirect

Krzysztof Onak: Updating the header

2019-08-26T18:36:07Z

Updating the header

Krzysztof Onak at 02:35, 25 August 2019

2019-08-25T02:35:56Z

Ccanonne at 21:45, 7 August 2019

2019-08-07T21:45:45Z

Ccanonne: 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..."

2019-08-07T21:40:32Z

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..."

New page

{{Header
|title=Effective Support Size Estimation in the Dual Model
|source=wola19
|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

- 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}}.

'''Question:''' Can one achieve time $O(\nu k)$?

← Older revision	Revision as of 18:36, 26 August 2019
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=wola19
 |who=Sorrachai Yingchareonthawornchai

@@ Line 4: / Line 4: @@
 |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
-- if $\bot$ is the output, there is no $S$ such that $v\in S$ with $|S| \leq \nu$ and $|N(S)| < k$;
+* 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$.
+* 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}}.
 '''Question:''' Can one achieve time $O(\nu k)$?