Space-Efficient Vertex Separators for Treewidth

For $n$-vertex graphs with treewidth $k=O(n^{1\mathrm{/}2-ϵ})$ and an arbitrary $ϵ>0$, we present a word-RAM algorithm to compute vertex separators using only $O(n)$ bits of working memory. As an application of our algorithm, we give an $O(1)$-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in $c^{k}n(\log \log n){\log }^{\ast }n$ time using $O(n)$ bits for some constant $c>0$. We finally use the tree decomposition obtained by our algorithm to solve Vertex Cover, Independent Set, Dominating Set, MaxCut and $q$-Coloring by using $O(n)$ bits as long as the treewidth of the graph is smaller than $c^{\mathrm{\prime }}\log n$ for some problem dependent constant $0<c^{\mathrm{\prime }}<1$.