First of all, we will leverage the well-known XOR trick [1]}, [2]} for deciding
if a boundary of some subset of vertices is non-empty.
We now briefly describe this method.
Suppose each \(e\in E\)  is assigned a random bit-string \(x_e\)  of length \(\Theta (\log {n})\)  that fits in \(O(1)\)  machine words.
Let \(x_v=\bigoplus _{vw=e\in E} x_e\)  denote the XOR of the respective bit-strings of edges incident to \(v\) .
Then, one can prove that, given \(S\subseteq V\) , with high probability the XOR \(\bigoplus _{u\in S}x_u\)  is non-zero if and only if \(\partial _{G}(S)\ne \emptyset \) . So, emptiness of \(\partial _G(S)\)  can be tested in \(O(|S|)\)  time.
