vertices appearing in the subtree of $T$ rooted at the node corresponding to $B$ (resp. the node $x$). We denote by [${\mathcal}{F}_t$]{}the set of all $t$-boundaried graphs that have a rooted tree decomposition of width $t-1$ with all boundary vertices contained in the root-bag. Obviously ${\ensuremath{{\mathcal}{F}_t}\xspace}\subseteq {\ensuremath{{\mathcal}{B}_t}\xspace}$. (Note that graphs can be viewed as 0-boundaried graphs, hence we use a same alphabet $\Gamma$ for describing graphs and boundaried graphs.)

\[defi:prot\] Let $t,\alpha$ be positive integers. A *$t$-protrusion* $Y$ of a graph $G$ is an induced subgraph of $G$ with $|\partial(Y)| {\leqslant}t$ and $ {{\mathbf{tw}}}(Y) {\leqslant}t-1$, where $\partial(Y)$ is the set of vertices of $Y$ having neighbors in $V(G) \setminus V(Y)$. An *$(\alpha,t)$-protrusion decomposition* of a graph $G$ is a partition ${\cal P}=Y_{0}\uplus Y_{1}\uplus \cdots \uplus Y_{\ell}$ of $V(G)$ such that for every $1\leqslant i\leqslant \ell$, $N(Y_{i})\subseteq Y_{0}$, $\max\{\ell, |Y_{0}|\}\leqslant \alpha$, and for every $1\leqslant i\leqslant \ell$, $Y_i\cup N(Y_i)$ is a $t$-protrusion of $G$. When $(G,k)$ is the input of a parameterized problem with parameter $k$, we say that an $(\alpha,t)$-protrusion decomposition of $G$ is *linear* whenever $\alpha =O(k)$.

We say that a rooted tree decomposition of a protrusion $G$ (resp. a boundaried graph $G$) is *boundaried* if the boundary $\partial(G)$ 