Space-Efficient Vertex Separators for Treewidth

Frank Kammer, Johannes Meintrup, Andrej Sajenko

For $n$-vertex graphs with treewidth $k=O(n^{1/2-\epsilon })$ and an arbitrary $\epsilon >0$, we present a word-RAM algorithm to compute vertex separators using only $O(n)$ bits of working memor…