size.

\[def:collection-scheme-optimal\] A class/collection of helper selection schemes $\mathcal{A}=\{A_1,A_2,\cdots\}$ is optimal if for any $(n,k,d)$ values, we can always find one $A\in\mathcal{A}$ such that $A$ is optimal.

By the above definitions, it is thus of significant practical/theoretic interest to find an optimal helper selection scheme $A$ for a given $(n,k,d)$ value, and to characterize the smallest optimal helper scheme class $\mathcal{A}$.

While we have been able to devise an optimal helper selection scheme $A$ for some $(n,k,d)$ combinations, see our results in Section \[sec:results\], the problem of finding a small optimal helper scheme class $\mathcal{A}$ remains unsolved. Instead, we will characterize a small class of helper schemes that is [*weakly optimal:*]{}

\[def:scheme-weakly-optimal\] For any given $(n,k,d)$ value, a helper selection scheme $W$ is *weakly optimal*, if the Boolean statement “there exists a DHS scheme $A$ such that $$\begin{aligned}
\min_{G\in \mathcal{G}_A}\min_{t\in \operatorname{DC}(G)}\operatorname{mincut}_G(s,t)> \min_{G\in \mathcal{G}}\min_{t\in \operatorname{DC}(G)}\operatorname{mincut}_G(s,t)\nonumber\end{aligned}$$ for some $(\alpha_1,\beta_1)$” implies $$\begin{aligned}
\min_{G\in \mathcal{G}_W}\min_{t\in \operatorname{DC}(G)}\operatorname{mincut}_G(s,t)> \min_{G\in \mathcal{G}}\min_{t\in \operatorname{DC}(G)}\operatorname{mincut}_G(s,t)\nonumber\end{aligned}$$ for some $(\alpha_2,\beta_2)$.

Comparing Definitions \[def:scheme-optimal\] and \[def:scheme-weakly-optimal\], the difference is that the absolute optimality needs to be the best among all DHS schemes, while the weak optimality definition uses the BHS as a baseline and only requires that if the optimal scheme $A^*$ can 