# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 7 Conclusions and Future Work  
We have shown that single-pass dynamic programming algorithms on treedepth, tree or path decompositions without preprocessing of the input must use space exponential in the width/depth, confirming a common suspicion and proving it rigorously for the first time. This complements previous SETH-based arguments about the running time of arbitrary algorithms on low treewidth graphs. We further demonstrate that treedepth allows non-DP linear-time algorithms that only use polynomial space in the depth of the provided decomposition. Both our lower bounds and the provided algorithm for Dominating Set appear as if they could be special cases of a general theory to be developed in future work and we further ask whether our result can be extended to less stringent definitions of \"dynamic programming algorithms\".  
It would be great to be able to characterize exactly which problems can be solved in linear-fpt time using \(\operatorname{poly}(d)\cdot\log n\) space. [PERSON] proved as part of his master thesis [PERSON] (1979) that the ideas presented here can be extended to the framework of [PERSON] and [PERSON] for graph partitioning problems [PERSON] and [PERSON] (2001). Mimicking the development for treewidth would point to extending this result to MSO. Sadly, a proven double exponential dependency on the run-time of model-checking MSO parameterized by the size of a vertex cover implies that no such result is possible [PERSON] and [PERSON] (2001). Is there a characterization that better captures for which problems this is possible? Previous research that might be relevant to this endeavor has investigated the height of the tower in the running time for MSO model-checking on graphs of bounded treedepth [PERSON] (2001).  
Despite the less-than-ideal theoretical bounds of the presented Dominating Set algorithms, the opportunities for heuristic improvements are not to be slighted. Take the pure branching algorithm presented in Section 5. During the branching procedure, we generate all partitions from the root-path starting at the current vertex. However, we actually only have to partition those vertices that are not dominated yet (by virtue of being themselves in the dominating set or being dominated by another vertex on the root-path). A sensible heuristic as to which branch--including the current vertex in the dominating set or not--to explore first, together with a _branch and bound_ routine should keep us from generating partitions of very large sets. A similar logic applies to the mixed dynamic programming/branching algorithm since the tables only have to contain information about sets that are not yet dominated. It might thus be possible to keep the tables a lot smaller than their theoretical bounds indicate.  
Furthermore, it seems reasonable that in practical settings, the nodes near the root of treedepth decompositions are more likely to be part of a minimal dominating set. If this is true, computing a treedepth decomposition would serve as a form of smart preprocessing for the branching, a rough \"plan of attack\", if you will. How much such a _guided branching_ improves upon known branching algorithms in practice is an interesting avenue for further research.  
It is still an open question, proposed by [PERSON] during GROW 2015, whether Dominating Set can be solved in time \((3-e)^{d}\cdot\operatorname{poly}(n)\) when parameterized by treedepth. Our lower bound result implies that if such an algorithm exists, it cannot be a straightforward dynamic programming algorithm.  
All authors' contributions are approximately of equal size.  
Research funded by DFG-Project RO 927/13-1 \"Pragmatic Parameterized Algorithms\". [PERSON] was supported in part by MOST-DAAD Sandwich Program under grant no. 103-2911-1-194-506.  
The authors declare no conflict of interest.