Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming

Algorithms

Li-Hsuan Chen¹  Fernando Sánchez Villaamil²  Peter Rossmanith²  Felix Reidl³ 

[1] AROBOT Innovation, Taiwan;Department of Computer Science, RWTH Aachen University, 52062 Aachen, Germany;Royal Holloway, University of London, TW20 0EX, UK;

关键词: treewidth;    treedepth;    dynamic programming;    branching algorithm;    space lower bound;   

DOI  :  10.3390/a11070098

来源: DOAJ

【 摘 要 】

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−ϵ)d·logO(1)n for Vertex Cover, (3−ϵ)d·logO(1)n for 3-Coloring and (3−ϵ)d·logO(1)n for Dominating Set for any ϵ>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 dO(d2)·n and uses space O(d3logd+dlogn) and a hybrid of branching and dynamic programming that achieves a running time of O(3dlogd·n) while using O(2ddlogd+dlogn) space.

【 授权许可】

Unknown