Approximation in (poly-) logarithmic space

Abstract

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), uses O(d2 + (d/ε)) log n) bits of space, and achieves an approximation ratio of O((d/ε)nε) for any positive ε ≤ 1 and any constant d ∈ N. In particular, this yields a factor-O(d log n) approximation algorithm which uses O(log2 n) bits of space. As a corollary, we obtain similar bounds on space and approximation ratio for Vertex Cover and several graph deletion problems. For graphs with maximum degree ∆, one can do better. We give a factor-2 approximation algorithm for Vertex Cover which runs in time n O(∆) and uses O(∆ log n) bits of space. For Independent Set on graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O(log n) bits of space. We also devise a factor-O(d2) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time nO(log n) and uses O(log2 n) bits of space. For d-regular graphs, we observe that a known randomized algorithm which achieves an approximation ratio of O(log d) can be derandomized to run in polynomial time and use O(log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.