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

Autor: Chen, Li-Hsuan, Reidl, Felix, Rossmanith, Peter, Sánchez Villaamil, Fernando
Předmět:
Zdroj: Algorithms; Jul2018, Vol. 11 Issue 7, p98, 1p
Abstrakt: 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 · log O (1) n for Vertex Cover, (3 − ϵ) d · log O (1) n for 3-Coloring and (3 − ϵ) d · log O (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 d O (d 2) · 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 · n) while using O (2 d d log d + d log n) space. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje