Treewidth Parameterized by Feedback Vertex Number

In this work, we focus on computing optimal tree decomposition. We overcome the difficulties of obtaining a single exponential time algorithm by moving to a larger parameter. The arguably most natural parameter that measures “tree-likeness” and is larger than treewidth is the feedback vertex number. It is the smallest number of vertices that need to be removed from a graph to turn it into a forest. Bodlaender, Jansen, and Kratsch [20] studied feedback vertex number in the context of kernelization algorithms for treewidth computation. The main result of our work is the following.

Theorem 1.1 directly improves a previously known result, that an optimal tree decomposition for an $n$-vertex graph $G$ can be computed in $2^{𝒪(\mathrm{𝗏𝖼𝗇}(G))}\cdot n^{𝒪(1)}$ time (if it exists) [26, 37], where $\mathrm{𝗏𝖼𝗇}(G)$ is the vertex cover number of $G$, which is the smallest number of vertices that need to be removed from a graph to remove all of its edges, and hence always at least as large as the feedback vertex number. To the best of our knowledge, the only other known result for treewidth computation that uses a different parameter to obtain single exponential running time is by Fomin et al. [37], who showed that an optimal tree decomposition can be computed in $2^{𝒪(\mathrm{𝗆𝗐}(G))}\cdot n^{𝒪(1)}$, where $\mathrm{𝗆𝗐}(G)$ is the modular width of $G$. We remark that the modular width can be upper-bounded by a (non-linear) function of the vertex cover number, but is incomparable to both the treewidth and the feedback vertex number of a graph. It follows that our result improves the best-known algorithms for computing optimal tree decompositions (in terms of the exponential part of the running time) for graphs $G$ where

where $\mathrm{𝗍𝗐}(G)$ denotes the treewidth of $G$. On a different note, since $\mathrm{𝖿𝗏𝗇}(G)$ is an upper bound on $\mathrm{𝗍𝗐}(G)$, our algorithm can also be seen either as an important step towards a positive resolution of the open problem of finding an $2^{𝒪(\mathrm{𝗍𝗐}(G))}\cdot n^{𝒪(1)}$ time algorithm for computing an optimal tree decomposition, or, if its answer is negative, then a mark of the tractability border of single exponential time algorithms for the computation of treewidth.

Our algorithm constitutes a significant extension of a dynamic programming algorithm by Chapelle et al. [26] for computing optimal tree decompositions which runs in $2^{𝒪(\mathrm{𝗏𝖼𝗇}(G))}\cdot n^{𝒪(1)}$ time. The building blocks of the algorithm are fairly simple and easy to implement, however the analysis is quite technical and involved. First of all, our algorithm needs to have access to a minimum feedback vertex set, that is, a set of vertices of minimum cardinality, such that the removal of those vertices turns the graph into a forest. It is well-known that such a set can be computed in ${2.7}^{\mathrm{𝖿𝗏𝗇}(G)}\cdot n^{𝒪(1)}$ time (randomized) [49] or in ${3.6}^{\mathrm{𝖿𝗏𝗇}(G)}\cdot n^{𝒪(1)}$ deterministic time [45]. As a second step, we apply the kernelization algorithm by Bodlaender, Jansen, and Kratsch [20] to reduce the number of vertices in the input graph to $𝒪(\mathrm{𝖿𝗏𝗇}{(G)}^4)$. We remark that this kernelization algorithm needs a minimum feedback vertex set as part of the input and ensures that this set remains a feedback vertex set for the reduced instance [20]. This second step is neither necessary for the correctness of our algorithm nor to achieve the claimed running time bound, but it ensures that the polynomial part of our running time is bounded by the maximum of the running time of the kernelization algorithm and the polynomial part of the running time needed to compute a minimum feedback vertex set. Neither Bodlaender, Jansen, and Kratsch [20], Li and Nederlof [49], nor Kociumaka and Pilipczuk [45] specify the polynomial part of the running time of their respective algorithms. However, an inspection of the analysis for the kernelization algorithm suggests that its running time is in $𝒪(n^5)$ and it is known that a minimum feedback vertex set can be computed in $2^{𝒪(\mathrm{𝖿𝗏𝗇}(G))}\cdot n^2$ time [25].

In the following, we give a brief overview of the main ingredients of our algorithm. The main purpose of this overview is to convey an intuition and an idea of how the algorithm works; it is not meant to be completely precise.

• $\mathrm{■}$

  Chapelle et al. [26] introduced notions and terminology to formalize how a (rooted) tree decomposition interacts with a minimum vertex cover. We adapt and extend those notions for minimum feedback vertex sets. Inspired by the well-known concept of nice tree decompositions [21], we define a class of rooted tree decompositions that interact with a given feedback vertex set in a “nice” way. We call those tree decompositions $S$-nice, where $S$ denotes the feedback vertex set. In $S$-nice tree decompositions, we classify each node $t$ by which vertices of the feedback vertex set are contained in the bag and which are only contained in bags of nodes in the subtree rooted at $t$. We show that nodes of the same class form (non-overlapping) paths in the tree decomposition.

• $\mathrm{■}$

  We give algorithms to compute candidates of bags for the top and the bottom node of a path that corresponds to a given node class. Here, informally speaking, we differentiate between the cases where nodes (and their neighbors) have “full” bags or not, where we consider a bag to be full if adding another vertex to it increases the width of the tree decomposition. We need two novel algorithmic approaches for the two cases.

• $\mathrm{■}$

  We give an algorithm to compute the maximum width of any bag “inside” a path that corresponds to a given node class. This algorithm needs as input the bag of the top node and the bottom node of the path, and the set of vertices that should be contained in some bags of the path.

• $\mathrm{■}$

  The above-described algorithm allows us to perform dynamic programming on the node classes. Informally, we show that node classes form a partially ordered set. This means that for a given node class, we can look up a partial tree decomposition where the root belongs to a preceding (according to the poset) node class in a dynamic programming table. Then we use the above-described algorithm to extend the looked-up tree decomposition to one where the root has the given node class.

We show that in the above-described way, we can find a tree decomposition of width $k$ whenever one exists. To this end, we introduce (additional) novel classes of tree decompositions that have properties that we can exploit algorithmically. We introduce so-called slim tree decompositions, which, informally speaking, have a minimum number of full nodes and some additional properties. Furthermore, we introduce top-heavy tree decompositions, where, informally speaking, vertices are pushed into bags that are as close to the root as possible. We show that there exists tree decompositions with minimum width that are $S$-nice, slim, and top-heavy. Lastly, we give a number of ways to modify tree decompositions. We will show that we can modify any optimal tree decomposition that is $S$-nice, slim, and top-heavy into one that our algorithm is able to find.

Due to space constraints, we defer considerable amounts of technical details to a full version of this work [41]. In Section 2 we give an overview of the main parts of the algorithm. Afterwards, we introduce the most important concepts and give some details on how the dynamic programming table looks like. The correctness proof and the running time analysis is deferred to the full version. Moreover, the full version contains expanded related work and additional illustrations.

Given a rooted tree decomposition $𝒯=(T,{\{X_t\}}_{t\in V(T)})$ of a graph $G$ and a minimum feedback vertex set $S$ for $G$, the feedback vertex set interacts with the bags of $𝒯$ is a very specific way. Given a bag $X_t$ of some node in $t$, we use $X_t^S=X_t\cap S$ to denote the vertices from $S$ that are inside the bag $X_t$. We use $L_t^S\subseteq S$ to denote the set of vertices from $S$ that are only in bags $X_{t^{\prime }}$ “below” $X_t$. More formally, bags $X_{t^{\prime }}$ of nodes $t^{\prime }$ that are descendants of node $t$. We use $R_t^S=S\setminus (L_t^S\cup X_t^S)$ to denote the set of vertices in $S$ that are only in bags of nodes that are outside the subtree of $𝒯$ rooted at $t$. These three sets build a so-called $S$-trace, a concept introduced by Chapelle et al. [26]. One can show that the nodes in a tree decomposition that share the same $S$-trace partition the tree decomposition into path segments [26]. These path segments (or the corresponding $S$-traces) form a partially ordered set which, informally speaking, allows us to design a bottom-up dynamic programming algorithm that constructs a rooted tree decomposition for $G$ from the leaves to the root.

A similar approach was used by Chapelle et al. [26] to obtain a dynamic programming algorithm that has single exponential running time in the vertex cover number of the input graph. They use a minimum vertex cover instead of a minimum feedback vertex set to define $S$-traces. We extend this idea to work for feedback vertex sets, which requires a significant extension of almost all parts of the algorithm.

The main idea of the overall algorithm is the following. We give a polynomial-time algorithm to compute a partial rooted tree decomposition containing nodes corresponding to a directed path of an $S$-trace and, informally speaking, some additional nodes that only cover vertices from the forest $G-S$. We combine this partial rooted tree decomposition with one for the preceding directed paths according to the above-mentioned partial order. In other words, intuitively, we give a subroutine to compute partial tree decompositions for directed paths corresponding to $S$-traces, and try to assemble them to a rooted tree decomposition for the whole graph. We start with the directed paths that do not have any predecessor paths and then try to extend them until we cover all vertices. We save the partial progress we made in a dynamic programming table. The overall algorithm is composed out of fairly simple subroutines, which makes the algorithm easy to implement. However, a very sophisticated analysis is necessary to prove its correctness and the desired running time bound.

In order to bound the number of dynamic programming table look-ups that we need to compute a new entry, we need to be able to assume that the rooted tree decomposition we are aiming to compute behaves nicely (in a very similar sense as in the well-known concept of nice tree decompositions [21]) with respect to the vertices in $S$. To this end, we introduce the concept of $S$-nice tree decompositions and we prove that every graph $G$ admits an $S$-nice tree decomposition with minimum width for every choice of $S$.

The main technical difficulty is to compute the part of the rooted tree decomposition that contains the nodes corresponding to a directed path of an $S$-trace. As described before, these parts are the main building blocks with which we assemble our tree decomposition for the whole graph.

Our approach here is to compute candidates for the bags of the top node and the bottom node of the directed path corresponding to an $S$-trace. Intuitively, since the $S$-trace specifies where in the tree decomposition the other vertices from $S$ are located and since we know that $G-S$ is a forest, we have some knowledge on how these bags need to look like. If the bag $X$ we are computing is for a node that, when removed, splits the tree decomposition into few parts, then we can “guess” which vertices of $S$ are located in which of the different parts in an optimal tree decomposition. To this end, we adapt the concept of “introduce nodes”, “forget nodes”, and “join nodes” for $S$-nice tree decompositions. A consequence is that if a node does not share its bag $X$ with any neighboring node, then, when the node is removed, the tree decomposition splits into at most three relevant parts (that is, parts that contain bags with vertices from $S$ that are not in $X$). In other word, the bag $X$ acts as a separator for at most three parts of $S$. This allows us to compute a candidate for $X$ in a greedy fashion, and argue that we can modify an optimal tree decomposition to agree with our choice for $X$. An important property that we need for this is, that neighboring bags are not “full”, that is, their size is not $\mathrm{𝗍𝗐}(G)+1$, which gives us flexibility to shuffle around vertices.

However, if the optimal tree decomposition contains a large subtree of nodes that all have the same bag and that are all full, then removing those nodes can split the tree decomposition into an unbounded number of parts that each can contain a different subset of $S$. Here, informally speaking, we cannot afford to “guess” anymore how the vertices of $S$ are distributed among the parts and we cannot shuffle around vertices. Hence, we have to find a way to compute a candidate bag for this case where we do not have to change the tree decomposition to agree with our choice.

To resolve this issue, we need to refine the concept of $S$-nice tree decompositions. We introduce the slim $S$-nice tree decompositions that, informally speaking, ensure subtrees of the tree decomposition where all nodes have the same full bag have certain desirable properties that allow us to compute candidate bags efficiently. We prove that there are slim $S$-nice tree decomposition of minimal width for all graphs and all choices of $S$. Furthermore, we prove (implicitly) that we can bound the size of the search-space for a potential bag by a function that is single exponential in the feedback vertex number. Therefore, we will able to provide small “advice strings”, that lead our algorithm for this case to a candidate bag and we can prove that there is an advice string that will lead the algorithm to the correct bag.

Since we need to modify the optimal tree decomposition in order to agree with the bags that we compute, we have to make sure that later modifications do not invalidate earlier choices for bags. To ensure this, we introduce so-called top-heavy slim $S$-nice tree decompositions. Informally speaking, we try to push all vertices that are not in $S$ into bags as close to the root as possible. Intuitively, this ensures that if we make modifications to those tree decompositions to make them agree with our bag choices, those modifications do not affect bags that are sufficiently far “below” the parts of the tree decomposition that we modify.

Now, having access to the bag of the top node and the bottom node of a directed path corresponding to some $S$-trace, we have to decide which other vertices (that are not in $S$) we wish to put into bags that are attached to that path. Here, we also have to make sure that our decisions are consistent. We will compute a three-partition of the complete vertex set: one part that represents the vertices that are contained in some bag of the directed path or a bag that is attached to it, one part of vertice that are only in bags “below” the directed path, and the last part with the remaining vertices, that is, the vertices that are only in bags outside of the subtree of the tree decomposition that is rooted at the top node of the directed path. The first described part is needed to compute the partial tree decomposition of the directed path. We provide a polynomial-time algorithm to do this. Furthermore, the three-partition will allow us to decide which choices for bags to the top and bottom nodes of preceding directed paths are compatible with each other.

Let $t$ be a node of a rooted tree decomposition $𝒯=(T,{\{X_t\}}_{t\in V(T)})$ of a graph $G=(V,E)$. We denote with $T_t$ the subtree of $T$ rooted at node $t$. We use the following notation throughout the document:

• $\mathrm{■}$

  The set $V_t={\bigcup }_{t^{\prime }\in V(T_t)}{X}_{t^{\prime }}$ is the union of all bags in the subtree $T_t$.

• $\mathrm{■}$

  The set $L_t=V_t\setminus X_t$ is the set of vertices “below” node $t$.

• $\mathrm{■}$

  The set $R_t=V\setminus V_t$ is the set of the “remaining” vertices, that is, the ones that are neither in the bag of node $t$ nor below $t$.

Clearly, for every node $t$, the sets $L_t,X_t,R_t$ are a partition of $V$.

Chapelle et al. [26] show that the nodes of a rooted tree decomposition that have the same $S$-trace form a directed path. They prove this for $S$-traces where $S$ is a minimum vertex cover and the rooted tree decomposition is nice, however inspecting their proof reveals that this property also holds for arbitrary sets $S$ and arbitrary rooted tree decompositions. Formally, we have the following.

Lemma 3.2 allows us to define so-called directed paths of $S$-traces, which will be central to our algorithm. Informally, given an $S$-trace our algorithm will compute candidates for the corresponding directed path, and then use a dynamic programming approach to connect the path to the rest of a partially computed rooted tree decomposition.

We use the above concepts and some additional ones that we introduce below to define a specific type of rooted tree decomposition that interacts with the set $S$ in a very structured way. The concepts are illustrated in Figure 1. First, we distinguish nodes that are at the end of a directed path of some $S$-trace.

Next, we observe that for every directed path of some $S$-trace, the parent of $t_{\max }$ is also an $S$-bottom node. Note that this implies that a situation as depicted in Figure 1(b) cannot happen.

We now define so-called $S$-parent and $S$-children. Informally, as $S$-child is a child of a node such that there is a vertex in $S$ that is only contained in nodes in the subtree of the tree decomposition rooted at the $S$-child. The $S$-parent of a node is defined analogously. Formally, we define them as follows.

We now give the definition of a so-called $S$-nice tree decomposition. Intuitively, this tree decomposition behaves nicely (in the sense of nice tree decompositions [21]) when interacting with vertices from the vertex set $S$, but is more flexible for the vertices in $V\setminus S$. Similarly to nice tree decomposition, $S$-nice tree decompositions distinguish three main types of $S$-bottom nodes, analogous to introduce, forget, and join nodes. We associate each $S$-bottom node with $S$-trace $(L^S,X^S,R^S)$ with a so-called S-operation, which can be $\mathrm{𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}(v)$ for some $v\in X^S$, $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}(v)$ for some $v\in S\setminus X^S$, or $\mathrm{𝗃𝗈𝗂𝗇}(X^S,X_1^S,X_2^S,L_1^S,L_2^S)$ for some $X_1^S,X_2^S\subseteq X^S$ and $L_1^S,L_2^S\subseteq L^S$.

See Figure 1(a) for an illustration of an $S$-nice tree decomposition. We show that if there is a tree decomposition for a graph $G=(V,E)$, then for every $S\subseteq V$ there is also an $S$-nice tree decomposition with the same width for $G$.

Note that, however, not every $S$-nice tree decomposition is a nice tree decomposition, since, for example, we allow $S$-bottom nodes to have an arbitrary amount of children that are not $S$-children. Furthermore, the $S$-children of an $S$-bottom nodes that admits $\mathrm{𝗃𝗈𝗂𝗇}$ as its $S$-operation do not have to have the same bags their parent.

Now we introduce slim $S$-nice tree decompositions. Intuitively, they do not contain nodes that unnecessarily have full bags. To this end, we first define full join trees of an $S$-nice tree decomposition, which, intuitively, are subtrees of the tree decomposition where all nodes have the same (full) bag and admit a $\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}$ operation.

Furthermore, we introduce the following terminology. Let $C$ be a connected component in $G[V^{\prime }]$ for some $V^{\prime }\subseteq V$.

• $\mathrm{■}$

  If $V(C)\cap S=\mathrm{\varnothing }$, then we call $C$ an $F$-component.

• $\mathrm{■}$

  If $V(C)\cap S\ne \mathrm{\varnothing }$, then we call $C$ an $S$-component.

It is easy to see that every connected component of $G[V^{\prime }]$ falls into one of the above categories, for every choice of $V^{\prime }\subseteq V$.

Now we are ready to define slim $S$-nice tree decompositions, this most central definition to be presented in the extended abstract.

Before we show that we can make any $S$-nice tree decomposition slim, we give some intuition on why the properties of slim $S$-nice tree decompositions are desirable for us.

1. 1.

   Condition 1 allows us to assume that all $S$-bottom nodes have a parent. This is important since, informally speaking, we want to remove all vertices that do not need to be in nodes that are below some $S$-bottom node, and move them above it. We formalize this later in this section when we define top-heavy tree decompositions.

2. 2.

   Condition 2 allows us to assume that $S$-bottom nodes with two $S$-children, that is, the ones that admit $S$-operation $\mathrm{𝗃𝗈𝗂𝗇}$, are either part of a full join tree, or both the $S$-children and the parent do not have full bags and those bags. This is important since we will treat these two cases differently in our algorithm. In particular in the latter case, that is, if an $S$-bottom node admits the $S$-operation $\mathrm{𝗃𝗈𝗂𝗇}$ and it is not part of a full join tree, we need the property that both the $S$-children and the parent do not have full bags and that the bags are subsets of the bag of the $S$-bottom node.

3. 3.

   Condition 3 allows us to assume that whenever an $S$-bottom node does not have a full bag, then the bag of its parent is also not full, and in particular, it is the same bag. This will make some proofs easier to achieve and easy to obtain by subdividing the edge between the $S$-bottom node and its parent, and giving the new node the same bag as the $S$-bottom node.

4. 4.

   Condition 4 allows us to assume that whenever an $S$-bottom node admits the $S$-operation $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}$ and its $S$-child (which always has a larger bag) it not full, then the bag of the $S$-child of the $S$-child (if it exists) is also not full. As with the previous condition, this is easy to achieve by edge subdivision and it simplifies some of our proofs.

5. 5.

   Condition 5 allows us to assume that in a directed path corresponding to an $S$-trace $(L^S,X^S,R^S)$ with $L^S\ne \mathrm{\varnothing }$, if the parent of the bottom node has a non-full bag, then the top node is not the parent of the bottom node. This will simplify many steps in our algorithm.

6. 6.

   Condition 6 allows us to assume that every $S$-bottom node that is part of a full join tree admits the $S$-operation $\mathrm{𝗃𝗈𝗂𝗇}$.

7. 7.

   Condition 7 is the most technical one and also the most important one. Essentially it allows us to assume that every vertex $v\in V\setminus S$ that is contained in a bag $X$ of a node that is part of a full join tree is a neighbor of at least three different $S$-components in $G-X$. This will be crucial for establishing the running time bound of a subroutine of our algorithm.

Now we show that if a graph $G$ admits an $S$-nice tree decomposition with width $k$, then $G$ also admits a slim $S$-nice tree decomposition with width $k$.

Now we describe how we extend the $S$-operations introduced in Definition 3.6. We first introduce a big version $\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}$ of the $S$-operation $\mathrm{𝗃𝗈𝗂𝗇}$. When we compute bags for $S$-bottom nodes that admit this operation, we will have several possible candidates for the bag, and an additional bit string $s$ encodes which one we are considering. Furthermore, we need the additional information on which vertex is (potentially) missing in each of the bags of the $S$-children or the parent, in the case that they are not full. This is encoded with three integers $d_0$, $d_1$ and $d_2$. We have the following big $S$-operation.

• $\mathrm{■}$

  $\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}(X^S,X_1^S,X_2^S,L_1^S,L_2^S,s,d_0,d_1,d_2)$ with some vertex sets $X^S,X_1^S,X_2^S,L_1^S,L_2^S\subseteq S$ and some bit string $s\in {\{0,1\}}^{2\mathrm{𝖿𝗏𝗇}(G)+1}$ and $d_0,d_1,d_2\in \{0,\mathrm{\dots },k+1\}$.

In order to define which $S$-bottom nodes admit the above-described big $S$-operations, we introduce a function that “decodes” its bag. Let $\mathrm{𝖻𝗂𝗀𝖻𝖺𝗀}:2^S\times {\{0,1\}}^{2\mathrm{𝖿𝗏𝗇}(G)+1}\to 2^V$ be a function which takes as input subset of $S$ (which will be the set $X^S$ of the $S$-bottom node that admits the big $S$-operation) and the bit string $s$ that encodes which bag candidate is chosen. This will always be a full bag. We additionally need to define a function that determines the bags of the children using the additional integers $d_1$ and $d_2$. Let $\mathrm{𝗌𝗎𝖻𝖻𝖺𝗀}:2^V\times \{0,\mathrm{\dots },k+1\}\to 2^V$ be a function that takes as input a subset of $V$ (which will be the bag of the $S$-bottom node that admits the $S$-operation $\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}$) and an additional integer that encodes which vertex is missing is the bag of a child (if the integer is zero, this will encode that the bag of the child is the same). Formally, $\mathrm{𝗌𝗎𝖻𝖻𝖺𝗀}(X,0)=X$ and $\mathrm{𝗌𝗎𝖻𝖻𝖺𝗀}(X,i)=X\setminus \{v\}$, where $v$ is at the $i$th ordinal position in $X$ (recall that $V$ is ordered in an arbitrary but fixed way).

Note that at this point, we cannot decide whether an $S$-bottom node admits a $\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}$ $S$-operation since we have not defined the function $\mathrm{𝖻𝗂𝗀𝖻𝖺𝗀}$ yet. Informally speaking, there will be sufficiently many options for the bit string $s$ such that for every possible bag that a node $t$ that meets the conditions in Definition 4.1 has, the function $\mathrm{𝖻𝗂𝗀𝖻𝖺𝗀}$ maps the $X_t^S$ and the bit string $s$ to that bag. Formally, we will show the following.

Now we introduce “small” $S$-operations for $S$-bottom nodes that are not contained in full join trees. Similar as in the case of the big operations, we need some additional information that allows us to compute bags of $S$-children or parent nodes. Here, we add an additional integer $d$ that will guide our algorithm to a specific bag candidate. The main reason why we add this information to the state is to guarantee that our algorithm computes the same bag for the bottom node of the directed path as we computed in the predecessor states for the parent of the top node. We have the following small $S$-operations.

• $\mathrm{■}$

  $\mathrm{𝗌𝗆𝖺𝗅𝗅𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}(v,d)$ with some vertex $v\in S$ and some integer $d\in \{1,\mathrm{\dots },{(n+1)}^3\}$.

• $\mathrm{■}$

  $\mathrm{𝗌𝗆𝖺𝗅𝗅𝗃𝗈𝗂𝗇}(X^S,X_1^S,X_2^S,L_1^S,L_2^S,d)$ with some vertex sets $X^S,X_1^S,X_2^S,L_1^S,L_2^S\subseteq S$ and some integer $d\in \{1,\mathrm{\dots },{(n+1)}^3\}$.

In order to define which $S$-bottom nodes admit the above-described small $S$-operations, we again use a function that “decodes” its bag. Let $\mathrm{𝗌𝗆𝖺𝗅𝗅𝖻𝖺𝗀}:2^S\times \mathbb{N}\to 2^V$ be a function which takes as input a subset of $S$ and the number $d$ that will guide the algorithm to a specific bag. We additionally need to define a function that determines the bags of the children. We call this function $\mathrm{𝗇𝖻𝖺𝗀}$ (for “neighboring bag”). It takes as input the bag, the integer $d$, and a flag from $\{P,L,R\}$ indicating whether we wish to compute the bag of the parent, the left child, or the right child (if the node only has one child, we consider this child to be a left child). Let $\mathrm{𝗇𝖻𝖺𝗀}:2^V\times \mathbb{N}\times \{P,L,R\}\to 2^V$.

Note that in particular, if an $S$-bottom node admits the $S$-operation $\mathrm{𝗌𝗆𝖺𝗅𝗅𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}$, then the bags of its parent and its $S$-child are not full. Similarly, if an $S$-bottom node admits the $S$-operation $\mathrm{𝗌𝗆𝖺𝗅𝗅𝗃𝗈𝗂𝗇}$, then the bags of its parent and both its $S$-children are not full.

In the case that an $S$-bottom node $t$ that admits the $S$-operation $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}(v)$, we have that its $S$-child $t^{\prime }$ has a potentially larger bag. In order to determine the bag of $t$, we will first compute the bag of the $S$-child $t^{\prime }$. Informally speaking, we need some information about the child of $t^{\prime }$ that is on the path from $t$ to its closest descendant that is an $S$-bottom node. Let $t^{\prime \prime }$ be the closest descendant of $t$ that is an $S$-bottom node. If $t^{\prime \prime }$ has the same bag as $t^{\prime }$, then we essentially have to compute the bag of the $S$-bottom node $t^{\prime \prime }$. Hence, we need a flag $f\in \{\text{true},\text{false}\}$ that indicates whether we are in this case. And if we are (that is, $f=\text{true}$), then we need all information about the $S$-operation $\tau$ of $t^{\prime \prime }$. Note that if $t^{\prime \prime }$ also admits the $S$-operation $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}(v)$, then we know that the bag of $t^{\prime \prime }$ is not full, which will be enough. If we are not in the above-described case (that is, $f=\text{false}$), then, similar as in the other small $S$-operations, we need an additional integer that will guide our algorithm to a specific bag candidate. To capture all the above-described extra information, we introduce the following extended version of the $S$-operation $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}(v)$.

• $\mathrm{■}$

  $\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau )$ with some vertex $v\in S$, $d\in \{1,\mathrm{\dots },{(n+1)}^3\}$, $f\in \{\text{true},\text{false}\}$, and some extended $S$-operation $\tau$ that is different from $\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}$.

Similarly to the previously introduced extended $S$-operations, we define some auxiliary functions that serve analogous purposes. Let ${\mathrm{𝗌𝗆𝖺𝗅𝗅𝖻𝖺𝗀}}_{\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}}:2^S\times \mathbb{N}\times \{\text{true},\text{false}\}\times \mathrm{\Pi }\to 2^V$, where $\mathrm{\Pi }$ denotes the set of all extended $S$-operations. Furthermore, let ${\mathrm{𝗇𝖻𝖺𝗀}}_{\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}}:2^V\times \mathbb{N}\times \{\text{true},\text{false}\}\times \mathrm{\Pi }\times \{P,L,R\}\to 2^V$.

Observe that if an $S$-bottom node admits an extended $S$-operation $\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau )$, then $\tau \ne \mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v^{\prime },d^{\prime },f^{\prime },{\tau }^{\prime })$. This follows from the fact that the bag of an $S$-bottom node that admits $S$-operation $\mathrm{𝖿𝗈𝗋𝗀𝖾𝗍}(v)$ (and hence potentially an $\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}$ $S$-operation) is never full.

Finally, we remark that for the small $S$-operations, we do not have an analog to Lemma 4.2, that is, in a slim $S$-nice tree decomposition, it is generally not the case that every $S$-bottom node that is not contained in a full join tree admits some small $S$-operation. We have to refine the tree decompositions further to ensure that all $S$-bottom nodes admit some extended (big or small) $S$-operation. This is discussed further in the full version [41].

Now we define a state of the dynamic program. From now on, we only consider extended $S$-operations, that is, whenever we refer to $S$-operations, we only refer to extended ones. As described at the beginning of the section, it contains an $S$-trace and two $S$-operations, one for the $S$-bottom node of the directed path of the $S$-trace, and one for the parent (if it exists) of the top node of the directed path of the $S$-trace. Formally, we define a state for the dynamic program as follows.

Note that Definition 4.7 implies that if a slim $S$-nice tree decomposition $𝒯$ of $G$ witnesses $\varphi =({\tau }_{-},L^S,X^S,R^S,{\tau }_{+})$, then we have that ${\tau }_{-}=\mathrm{𝗏𝗈𝗂𝖽}$ if and only if $L^S=\mathrm{\varnothing }$, since $S$-bottom nodes never admit the $S$-operation $\mathrm{𝗏𝗈𝗂𝖽}$.

Intuitively, we wish to obtain a dynamic programming table $\mathrm{𝖯𝖳𝖶}:𝒮\to \{\text{true},\text{false}\}$ (for “partial treewidth”) that maps states to true if and only if there is a tree decomposition $𝒯$ of the subgraph “below” the top node of the directed path of the $S$-trace contained in the state that has width at most $k$ and that witnesses $\varphi$. Note that this is not a precise definition, since there may be many vertices in the graph $G$ that we may add to bags in the directed path of the $S$-trace contained in the state, or above, or below it. Informally speaking, we will only add vertices of $G$ to bags in the directed path of the $S$-trace contained in the state if they need to be added to those bags. This allows us to compute a function $\mathrm{𝖫𝖳𝖶}:𝒮\to \{\text{true},\text{false}\}$ (for “local treewidth”) that outputs true if and only if the size of any bag in the directed path is at most $k+1$. We will give a precise definition later. Our definition for $\mathrm{𝖯𝖳𝖶}:𝒮\to \{\text{true},\text{false}\}$ will be somewhat similar to the one by Chapelle et al. [26], however, our definition of $\mathrm{𝖫𝖳𝖶}:𝒮\to \{\text{true},\text{false}\}$ will be significantly more sophisticated than the one used by Chapelle et al. [26].

Given a state $({\tau }_{-},L^S,X^S,R^S,{\tau }_{+})$ of the dynamic program, by Definition 3.9 we can immediately deduce the $S$-traces of the $S$-children of the bottom node of the directed path of the $S$-trace $(L^S,X^S,R^S)$. This gives rise to a “preceding”-relation on states. Let $\varphi =({\tau }_{-},L^S,X^S,R^S,{\tau }_{+})$ be a state with $L^S\ne \mathrm{\varnothing }$. Denote with $\mathrm{\Pi }$ the set of all extended $S$-operations. Then, if ${\tau }_{-}=\mathrm{𝗌𝗆𝖺𝗅𝗅𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}(v,d)$ or ${\tau }_{-}=\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau )$, the set $\mathrm{\Psi }(\varphi )$ of preceding states of $\varphi$ is defined as follows.

• $\mathrm{■}$

  If ${\tau }_{-}=\mathrm{𝗌𝗆𝖺𝗅𝗅𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}(v,d)$, then

  $\mathrm{\Psi }(\varphi )=\{({\tau }_{-}^{\prime },L^S,X^S\setminus \{v\},R^S\cup \{v\},\mathrm{𝗌𝗆𝖺𝗅𝗅𝗂𝗇𝗍𝗋𝗈𝖽𝗎𝖼𝖾}(v,d))\mid {\tau }_{-}^{\prime }\in \mathrm{\Pi }\}.$

• $\mathrm{■}$

  If ${\tau }_{-}=\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau )$, then

  $\mathrm{\Psi }(\varphi )=\left\{(\tau ,L^S\setminus \{v\},X^S\cup \{v\},R^S,\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau ))\right\}\text{ if }f=\text{true},\text{ and}$

  $\mathrm{\Psi }(\varphi )=\{({\tau }_{-}^{\prime },L^S\setminus \{v\},X^S\cup \{v\},R^S,\mathrm{𝖾𝗑𝗍𝖾𝗇𝖽𝖾𝖽𝖿𝗈𝗋𝗀𝖾𝗍}(v,d,f,\tau ))\mid {\tau }_{-}^{\prime }\in \mathrm{\Pi }\}\text{ otherwise.}$

If ${\tau }_{-}=\mathrm{𝗌𝗆𝖺𝗅𝗅𝗃𝗈𝗂𝗇}(X^S,X_1^S,X_2^S,L_1^S,L_2^S,d)$ or ${\tau }_{-}=\mathrm{𝖻𝗂𝗀𝗃𝗈𝗂𝗇}(X^S,X_1^S,X_2^S,L_1^S,L_2^S,s,d_0,d_1,d_2)$, then the sets ${\mathrm{\Psi }}_1(\varphi )$ and ${\mathrm{\Psi }}_2(\varphi )$ of preceding states of $\varphi$ are defined in an analogous way. We give all details in the full version [41].

We can show that the “preceding”-relation on states is acyclic. Hence, we can look up the value of $\mathrm{𝖯𝖳𝖶}$ for preceding states in our dynamic programming table when computing $\mathrm{𝖯𝖳𝖶}(\varphi )$ for some state $\varphi$. However, the above definition is purely syntactic and not for every pair of a state and its preceding states there is a tree decomposition that witnesses all states at the same time. Hence, we need to check which preceding states are legal. To this end, we introduce functions ${\mathrm{𝗅𝖾𝗀𝖺𝗅}}_1:𝒮\times 𝒮\to \{\text{true},\text{false}\}$ and ${\mathrm{𝗅𝖾𝗀𝖺𝗅}}_2:𝒮\times 𝒮\times 𝒮\to \{\text{true},\text{false}\}$ that check whether for a pair of states $\varphi ,\psi$ or a triple of states $\varphi ,{\psi }_1,{\psi }_2$, respectively, the second state or the second and third state are legal predecessors for the first state, respectively. In other words, it checks whether there exists a tree decomposition that witnesses all states and their preceding-relation. For the ease of presentation, we state the dynamic program as an algorithm that only decides whether the input graph has treewidth at most $k$ or not. However, the algorithm can easily be adapted to compute and output a corresponding tree decomposition. Formally, we define the dynamic programming table as follows.

The function $\mathrm{𝖫𝖳𝖶}$ depends on the following three sets of vertices. Let $\varphi =({\tau }_{-},L^S,X^S,R^S,{\tau }_{+})$ be a state.

• $\mathrm{■}$

  $X_{\max }^{\varphi }$ are the vertices in $V$ that we want to be in the bag of the top node $t_{\max }$ of the directed path of $(L^S,X^S,R^S)$, or, if $L^S=\mathrm{\varnothing }$ in the bag of the $S$-child with $S$-trace $(L^S,X^S,R^S)$ of an $S$-bottom node.

• $\mathrm{■}$

  $X_p^{\varphi }$ are the vertices in $V$ that we want to be in the bag of the parent of $t_{\max }$. If $t_{\max }$ is the root, we will assume that $X_p^{\varphi }=\mathrm{\varnothing }$.

• $\mathrm{■}$

  $X_{\min }^{\varphi }$ are the vertices in $V$ that we want to be in the bag of the bottom node $t_{\min }$ of the directed path of $(L^S,X^S,R^S)$, or if $L^S=\mathrm{\varnothing }$ then we set $X_{\min }=X^S$.

• $\mathrm{■}$

  $X_{\text{path}}^{\varphi }$ are additional vertices in $V\setminus S$ that we want to place in some bag of the directed path of $(L^S,X^S,R^S)$, or in some bag of a subtree rooted in a child of a node in the directed path that is not an $S$-child, or if $L^S=\mathrm{\varnothing }$ in some bag of a node below $t_{\max }$ that is not an $S$-child.