Width, depth, and space: tradeoffs between branching and dynamic programming (Q2287480)

Summary: \textit{Treedepth} is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth \(d\) cannot be bounded by \((2 - \epsilon)^d \cdot \log^{O(1)} n\) for \textsc{Vertex Cover}, \((3 - \epsilon)^d \cdot \log^{O(1)} n\) for 3-\textsc{Coloring} and \((3 - \epsilon)^d \cdot \log^{O(1)} n\) for \textsc{Dominating Set} for any \(\epsilon > 0\). This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth \(d\): A pure branching algorithm that runs in time \(d^{O(d^2)} \cdot n\) and uses space \(O(d^3 \log d + d \log n)\) and a hybrid of branching and dynamic programming that achieves a running time of \(O(3^d \log d \cdot n)\) while using \(O(2^d d \log d + d \log n)\) space.