2019/07/01 by Frank von der Kammer, Frank Kammer, Johannes Meintrup +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Feedback vertex set #Graph #Line graph #Mathematics #Pathwidth #Time complexity #Tree decomposition #Treewidth #Vertex (graph theory) #Vertex cover #cs.DS
paper · pdf · open access · doi:10.48550/arxiv.1907.00676
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2019/07/01 · arxiv created 2020/09/30 · arxiv updated 2020/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
For n-vertex graphs with treewidth k = O(n1/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 ck n (log log n) log^* 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' log n for some problem dependent constant 0 < c' < 1.