The notion of

Algorithmically, treedepth is interesting since it is structurally more restrictive than pathwidth. Treedepth bounds the pathwidth and treewidth of a graph, i.e.,

Lokshtanov, Marx and Saurabh showed—assuming the Strong Exponential Time Hypothesis (SETH)—that for 3-

It can be noted that there have been previous formalizations of common algorithmic paradigms in an attempt to investigate what different kinds of algorithms can and cannot achieve, including dynamic programming [

To formalize the notion of a dynamic programming algorithm on tree, path and treedepth decompositions, we consider algorithms that take as input a tree-, path- or treedepth decomposition of width/depth

They pass a

they use

they do not modify the decomposition, including re-arranging it.

While these three constraints might look stringent, they include pretty much all dynamic programming algorithm for hard optimization problems on tree or path decompositions. For that reason, we will refer to this type of algorithms simply as

To show the aforementioned space lower bounds, we introduce a simple machine model that models DP algorithms on treedepth decompositions and construct superexponentially large

Consequently, any algorithmic benefit of treedepth over pathwidth and treewidth must be obtained by non-DP means. We demonstrate that treedepth allows the design of branching algorithms whose space consumption grows only polynomially in the treedepth and logarithmic in the input size. Such space-efficient algorithms are quite easy to obtain for 3-

While applying branching to treedepth seems natural, it is unclear whether it could be applied to treewidth or pathwidth. Recent work by Drucker, Nederlof and Santhanam suggests that, relative to a collapse of the polynomial hierarchy,

The idea of using treedepth to improve space consumption is not novel. Fürer and Yu demonstrated that it is possible to count matchings using polynomial space in the size of the input [

In our opinion, algorithms based on algebraization have two disadvantages: On the theoretical side, the dependency of the running and space consumption on the input size is often at least

We write

We assume that the input graphs are connected, which allows us to presume that the treedepth decomposition is always a tree. Furthermore, let

An

In this section, we introduce the basic machinery to formalize the notion of dynamic programming algorithms and how we prove lower bounds based on this notion.

First of all, we need to establish what we mean by

Any single-pass dynamic programming algorithm that solves a DP decision problem on tree, path or treedepth decompositions of width/depth

The theorem of Myhill and Nerode is best known from formal language theory where it is used to show that a language is not regular, but is more general in its original form. For example, if we look at the language

The following notion of a

Let

The following lemma still holds if we replace “treedepth” by “pathwidth” or “treewidth”.

Before proving Lemma 1 let us look at a simple example. The DP decision problem consists of graphs that have components of size

(of Lemma 1) Assume, on the contrary, that such a DPTM

By definition, for every

Notice that

In this section we prove space lower bounds for dynamic programming algorithms as defined in

For any

To construct the graphs

Now for every subset

Surprisingly, the construction to prove a lower bound for

For every

Consider

We construct

We claim that

The size of the family

For any

For a subset

Let

Now assume that we start with a dominating set

Let us now show that our boundaried graphs work as intended and calculate the appropriate parameters

Choosing

That branching might be a viable algorithmic design strategy for low-treedepth graphs can easily be demonstrated for problems like 3-

The task of designing a similar algorithm for

We split the proof of Theorem 4 into lemmas for correctness, running time and used space.

If we look at a minimal dominating set

It is clear that the algorithm will call itself until a leaf is reached. Let

We assume now

The running time when

There are at most

We have seen that it is possible to solve

We divide the proof into lemmas as before.

Notice that the associative array

Assume

Assume now that

To prove the running time of Algorithm 2 we will need the values

Let

On a call on which

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

It would be great to be able to characterize exactly which problems can be solved in linear-fpt time using

Despite the less-than-ideal theoretical bounds of the presented

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

It is still an open question, proposed by Michał Pilipczuk during GROW 2015, whether

All authors’ contributions are approximately of equal size.

Research funded by DFG-Project RO 927/13-1 “Pragmatic Parameterized Algorithms”. Li-Hsuan Chen was supported in part by MOST-DAAD Sandwich Program under grant no. 103-2911-I-194-506.

The authors declare no conflict of interest.

The gadget

The gadget