Treffer: Space-Efficient Vertex Separators for Treewidth.

For n-vertex graphs with treewidth k = O (n 1 / 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 ∗ n time using O(n) bits for some constant c > 0 . Together with the result of Banerjee et al. (Proceedings of 21st international conference on computing and combinatorics (COCOON 2015). LNCS, vol 9198, Springer, pp 349–360, 2015. https://doi.org/10.1007/978-3-319-21398-9%5f28) we are able to compute a solution for all monadic-second-order problems (MSO) with O (n + τ (k) · p (log p n) log n) bits in O (τ (k) · n 2 + (2 / log p)) time where k is the treewidth of the given graph, p is some arbitrary parameter with 2 ≤ p ≤ n and τ is some function depending on the MSO formula. We finally use the tree decomposition obtained by our algorithm to solve Vertex Cover, Independent Set, Dominating Set, MaxCut and q-Coloring by using polynomial time and O(n) bits as long as the treewidth of the graph is smaller than c ′ log n for some problem dependent constant 0 < c ′ < 1 . [ABSTRACT FROM AUTHOR]

Copyright of Algorithmica is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)