Abstract
Dynamic programming is often useful to speed up FPT algorithms. It uses, however, often a lot of memory. We show that the high space complexity is unavoidable by tight lower bounds on several problems.
Dynamic programming is often useful to speed up FPT algorithms. It uses, however, often a lot of memory. We show that the high space complexity is unavoidable by tight lower bounds on several problems.