Problem 101: Vertex Connectivity in the LOCAL Model
|Suggested by||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$.
Question: Can one achieve time $O(\nu k)$?