text:
\section{Introduction} \label{sec:intro}

Since the famous `graph minor' project by Robertson and Seymour that started with \cite{RobertsonS83}, the notions of treewidth and pathwidth received growing interest and a vast amount of results has been obtained.
The pathwidth, informally speaking, allows us to say how closely an arbitrary graph resembles a path.
This concept proved to be useful in designing algorithms for various graph problems, especially in the case when the pathwidth of an input graph is small (e.g. fixed), in which case quite often a variant of well-known dynamic programming approach that progresses along a path decomposition of input graph turns out to be successful.

Several modifications to pathwidth have been proposed and in this work we are interested in the connected variant in which one requires that a path decomposition $(X_1,\ldots,X_l)$ of a graph $G$ satisfies: the vertices $X_1\cup\cdots\cup X_i$ induce a connected subgraph in $G$ for each $i\in\{1,\ldots,l\}$.
This version of the classical pathwidth problem is motivated by several pursuit-evasion games, including, but not limited to, \emph{edge search}, \emph{node search} or \emph{mixed search}~\cite{searchingPebbling,ParsonsPursuitEvasion,takahashi1995mixed}.
More precisely, computing the minimum number of searchers needed to clean a given graph $G$ in the node search game (i.e., computing the \emph{node search number} of $G$) is equivalent to computing the connected pathwidth of $G$. Moreover, a connected path decomposition can be easily translated into the corresponding node search strategy that cleans $G$ and vice versa.
For further references that provide more details on correspondences between connected path decomposition and different variants of the search games see e.g.~\cite{BFFFNST12,Dereniowski12SIDMA,FN06,FT08}.

\subsection{Related work} \label{sec:related}

A lot of research has been done in the direction of obtaining FPT algorithms for pathwidth, parametrized by the pathwidth $k$.
One of the first polynomial-time algorithm was presented in $1983$ by Ellis \emph{et al.} and had running time $O(n^{2k^2+4k+2})$~\cite{EllisST83}. Later these results were improved (e.g., \cite{Bodlaender96,BodlaenderK96}) leading to the currently fastest FPT algorithm, working in time $2^{O(k^2)}n$~\cite{Furer16}. In these algorithms, in order to produce an optimal solution, an approximate path- or tree-decomposition is pre-computed.
It is thus of interest to have good approximations for these problems. Numerous works have been published in this direction \cite{Amir10,Lagergren96,Reed92}, leading to the currently fastest algorithm for constant-factor approximation for treewidth, working in time $2^{O(k)}n$~\cite{BodlaenderDDFLP16}, that is, single exponential in the treewidth $k$. The best known approximation ratio of a polynomial time approximation algorithm for pathwidth is $O(\sqrt{\log (opt)}\log n)$~\cite{FeigeHL08}.

There exist exact algorithms for computing pathwidth, whose running times are exponential in the order of the input graph.
Pathwidth can be computed in $O^*(2^n)$-time (in $O^*(2^n)$ space) or in $O^*(4^n)$-time with the use of polynomial space, using a simple algorithm from~\cite{BodlaenderFKKT12}.
There is also a faster algorithm with running time $O^*(1.9657^n)$~\cite{SuchanV09}, which has been further improved very recently to $O^*(1.89^n)$~\cite{KitsunaiKKTT12}.
See \cite{BiedlBNNPR13,Coudert16,CoudertMN16} for some experimental approaches to pathwidth computation.

For pathwidth, it is known due to~\cite{RobertsonS04} that the set of minimal forbidden minors (i.e., the obstruction set) is finite for each fixed $k$.
However, a significant difference between pathwidth and connected pathwidth is that the latter one is not closed under taking minors and hence it is not known if the set of minimal forbidden minors for connected pathwidth is finite~\cite{BestGTZ16}.

We also point out that a number of results have been obtained for connected pathwidth or the closely related connected graph (edge) search, including algorithmic and computational ones \cite{BFFFNST12,Dereniowski11,Dereniowski12SIDMA,connected_outerplanar,FN06,Nisse08}, monotonicity \cite{FN08,YDA09}, structural properties \cite{connected_and_internal} or distributed algorithms \cite{BorowieckiDK15,FHL05,INS09}.

\subsection{Motivation} \label{sec:motivation}

The connectivity constraint for pathwidth is natural and useful in graph searching games \cite{BFFFNST12,FHL05,FN06}.
The connectivity is in some cases implied by potential applications (e.g., security constraints may enforce the clean, or safe, area to be connected) or it is a necessity, like in distributed or online versions of the problem~\cite{BlinFNV08,BorowieckiDK15,INS09,NS09}.

Our second motivation comes from connections between pathwidth and connected pathwidth.
More specifically, \cite{Dereniowski12SIDMA} implies that for any graph $G$, these parameters differ multiplicatively only by a small constant.
This implies that an approximation algorithm for connected pathwidth immediately provides an approximation algorithm for pathwidth with asymptotically the same approximation ratio.
This may potentially lead to obtaining better approximations for pathwidth since, informally speaking, the algorithmic search space for connected pathwidth is for some graphs much smaller than that for pathwidth.
On the other hand, we do not know any algorithm computing the connected pathwidth in time $O^*((2-\epsilon)^n)$, for any $\epsilon > 0$. Thus, despite this smaller algorithmic search space, it is not clear how these two problems algorithmically differ in the context of designing exact algorithms.

During the GRASTA 2017 workshop, Fedor V. Fomin \cite{fominQuestion} raised an open question, whether we can verify in polynomial time, if the connected pathwidth of the given graph is at most $k$, for a fixed constant $k$. In this paper we answer this question in the affirmative.

\subsection{Outline} \label{sec:our-work}
In the next section we recall a definition of connected pathwidth and related terms used in this work.
Section~\ref{sec:algorithm} provides a polynomial-time algorithm for determining whether the connected pathwidth of an arbitrary input graph $G$ is at most $k$, where $k$ is a fixed integer. The algorithm is inspired by the algorithms for computing mininum-length path decompositions by Dereniowski, Kubiak, and Zwols~\cite{DERENIOWSKI20151715}, we also use the notation from this paper.
Then, Section~\ref{sec:analysis} contains the analysis of the algorithm (its correctness and running time).
We finish with some open problems in Section~\ref{sec:open-problems}.

\section{Definitions} \label{sec:definitions}
For a simple graph $G=(V(G),E(G))$ and a set $Y\subseteq V(G)$, the subgraph with vertex set $Y$ and edge set $\{\{u,v\}\in E(G)\hspace{0.1cm}\bigl|\bigr.\hspace{0.1cm} u,v\in Y\}$ is denoted by $G[Y]$ and is called the subgraph \emph{induced} by $Y$.
For $Y\subseteq V(G)$, we write $N_G(Y)$ to denote the \emph{neighborhood} of $Y$ in $G$, defined as $N_G(Y)=\{v\in V(G)\setminus Y\hspace{0.1cm}\bigl|\bigr.\hspace{0.1cm} \exists u\in Y \textup{ s.t. }\{u,v\}\in E(G)\}$.

\begin{definition} \label{def:path_dec}
A \emph{path decomposition} of a simple graph $G=(V(G),E(G))$ is a sequence $\mathcal{P}=(X_1,\ldots,X_l)$, where $X_i\subseteq V(G)$ for each $i\in\{1,\ldots,l\}$, and
\begin{enumerate}[label={\normalfont(\roman*)},align=left,leftmargin=*]
 \item\label{it:path1} $\bigcup_{i=1}^{l} X_i=V(G)$,
 \item\label{it:path2} for each $\{u,v\}\in E(G)$ there exists $i\in\{1,\ldots,l\}$ such that $u,v\in X_i$,
 \item\label{it:path3} for each $i,j,k$ with $1\leq i\leq j\leq k\leq l$ it holds that $X_i\cap X_k\subseteq X_j$.
\end{enumerate}
The \emph{width} of a path decomposition $\mathcal{P}$ is $\width{\mathcal{P}}=\max_{i\in\{1,\ldots,l\}}|X_i|-1$.
The \emph{pathwidth} of $G$, denoted by $\pathwidth{G}$, is the minimum width over all path decompositions of $G$.
\end{definition}

We say that a path decomposition $\mathcal{P}=(X_1,\ldots,X_l)$ is \emph{connected} if the subgraph $G[X_1\cup\cdots\cup X_i]$ is connected for each $i\in\{1,\ldots,l\}$. A \emph{connected pathwidth} of a graph $G$, denoted by $\cpw{G}$, is the minimum width taken over all connected path decompositions of $G$.

Finally, a \emph{connected partial path decomposition} of a graph $G$ is a connected path decomposition $(X_1,\ldots,X_i)$ of some subgraph $H$ of $G$, where $N_G(V(G)\setminus V(H))\subseteq X_i$.
In other words, in the latter condition we require that each vertex of $H$ that has a neighbor outside $H$ belongs to the last bag $X_i$.
Intuitively, a connected partial path decomposition of $G$ can be potentially a prefix of some connected path decomposition of $G$.
Also note that if $(X_1,\ldots,X_l)$ is a connected path decomposition, then for each $i\in\{1,\ldots,l\}$, $(X_1,\ldots,X_i)$ is a connected partial path decomposition of $G$, where $H=G[X_1\cup\cdots\cup X_i]$.

In our analysis we will use an intermediate notion between arbitrary and connected path decompositions.
For a path decomposition $\mathcal{P}=(X_1,\ldots,X_l)$ of $G$ and $\mathcal{I}\subseteq V(G)$, we say that it is \emph{$\mathcal{I}$-connected} if for each $i\in\{1,\ldots,l\}$ each connected subgraph of $G[X_1\cup\cdots\cup X_i]$ contains a vertex from $\mathcal{I}$.
In other words, if one takes a prefix of $\mathcal{P}$, then the subgraph of $G$ induced by the vertices of this prefix may have several connected components and each of them must have a vertex in $\mathcal{I}$.
Note that if $\mathcal{P}$ is connected then there is only one such connected component.

\section{The algorithm} \label{sec:algorithm}
Note that we may without loss of generality assume that the first bag in a connected path decomposition to be computed has only one vertex.
In the remaining part of the paper we denote this vertex by $s^*$. For the time being we may assume that $s^*$ is known to the algorithm because checking all possible values of $s^*\in V(G)$ increases the complexity only by a factor of $n$.
We will present an algorithm  deciding whether, for an input graph $G$ and $\mathcal{I}=\{s^*\}$, there exists an $\mathcal{I}$-connected path decomposition of width $k-1$.
Our algorithm is recursive so for subsequent recursive calls all three parameters are different.
We will consider width $k-1$ so that the sets we have to handle will have size at most $k$.
This modification in which we consider the `starting bag' of a decomposition is dictated by the fact that our algorithm is recursive and on subsequent levels of the recursion the content of the first bag cannot be arbitrary in connected path decompositions (as opposed to just path decompositions).

In the following by $G$ we denote the input graph with $n$ vertices, $\mathcal{I}$ and $k$ are also fixed.
In the rest of the work, $k$ refers to the maximum bag size of the connected path decomposition to be computed (thus, the algorithm checks whether $\cpw{G}\leq k-1$ for the input graph $G$).

For any $S\subseteq V(G)$, we say that a subgraph $H$ of $G$ is an \emph{$S$-branch} if $H$ is a connected component of $G-S$ and $N_G(V(H))=S$. For any $S\subseteq V(G)$, define $\branches{S}$ to be the set of all $S$-branches.
A set $S$ is called a \emph{bottleneck} if the number of $S$-branches is at least $2k+1$, as it guarantees us the existence of at least one special branch called an \emph{in-branch}, which will be defined formally in the next Section.
Observe that each connected component of $G-X$, for any $X\subseteq V(G)$, is an $S$-branch for exactly one non-empty subset $S$ of $X$.

Let us mention that $S$-branches are also known as \emph{full components associated with $S$} (see e.g. Bouchitt{\'e} and Todinca~\cite{DBLP:journals/siamcomp/BouchitteT01}).

\subsection{States}

By a \emph{potential state} we mean a triple $(X,\{B_S\}_{S \subseteq X}, \{f^B_S \}_{S \subseteq X})$, consisting of:
\begin{itemize}
\item a non-empty set $X \subseteq V(G)$ with $\card{X} \leq k$,
\item a subset $B_S \subseteq \branches{S}$ of cardinality at most $2k$, chosen for every non-empty $S \subseteq X$,
\item a function $f^B_S \colon \branches{S} \to \{0,1\}$, chosen for every non-empty $S \subseteq X$. We additionally require that if $H,H' \in \branches{S} \setminus B_S$, then $f^B_S(H)=f^B_S(H')$.
\end{itemize}
The exact meaning of $B_S$ will be explained later on, but let us present some intuition. In Lemma~\ref{lem:small} we show that for every path decomposition $\mathcal{P}$, the vertices of all but at most $2k$ $S$-branches appear in bags of $\mathcal{P}$ in a certain, well-structured way. The set $B_S$ and the function $f^B_S$ will used to describe the structure of the remaining, badly behaving $S$-branches.

Observe that the set $X$ may be chosen in at most $n^k$ ways and the number of choices of $S$ is at most $2^k$. For every $S$, the number of $S$-branches is at most $n$, so $B_S$ can be chosen in at most $n^{2k}$ ways. The function $f^B_S$ can be chosen in at most $2^{|B_S|} \cdot 2 \leq 2^{2k+1}$ ways. Therefore the number of potential states is at most $n^k  \cdot 2^k \cdot n^{2k} \cdot 2^{2k+1}= O(n^{3k})$, i.e., polynomial in $n$, where the asymptotic notation hides the factor that depends on $k$.

With a potential state $s=(X,\{B_S\}_{S\subseteq X},\{f^B_S\}_{S \subseteq X})$ we associate the following notions.
By $\bag{s}$ we denote the set $X$.
By $\cover{s}$ we denote the set of vertices
\[X \cup \bigcup_{S \subseteq X, S \neq \emptyset} \left( \bigcup_{H \in \branches{S} \colon f_S^B(H)=1} V(H) \right).\]
By $G_s$ we denote the subgraph of $G$ induced by $\cover{s}$.
We say that two states $w,s$ are \emph{indistinguishable} if $\cover{w}=\cover{s}$ and $\bag{w} = \bag{s}$. Otherwise states are \emph{distinguishable}.
We note that for such two distinguishable states it may hold that $\cover{w}=\cover{s}$ but $\bag{w}\neq\bag{s}$.

Let $v$ be a vertex from $\cover{s}$ which has a neighbor $u \notin \cover{s}$.
We argue that $v\in\bag{s}$.
Otherwise, if $v \notin \bag{s}$, then both $v$ and $u$ belong to the same $S$-branch for some $S \subseteq \bag{s}$. Thus, they are either both in $\cover{s}$, or outside it. From this it follows that every vertex $v \in \cover{s}$, which has a neighbor $u \notin \cover{s}$, must belong to $\bag{s}$. Let us denote the set of such vertices $v$ by $\border{s}$.
We have proved:
\begin{observation} \label{obs:cover}
For each potential state $s$ it holds that $\border{s}\subseteq\bag{s}$.
\end{observation}

We say that a potential state $s$ is a \emph{state} if each connected component of $G_s$ contains a vertex in $\mathcal{I}$.

We introduce a boolean table $Tab$, indexed by all states.
For a state $s$, the value of $Tab[s]$ will be set to $true$ by our algorithm if and only if there exists some $\mathcal{I}$-connected path decomposition $\mathcal{P}=(X_1,X_2,\ldots,X_l)$ of $G_s$, such that $\width{\mathcal{P}}$ is at most $k-1$, $\mathcal{P}$ starts with $\mathcal{I}$ and $X_l = \bag{s}$. We will use a dynamic programming to fill out the table $Tab$. Then, we will conclude $\cpw{G} \leq k-1$ (with the additional constraint concerning $\mathcal{I}$) if and only if $Tab[s] = true$ for some state $s$ with $\cover{s} = V(G)$.

Observe that such a final state exists, since for $s = (X, \{B_S\}_S, \{f^B_s\}_S)$, we have $\cover{s}=V(G)$ if and only if $f^B_S(H)=1$ for every $S$ and $H$.
However, the astute reader may notice that in our representation we might have not included some $\mathcal{I}$-connected partial path decompositions and it could be possible that we do not find a solution, even though it exists. We will show that if $\cpw{G} \leq k-1$, then there exists a special type of a $\mathcal{I}$-connected path decomposition of width at most $k-1$, called a \emph{structured path decomposition} (defined later), which can be found using our algorithm because, as we will argue, our table $Tab$ does not `omit' any structured path decompositions.

\subsection{Extension rules}

Let us introduce a total ordering $\prec_s$ on the set of states. We say that $w \prec_s s$ if $|\cover{w}| < |\cover{s}|$, or $|\cover{w}|=|\cover{s}|$ and $|\bag{w}| > |\bag{s}|$. If $|\cover{w}| = |\cover{s}|$ and $|\bag{w}| = |\bag{s}|$, then we resolve such a tie arbitrarily.

In our dynamic programming, we process states according to the ordering $\prec_s$ and fill the table $Tab$ using two extension rules: \emph{step extension} and \emph{jump extension}.

\begin{description}
\item[step extension] for distinguishable states $w, s$ with $s \prec_s w$ and $|\cover{s}|>1$: if $Tab[w] = true$ and
\begin{enumerate}[label={\normalfont(S\arabic*)},align=left,leftmargin=*]
\item\label{step:1} each connected component of $G[\bag{s}]$ contains a vertex from $\bag{w}$,
\item\label{step:2} $\border{w}\subseteq\bag{s}$,
\item\label{step:3} $\cover{s} = \cover{w} \cup \bag{s}$,
\item\label{step:4} $\bag{s} \cap \cover{w} \subseteq \bag{w}$,
\end{enumerate}
then set $Tab[s]$ to $true$,
\item[jump extension] for distinguishable states $w = (X,\{B_S\}_{S\subseteq X},\{f^B_S\}_S)$ and $s = (X,\{B_S\}_{S\subseteq X},\{g^B_S\}_S)$ with $s \prec_s w$ and $|\cover{s}|>1$: if $Tab[w] = true$ and there exists a bottleneck set $S' \subseteq X$, such that
\begin{enumerate}[label={\normalfont(J\arabic*)},align=left,leftmargin=*]
\item\label{jump:green} $f^B_{S'}(H) = 0$ and $g^B_{S'}(H) = 1$ for every $H \in \branches{S'} \setminus B_{S'}$,
\item\label{jump:otherS} $f^B_{S'}(H) = g^B_{S'}(H)$ for every $H \in B_{S'}$,
\item\label{jump:other} $f^B_{S}(H) = g^B_{S}(H)$ for every non-empty $S \neq S'$, $S\subseteq X$, and $H \in \branches{S}$,
\item\label{jump:rec} for each $H \in \branches{S'} \setminus B_{S'}$ there exists a $N_G(S')\cap V(H)$-connected path decomposition $\mathcal{P}_H$ of $H$ of width at most $k-|X|-1$,
\end{enumerate}
then set $Tab[s]$ to $true$.
\end{description}

Let us present some intuitions behind these extension rules.
In step extension, if $w$ corresponds to some $\mathcal{I}$-connected partial path decomposition $\mathcal{P} = (X_1,X_2,\ldots,X_l=\bag{w})$, then $s$ corresponds to an $\mathcal{I}$-connected partial path decomposition $\mathcal{P}' = (X_1,X_2,\ldots,X_l,X_{l+1}=\bag{s})$ (we extend $\mathcal{P}$ by adding a single bag, namely $\bag{s}$).
Also note, that each new vertex in $X_{l+1}$, i.e. one that is not in $X_l$, has (due to~\ref{step:1}) a neighbor in $X_l$, as required in connected path decompositions.

In jump extension, if the state $w$ corresponds to some $\mathcal{I}$-connected partial path decomposition $\mathcal{P} = (X_1,X_2,\ldots,X_l)$, then the state $s$ corresponds to a $\mathcal{I}$-connected partial path decomposition $\mathcal{P}' = (X_1,X_2,\ldots,X_l,X_{l+1},X_{l+2},\ldots,X_{l + l'})$, where
\begin{itemize}
\item $\bigcap_{i=l}^{l+l'}X_i = X_l = X_{l+l'}$,
\item $\mathcal{P}'' := (X_{l+1} \setminus X_l, X_{l+2} \setminus X_l,\ldots, X_{l+l'} \setminus X_l)$  is a (not necessarily connected) path decomposition of the graph induced by $S'$-branches, for some $S' \subseteq X_l$.
These are the $S'$-branches $H$ in~\ref{jump:green} and $\mathcal{P}''$ is obtained by `concatenating' the path decompositions from~\ref{jump:rec}.
\end{itemize}
Note that although a path decomposition $\mathcal{P}_H$ in~\ref{jump:rec} may not be connected, we ensure (by definition of $\mathcal{I}$-connectivity) that each connected component of the subgraph induced by each prefix of $\mathcal{P}_H$ has a vertex from $N_G(S')\cap V(H)$ and hence it contains a neighbor of $S'$, ensuring required connectivity of the resulting path decomposition.

\subsection{Summing up}
 Let us recall how the algorithm works. We introduce a boolean table $Tab$, indexed by all states. We initialize $Tab$ by setting $Tab[s]=true$ for every state $s$, such that $\cover{s} = \bag{s} = \{ v \}$, for some $v \in \mathcal{I}$, while for the remaining states $s$ we initialize $Tab[s]$ to be $false$.

Then we process states in the ordering $\prec_s$, checking whether a step extension or a jump extension can be applied to set $Tab[s]= true$.
We terminate when we find a state corresponding to a feasible solution (i.e., we set $Tab[s]=true$ for some state $s$ with $\cover{s}=V(G)$), or when we process all states, in the latter case we report that a solution does not exist.

 We note that the algorithm will be subsequently switching some entries of $Tab$ from $false$ to $true$, and hence until the completion of the algorithm it is understood that the value $false$ of a particular entry of $Tab$ does not provide any information as to whether a corresponding path decomposition exists.

\section{The analysis} \label{sec:analysis}

Let us start by introducing some more definitions and additional notation.
Let $\mathcal{P}=(X_1,X_2,\ldots,X_l)$ be a path decomposition of $G$.
We say that a connected subgraph $H$ of $G$ is \emph{contained in} an interval $[i,j]$ of $\mathcal{P}$ for some $1\leq i\leq j\leq l$, if $V(H)\cap X_t\neq\emptyset$ if and only if $t\in\{i,\ldots,j\}$. Note that this definition is valid since it follows that for a connected subgraph $H$, the subset of indices $t$ such that $V(H)\cap X_t\neq\emptyset$ is indeed an interval. If $H$ is contained in $[i,j]$, then we denote these endpoints of the interval as $i=\graphStart{H}{\mathcal{P}}$ and $j=\graphEnd{H}{\mathcal{P}}$.
If $\mathcal{P}$ is clear from the context, we will often write shortly $\graphStartS{H} := \graphStart{H}{\mathcal{P}}$ and $\graphEndS{H}:=\graphEnd{H}{\mathcal{P}}$.

For a set  $S$ and an $\mathcal{I}$-connected path decomposition $\mathcal{P}=(X_1,X_2,\ldots,X_l)$, we say that an $S$-branch $H$ is an \emph{in-branch} if $S \subseteq X_{\graphStartS{H}}$ and $S \subseteq X_{\graphEndS{H}}$. The lemma below gives us a lower bound for number of in-branches of $S$.

\begin{lemma}\label{lem:small}
For every set $S$ and path decomposition $\mathcal{P}=(X_1,X_2,\ldots,X_l)$, at most $2k$ $S$-branches are not in-branches.
\end{lemma}
\begin{proof}
Consider an $S$-branch $H$, which is not an in-branch. This means that $S \not\subseteq X_{\graphStartS{H}}$ or $S \not\subseteq X_{\graphEndS{H}}$.

First, consider $H$, such that $S \not\subseteq X_{\graphStartS{H}}$. Let $t$ be the minimum index such that $S \subseteq X_1 \cup X_2 \cup \cdots \cup X_t$. Let $v \in S$ be a vertex in $X_t \setminus (X_1 \cup X_2 \cup \cdots \cup X_{t-1})$, it exists by the definition of $t$.
Recall that $v$ is a neighbor of some vertex $w$ of $H$, so, since $\mathcal{P}$ is a path decomposition, there must be a bag $X_i$ containing both $v$ and $w$. Since $X_t$ is the first bag, where $v$ appears, we observe that $i \geq t$ and thus $\graphEndS{H} \geq t$.

Suppose now that $\graphStartS{H} > t$. Note that since $S \not\subseteq X_{\graphStartS{H}}$, there is some $u \in S \setminus X_{\graphStartS{H}}$.
Recall that $u$ is a neighbor of some vertex from $H$. However, since $u \in  X_1 \cup X_2 \cup \cdots \cup X_t$ and $u \notin X_{\graphStartS{H}}$, the vertex $u$ does no appear in any bag containing a vertex of $H$, so $\mathcal{P}$ cannot be a path decomposition of $G$. Thus $\graphStartS{H} \leq t$.

Therefore, the bag $X_{t}$ contains at least one vertex from $H$.
Since $S$-branches are vertex-disjoint and $|X_t|\leq k$, we observe that there are at most $k$ $S$-branches $H$, such that  $S \not\subseteq X_{\graphStartS{H}}$.

Now consider an $S$-branch $H$, such that  $S \subseteq X_{\graphStartS{H}}$ and $S \not\subseteq X_{\graphEndS{H}}$.
Let $t'$ be the maximum index such that $S\subseteq X_{t'}\cup\cdots\cup X_l$.

Analogously to the previous case, we observe that $\graphStartS{H} \leq t'$ (by the maximality of $t'$) and $\graphEndS{H} \geq t'$, because $S \not\subseteq X_{\graphEndS{H}}$.
Thus the bag $X_{t'}$ contains at least one vertex from $H$, which shows that the number of $S$-branches $H$, such that $S \subseteq X_{\graphStartS{H}}$ and $S \not\subseteq X_{\graphEndS{H}}$, is at most $k$.
Therefore the total number of $S$-branches, that are not in-branches is at most $2k$, which completes the proof.
\end{proof}

Recall that a non-empty set $S$ is a bottleneck if $|\branches{S}| > 2k$. Thus Lemma \ref{lem:small} implies the following:

\begin{corollary}\label{cor:bottlenecks}
If $\mathcal{P}=(X_1,\ldots,X_l)$ is a path decomposition and $S$ is a bottleneck, then the following properties hold:
\begin{enumerate}
\item $S$ has at least one in-branch,
\item there is $i$, such that $S \subseteq X_i$,
\item $\card{S} \leq k$. \qed
\end{enumerate}
\end{corollary}
These properties justify the following definition.

\begin{definition} \label{def:interval}
For a bottleneck $S \subseteq V(G)$, let $\botStart{S}{\mathcal{P}}$ (respectively $\botEnd{S}{\mathcal{P}})$ be the minimum (respectively maximum) index $i$ such that $i=\graphStart{H}{\mathcal{P}}$ ($i=\graphEnd{H'}{\mathcal{P}}$, respectively) for some $S$-branch $H$ (respectively $H'$), which is an in-branch.
\end{definition}
Note that the definition of an in-branch implies that $S \subseteq X_{\botStart{S}{\mathcal{P}}} \cap X_{\botEnd{S}{\mathcal{P}}}$.
The interval $I(S, \mathcal{P}) =[\botStart{S}{\mathcal{P}},\botEnd{S}{\mathcal{P}}]$ is called the \emph{interval of} $S$.
Again, we will often write shortly $\botStartS{S}$, $\botEndS{S}$, and $I(S)$, if $\mathcal{P}$ is clear from the context.

For a bottleneck $S$ we can refine the classification of $S$-branches, which are not in-branches.
We say that an $S$-branch $H$, which is not an in-branch, is
\begin{itemize}
\item a \emph{pre-branch} if $\graphStartS{H} < \botStartS{S}$,
\item a \emph{post-branch} if $\graphStartS{H} \geq  \botStartS{S}$ and $\graphEndS{H} > \botEndS{S}$.
\end{itemize}
By $\branchesin{x}{S,\mathcal{P}}$ we denote the set of all $x$-branches for $S$, where $x \in \{\textup{pre},\textup{in},\textup{post}\}$.
Again, if $\mathcal{P}$ is clear from the context, we will write $\branchesin{x}{S}$ instead of $\branchesin{x}{S,\mathcal{P}}$.
By $\mathcal{C}(S)$ we denote the set of all connected components of $G - S$, that are not $S$-branches.

\paragraph*{Example.} \textit{The graph $G$ in Figure~\ref{fig:preinpost} illustrates the above concepts.
The sequence $X_1,X_2,\ldots,X_{16}$ forms a connected path decomposition of $G$.
The only bottleneck set $S$ consists of two vertices denoted by circles. (In this example we take $k=3$.) There are $13$ $S$-branches: one pre-branch ($G[X_1 \cup X_2 \setminus S]$), eleven in-branches ($G[X_i \setminus S]$ for $i=4,5,\ldots,14$), and one post-branch $(G[X_{15} \cup X_{16} \setminus S]$).
The interval of $S$ is equal to $I(S,\mathcal{P}) = [4, 14]$ and the component $G[X_3 \setminus S]$ is not an $S$-branch, because some vertices in $S$ do not have a neighbor in this component.}

\begin{figure}[htb]
\begin{center}
\centering
  \includegraphics[scale=0.9]{fig-preinpost.pdf}
	\end{center}
\caption{An illustration of two-vertex bottleneck set $S$ and the corresponding $S$-branches.}
\label{fig:preinpost}
\end{figure}

For a subgraph $H$ of $G$, we say that $H$ \emph{waits in} an interval $[i,j]$ of $\mathcal{P}$ if
\[V(H)\cap X_i=V(H)\cap X_{i+1}=\cdots=V(H)\cap X_j.\]
We say that a path decomposition $\mathcal{P}$ is $S$-\emph{structured} if each $C$ that is in $C(\mathcal{S})$ or is a post- or a pre-branch of $\mathcal{S}$ waits in $I(S,\mathcal{P})$.
The main technical tool in our approach is the following result concerning the structure of $\mathcal{I}$-connected path decompositions. The proof of the lemma is provided after giving several technical facts that we need.

\begin{lemma}\label{lem:main_transformation}
If there exists an $\mathcal{I}$-connected path decomposition $\mathcal{P}$, then there is also an $\mathcal{I}$-connected path decomposition $\mathcal{P}'$ of width at most $\width{\mathcal{P}}$ such that $\mathcal{P}'$ is $S$-structured for every bottleneck $S$.
\end{lemma}

We define $\cMin[S,\mathcal{P}]$ as the minimum index $i \in I(S,\mathcal{P})$, for which the size of the set
\[X_{i} \cap \left( \bigcup_{H \in \branchesin{\textup{pre}}{S} \cup \branchesin{\textup{post}}{S} \cup \mathcal{C}(S)} V(H) \right)\]
is minimum. Also, set $X^*:=\left( \bigcup_{H \in \branchesin{\textup{pre}}{S} \cup \branchesin{\textup{post}}{S} \cup \mathcal{C}(S)} V(H) \right) \cap X_{\cMin[S,\mathcal{P}]}$ to be this minimum-size set.

Let $\Gamma$ be the set of all $\mathcal{I}$-connected path decompositions of $G$ and $\mathcal{S}$ be the set of all bottlenecks of $G$.
We will define a function $F : \mathcal{S} \times \Gamma \rightarrow \Gamma$, which for given $S \in \mathcal{S}$ and $\mathcal{P} \in \Gamma$ transforms $\mathcal{P}$ into an $S$-structured $\mathcal{I}$-connected path decomposition of width at most $\width{\mathcal{P}}$.
For simplicity of notation, from now on $t_1 = \botStart{S}{\mathcal{P}}$, $t_2 = \botEnd{S}{\mathcal{P}}$, and $\cMin = \cMin[S,\mathcal{P}]$, whenever $S$ and $\mathcal{P}$ are clear from the context.
Let $\branchesin{\textup{in}}{S,\mathcal{P}} = \{H_1,\ldots, H_{l_{\textup{in}}}\}$, where the in-branches are ordered according to their first occurrences in $\mathcal{P}$, that is, $\graphStartS{H_1} \leq \cdots \leq \graphStartS{H_{l_{\textup{in}}}}$.
Let
\[d= \sum\limits_{H \in \branchesin{\textup{in}}{S}} \left(\graphEndS{H} - \graphStartS{H} + 1\right).\]
In other words, $d$ is the sum of lengths of intervals in which the in-branches $H$ are contained in the path decomposition $\mathcal{P} = (X_1,X_2,\ldots,X_l)$.

For each in-branch $H_i$, for $i\in\{1,\ldots,l_{\textup{in}}\}$, we define the following sequence:
\[\mathcal{P}_i: = \left(X_{\graphStartS{H_i}}\cap V(H_i),\ldots, X_{\graphEndS{H_i}}\cap V(H_i)\right).\]
Since $\mathcal{P}$ is an $\mathcal{I}$-connected path decomposition of $G$, it is straightforward to observe that $\mathcal{P}_i$ is a $N_G(S)\cap V(H_i)$-connected path decomposition of $H_i$. We will denote the elements of $\mathcal{P}_i$ by
\[\mathcal{P}_i=\left(X_1^i,\ldots, X^i_{\graphEndS{H_i} - \graphStartS{H_i} + 1} \right).\]

Then, let us define a sequence $\mathcal{P}^*$ as follows:
\[\mathcal{P}^* := \prod_{i=1}^{l_{\textup{in}}} \; \mathcal{P}_i,\]
where $\prod$ denotes the concatenation of sequences. Observe that the length of $\mathcal{P}^*$ is exactly $d$. We will denote the elements of $\mathcal{P}^*$ by $\mathcal{P}^*=\left(X_{1}^*,\ldots,X^*_{d}\right)$.

Define $B^{\textup{in}}$ to be the set of vertices of the in-branches of $S$, i.e., $B^{\textup{in}} := \bigcup_{H \in \branchesin{\textup{in}}{S,\mathcal{P}}} V(H)$. Now, we define a path decomposition $F(S,\mathcal{P}) = \left(X'_1,\ldots,X'_{l + d + 1}\right)$ as follows:
\begin{numcases}{X_i'=}
X_i	& for $i \in \{1,\ldots, t_1 - 1\}$; \label{eq:prefix}\\
X_i \setminus B^{\textup{in}}		& for $i\in\{t_1,\ldots, \cMin - 1\}$; \label{eq:tillcmin}\\
X_{\cMin}\setminus B^{\textup{in}} & for $i = \cMin$; \label{eq:minimal1}\\
X^* \cup X_{i - \cMin}^*\cup S		 		& for $i\in\{\cMin + 1,\ldots, \cMin + d\}$; \label{eq:waiting}\\
X_{\cMin}\setminus B^{\textup{in}} & for $i = \cMin + d + 1$;\label{eq:minimal2}\\
X_{i - d - 1}\setminus B^{\textup{in}}	& for $i\in\{\cMin + d + 2,\ldots, t_2 + d + 1\}$; \label{eq:aftercmin}\\
X_{i - d - 1}										& $i\in\{t_2 + d + 2 ,\ldots, l + d + 1\}$. \label{eq:suffix}
\end{numcases}
Observe that $F(S,\mathcal{P})$ is obtained from $\mathcal{P}$ by a modification of the interval $[t_1,t_2]$ of $\mathcal{P}$. The prefix $(X_1,X_2,\ldots,X_{t_1-1})$ and the suffix $(X_{t_2+1},X_{t_2+2},\ldots,X_{l})$ of $\mathcal{P}$ are just copied into $F(S,\mathcal{P})$ without any changes (see conditions \eqref{eq:prefix} and \eqref{eq:suffix}).
All components of $G-S$, apart from the in-branches, are covered by bags on positions up to $\cMin-1$, see~\eqref{eq:tillcmin}, and after position $\cMin+d + 1$, see~\eqref{eq:aftercmin}, and they wait for $d + 2$ steps in the interval $[\cMin,\cMin+d + 1]$ of $F(S,\mathcal{P})$ --- see~\eqref{eq:minimal1}--\eqref{eq:minimal2}.
The interval $[\cMin +1,\cMin+d]$ is used in~\eqref{eq:waiting} to cover all in-branches, one by one, in the order of their appearance in $\mathcal{P}$. Additional two bags without any vertices of in-branches are added on positions $\cMin$ and $\cMin + d + 1$ to ensure that for any other bottleneck $S'$, such that $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$, we have that $\cMin(S',\mathcal{P}) \not\in I(S,\mathcal{P})$, see~\eqref{eq:minimal1} and~\eqref{eq:minimal2}. See Figure~\ref{fig:trans1} that illustrates the conversion from $\mathcal{P}$ to $F(S,\mathcal{P})$ for a bottleneck $S$.
Notice that the interval of $S$ in $\mathcal{P}'$ is given by $\botStart{S}{\mathcal{P}'} = \cMin + 1$  and $\botEnd{S}{\mathcal{P}'} = \cMin + d$, and it is possibly different than  $[t_1,t_2]$.
In the next lemma we show that $F(S,\mathcal{P})$ has all necessary properties.

  \begin{figure}[htb]
\centering
\begin{subfigure}{\textwidth}
  \centering
  \includegraphics[width=0.55\textwidth]{fig-trans1a.pdf}
  \caption{$S$-branches for a path decomposition $\mathcal{P}$ before transformation.}
  \label{fig:trans1b}
\end{subfigure}
\begin{subfigure}{\textwidth}
  \centering
  \includegraphics[width=0.85\textwidth]{fig-trans1b.pdf}
  \caption{New bags are inserted into $\mathcal{P}$ in which all components apart from in-branches wait in the interval of $S$ in $\mathcal{P}'$,  i.e., $C_2,C_3,H_2^{\textup{pre}}$ wait in $[\botStart{S}{\mathcal{P}'}, \botEnd{S}{\mathcal{P}'}]$.}
  \label{fig:trans1a}
\end{subfigure}
\caption{Illustration of the conversion from $\mathcal{P}$ to $\mathcal{P}' = F(S,\mathcal{P})$ for a bottleneck $S$. For simplification, $S$ is assumed to only have $8$ $S$-branches and $3$ components, which are denoted by letters $H$ and $C$, respectively, with appropriate indices.}
\label{fig:trans1}
\end{figure}

\begin{lemma}\label{lem:reorganizing}
For any $\mathcal{I}$-connected path decomposition $\mathcal{P}$ and a bottleneck $S$, $\mathcal{P}' = F(S,\mathcal{P})$ is an $\mathcal{I}$-connected path decomposition with $\width{\mathcal{P}'} \leq \width{\mathcal{P}}$.
\end{lemma}
\begin{proof}
Let us recall the notation: $\mathcal{P} := (X_1,\ldots, X_l)$, $\mathcal{P}' = F(S,\mathcal{P}) = (X_1',\ldots, X'_{l'})$, $t_1 = \botStart{S}{\mathcal{P}}$ and $t_2 = \botEnd{S}{\mathcal{P}}$, $B^{\textup{in}} := \bigcup_{H \in \branchesin{\textup{in}}{S,\mathcal{P}}} V(H)$.
Moreover, define
\[B^{\textup{not-in}}:=\left( \bigcup_{H \in \branchesin{\textup{pre}}{S,\mathcal{P}} \cup \branchesin{\textup{post}}{S,\mathcal{P}} \cup \mathcal{C}(S)} V(H) \right).\]
Also, recall that $X'_i = X_i,\ 1 \leq i < t_1$ and $X'_i = X_{i-d-1}$, for all $t_2 + d + 2 \leq i \leq l'$.

First, we want to show that $\mathcal{P}'$ satisfies conditions in Definition \ref{def:path_dec}.

Let $\{u,v\}$ be an edge of $G$. Since $\mathcal{P}$ is a path decomposition, $u,v \in X_i$ for some $i$.
If $i < t_1$, then $u,v \in X'_i=X_i$. If $i > t_2$, then $u,v \in X'_{i+d+1} =X_i$.

So suppose that $u,v \in X_i$ for $i \in [t_1,t_2]$.
Note that this means that $u,v \in B^{\textup{in}} \cup S$ or $u,v \in B^{\textup{not-in}} \cup S$.
If $u,v \in B^{\textup{not-in}} \cup S$, then we have
\begin{enumerate}[label=(\roman*)]
\item $u,v \in X'_i$, if $i \leq \cMin$;
\item $u,v \in X'_{i+d+1}$, otherwise.
\end{enumerate}

Finally, consider the case that, say, $u \in B^{\textup{in}}$ and $v \in B^{\textup{in}} \cup S$ (if both $u,v \in S$, then we are at the previous case). This means that $u$ is a vertex of some in-branch $H_s \in \branchesin{\textup{in}}{S,\mathcal{P}}$, so it appears in some bag of $\mathcal{P}_s$ and thus of $\mathcal{P}^*$. This implies that $u,v \in X'_j$ for some $j \in [\cMin + 1,\cMin+d]$. This implies that $\mathcal{P}'$ satisfies conditions \ref{it:path1} and \ref{it:path2} from Definition \ref{def:path_dec}.

Now let us verify that the condition \ref{it:path3} is also satisfied, i.e., for every vertex $v$ and indices $i < s < j$, such that $v \in X'_i \cap X'_j$ we have $v \in X'_s$. Clearly the condition is satisfied for every $v$ and  $j < t_1$ or $i > t_2$, since these parts of $\mathcal{P}'$ are just copied from $\mathcal{P}$ without any modifications.
The situation is very similar if $i \leq t_2$ and $j \geq t_1$ and $v \in \left ( S \cup B^{\textup{not-in}} \right ) \setminus X^*$. If $v \in X^*$, then $v$ is included in all bags $X'_s$ for $s \in [\cMin ,\cMin+d +1]$, so the condition \ref{it:path3} follows from the correctness of $\mathcal{P}$. Finally, if $v$ is a vertex of some $H_a \in \branchesin{\textup{in}}{S,\mathcal{P}}$, then the condition \ref{it:path3} follows from the property \ref{it:path3} that holds for the path decomposition $P_a$.

Next thing to show is that $\width{\mathcal{P}'} \leq \width{\mathcal{P}}$.
Let $c_1 = \card{X^*}$ and $c_2 = \max\limits_{i=t_1,\ldots,t_2} \card{B^{\textup{in}} \cap X_i}$, and let $k=\width{\mathcal{P}} +1 = \max\limits_{i=1,\ldots,l} \card{X_i}$. Observe that each $X'_i$ for $i  \notin \{t_1,\ldots,t_2+d + 1\}$ is an exact copy of some $X_j$, so $\card{X'_i} \leq k$. Moreover, each $X'_i$ for $i\in \{t_1,\ldots,\cMin\} \cup \{\cMin+d + 1,\ldots,t_2 + d + 1\}$ was obtained from some $X_j$ by removal of vertices of $B^{\textup{in}}$, so again we have $\card{X_i} \leq k$.
Finally, for $i \in \{\cMin + 1,\ldots,\cMin + d\}$ we have
\[
\card{X'_i} = \card{S} + \card{X^*} + \card{X_{i - \cMin}^*} \leq \card{S} + c_1 + c_2.
\]
However, by the definition of $\mathcal{P}^*$, we observe that $\card{S} + c_1 + c_2 \leq \card{X_j}$ for some $j \in \{t_1,\ldots,t_2\}$. Therefore, $\width{\mathcal{P}'} \leq \width{\mathcal{P}}$.

Finally, recall that $\mathcal{P}$ is $\mathcal{I}$-connected, i.e., $X_1$ is a one-element subset of $\mathcal{I}$. Observe that $X_{\botStart{S}{\mathcal{P}}}$ contains whole $S$ and at least one vertex from an $S$-branch (an in-branch, to be more specific). Since $S \neq \emptyset$, we conclude that $X_{\botStart{S}{\mathcal{P}}}$ cannot be $X_1$, so $X'_1 = X_1$ and therefore $\mathcal{P}'$ is $\mathcal{I}$-connected too.
\end{proof}

Observe that every connected component $H$ of $G-S$ is either contained in $I(S, \mathcal{P}')$ (which means that $H$ is an in-branch) or waits in $I(S, \mathcal{P}')$ (for all other $H$).

\begin{observation}\label{obs:structured}
For any $\mathcal{P}$ and bottleneck $S$, the path decomposition $F(S,\mathcal{P})$ is $S$-structured. \qed
\end{observation}

Now we want to define a series of transformations, which start at an arbitrary $\mathcal{I}$-connected path decomposition $\mathcal{P}$ and transform it into an $\mathcal{I}$-connected path decomposition with no larger width, which is $S$-structured for every $S \in \mathcal{S}$. For this, we will apply the $F$-transformations for all bottlenecks. In order to do this we need some technical lemmas about the structure of bottlenecks and their branches.

\begin{lemma}\label{lem:subsets_bottlenecks}
Let $S$ and $S'$ be two bottlenecks, such that $S'\subsetneq S$. There exists an $S'$-branch $H$ such that $\bigcup_{H' \in \branches{S}} V(H') \cup S  \setminus S' \subseteq V(H)$ and every $S'$-branch $H'$, different than $H$, is a non-branch connected component of $G-S$.
\end{lemma}
\begin{proof}
Let $S, S' \in \mathcal{S}$ such that $S'\subsetneq S$. Clearly $S$ intersects some connected component of $G-S'$.
Since every $S$-branch $H''$ is connected and $S\setminus S' \subset N_G(V(H''))$, we observe that two connected components of $G-S'$ can not be distinctive, i.e., there exists a connected component $H$ of $G-S'$ such that $\bigcup_{H' \in \branches{S}} V(H') \cup S  \setminus S' \subseteq V(H)$.

To see that $H$ is an $S'$-branch, consider a vertex $s' \in S'$. By assumption, $S'\subseteq S$ and hence $s'$ is also a vertex of $S$.
Thus, $s'$ has a neighbor in every $S$-branch $H'$, and thus in $H$. See Figure~\ref{fig:case1} for an illustration.

Now consider an $S'$-branch $H'' \neq H$. If every vertex of $S \setminus S'$ is adjacent to some vertex of $H''$,  then $H''$ is an $S$-branch, a contradiction. Thus, $H''$ is a connected component of $G-S$, which is not an $S$-branch.
\end{proof}

  \begin{figure}[htb]
  \centering
  \includegraphics[width=0.5\textwidth]{fig-case1.pdf}
  \caption{Illustration for Lemma~\ref{lem:subsets_bottlenecks}; $S$ and $S'$ are bottlenecks, such that  $S' \subsetneq S$. All $S$-branches are subgraphs of an $S'$-branch $H$ and every $S'$-branch, different than $H$, is a connected component of $G-S$, which is not an $S$-branch.  }
  \label{fig:case1}
\end{figure}

\begin{lemma}\label{lem:one_component}
For any two bottlenecks $S,S'$, if $S'\nsubseteq S$, then there exists exactly one connected component $H$ of $G-S$ such that $S'\subseteq S\cup V(H).$
\end{lemma}
\begin{proof}
Let $S, S' \in \mathcal{S}$ such that $S'\nsubseteq S$. Clearly $S'$ intersects some connected component of $G-S$. Suppose that $S'$ has a non-empty intersection with two connected components $H$ and $H'$ of $G-S$.
Thus, since every $S'$-branch  $H''$ is connected and $N_G(V(H''))=S'$, we observe that $H''$ contains a vertex of $S$ (otherwise $H,H'$ would not be two distinct components). Since $S'$-branches are vertex-disjoint, this implies that
the number of such $S'$-branches is at most $\card{S}$, which is in turn at most $k$ by Corollary \ref{cor:bottlenecks}. However, this contradicts the assumption that $S'$ is a bottleneck.
\end{proof}

The next remark is a straightforward consequence of Lemma~\ref{lem:subsets_bottlenecks} and Lemma~\ref{lem:one_component}.

\begin{remark}\label{rem:all_branches}
Let $S,S'$ be bottlenecks such that $S'\nsubseteq S$ and $S \nsubseteq S'$. Let $H$ be the connected component of $G-S$, such that $S'\subseteq S\cup V(H)$.
There exists exactly one connected component $C$ of $G-S'$ such that $\bigcup_{H' \in \branches{S} \setminus H} V(H') \cup S \setminus S' \subseteq V(C)$.
Moreover, all $S'$-branches but possibly  $C$ are subgraphs of $H$.
\qed
\end{remark}

See Figure~\ref{fig:case2-3} for the illustration for Lemma~\ref{lem:one_component} and Remark~\ref{rem:all_branches}.

\begin{figure}[htb]
\centering
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.83\textwidth]{fig-case2.pdf}
  \caption{$S \setminus S' \neq \emptyset$ and $S \cap S' \neq \emptyset$.}
  \label{fig:case2}
\end{subfigure}~~
\begin{subfigure}{0.5\textwidth}
  \centering
  \includegraphics[width=0.83\textwidth]{fig-case3.pdf}
  \caption{$S \cap S' = \emptyset$. }
  \label{fig:case3}
\end{subfigure}
\caption{Illustration of two cases for Lemma~\ref{lem:one_component} and Remark~\ref{rem:all_branches}; $S$ and $S'$ are bottlenecks. All $S$-branches (apart from $H$, which is a connected component of $G-S$, which may or may be not an $S$-branch) are subgraphs of $C$ and $S' \subseteq S \cup V(H)$.}
\label{fig:case2-3}
\end{figure}

We say two bottlenecks $S, S'$ are \emph{well-nested} in $\mathcal{P}$ if
\begin{enumerate}[label=\textup{(\roman*)}]
\item $I(S',\mathcal{P}) \subsetneq I(S,\mathcal{P})$ or
\item $I(S,\mathcal{P}) \subseteq I(S',\mathcal{P})$ or
\item $I(S,\mathcal{P}) \cap I(S',\mathcal{P}) = \emptyset$.
\end{enumerate}
Observe that the ordering of $S,S'$ in the definition above matters.

\begin{lemma} \label{lem:structured}
For any $\mathcal{I}$-connected path decomposition $\mathcal{P}$ and bottlenecks $S,S'$, if $\mathcal{P}$ is $S'$-structured, then $S$ and $S'$ are well-nested in $\mathcal{P}$.
Moreover, if $S \subsetneq S'$, then either $I(S,\mathcal{P}) \cap I(S',\mathcal{P}) = \emptyset$ or $I(S',\mathcal{P}) \subseteq I(S,\mathcal{P})$.
\end{lemma}
\begin{proof}
Let $\mathcal{P} = (X_1,\ldots,X_l)$ be an $\mathcal{I}$-connected path decomposition of $G$ and let $S, S' \in \mathcal{S}$. Suppose $\mathcal{P}$ is $S'$-structured.
Let us assume that $I(S',\mathcal{P}) \cap I(S,\mathcal{P}) \neq \emptyset$, we will show that either $I(S',\mathcal{P}) \subsetneq I(S,\mathcal{P})$ or $I(S,\mathcal{P}) \subseteq I(S',\mathcal{P})$.

\paragraph*{Case A: $S'\subsetneq S$.}
By Lemma~\ref{lem:subsets_bottlenecks}, there exists an $S'$-branch $H$ such that for every $S$-branch $H'$ it holds that $S \setminus S' \cup V(H')\subseteq V(H)$, and thus $[\graphStartS{H'},\graphEndS{H'}] \subseteq [\graphStartS{H},\graphEndS{H}]$. Recall that $\botStartS{S} = \graphStartS{H_1'}$ and $\botEndS{S} = \graphEndS{H_2'}$ for some in-branches $H_1',H_2' \in \branches{S}$, so $I(S,\mathcal{P}) = [\botStartS{S}, \botEndS{S}] \subseteq [\graphStartS{H},\graphEndS{H}]$.
Consider two subcases.
\subparagraph*{Subcase A1: $\graphStartS{H} \in I(S',\mathcal{P})$.}
Since $\mathcal{P}$ is $S'$-structured, we observe that $H$ is an in-branch for $S'$, which implies that $I(S,\mathcal{P}) \subseteq [\graphStartS{H},\graphEndS{H} ] \subseteq I(S',\mathcal{P})$.
\subparagraph*{Subcase A2: $\graphStartS{H} \notin I(S',\mathcal{P})$.}
First, observe that if $\graphStartS{H} > \botEndS{S'}$, then $\botStartS{S} > \botEndS{S'}$ and thus $I(S,\mathcal{P}) \cap I(S',\mathcal{P}) = \emptyset$, which contradicts our assumption. Analogously, if $\graphEndS{H} < \botStartS{S'}$, we again obtain that $I(S,\mathcal{P}) \cap I(S',\mathcal{P}) = \emptyset$.
Therefore assume that $\graphStartS{H} < \botStartS{S'} \leq \graphEndS{H}$. Observe that this implies that $H$ is a pre-branch for $S'$ and, since $\mathcal{P}$ is $S'$-structured, $H$ waits in $I(S',\mathcal{P})$. In particular $(S \setminus S') \cap X_{\botStartS{S'}} = (S \setminus S') \cap X_{\botStartS{S'}+1} = \ldots = (S \setminus S') \cap X_{\botEndS{S'}}$. Since $I(S',\mathcal{P}) \cap I(S,\mathcal{P}) \neq \emptyset$, it is necessary that $\botStartS{S} \leq \botStartS{S'}$ (otherwise $\botStartS{S} > \botEndS{S'}$).
 Thus, $\botStartS{S} \leq \botStartS{S'} \leq \botEndS{S'} \leq \botEndS{S}$ (recall $H$ waits in $I(S',\mathcal{P})$).
Summing up, if $S' \subsetneq S$, then either $I(S',\mathcal{P}) \subsetneq I(S,\mathcal{P})$ or $I(S,\mathcal{P}) \subseteq I(S',\mathcal{P})$, which completes the proof for this case.

\paragraph*{Case B: $S'\nsubseteq S$.}
By Lemma~\ref{lem:one_component}, there exists exactly one connected component $H$ of $G-S$ such that $S'\subseteq S\cup V(H)$.
Since $S'\nsubseteq S$, we observe that $V(H)\cap S'\neq\emptyset$.

If $H$ is an $S$-branch that is an in-branch in $\mathcal{P}$, then
\[I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}},\graphEnd{H}{\mathcal{P}}] \subseteq I(S, \mathcal{P}).\]
We observe that $I(S',\mathcal{P}) \subseteq I(S, \mathcal{P})$ is equivalent to $I(S',\mathcal{P}) \subsetneq I(S, \mathcal{P})$ or $I(S',\mathcal{P}) = I(S, \mathcal{P})$, thus $S$ and $S'$ are well-nested in $\mathcal{P}$. So assume that $H$ is a connected component of $G-S$, that is not an in-branch for $S$ (it may still be a pre- or a post-branch). We consider now two subcases.

\subparagraph*{Subcase B1: $S \subsetneq S'$.}
By Lemma~\ref{lem:subsets_bottlenecks}, all $S$-branches possibly except for $H$ are not $S'$-branches and all $S'$-branches are subgraphs of $H$.

Because $\mathcal{P}$ is $S'$-structured, every $S$-branch but possibly $H$ waits in $I(S',\mathcal{P})$.
In particular, every in-branch $H''$ for $S$ does wait in $I(S',\mathcal{P})$.
Thus, for every such an in-branch $H''$ it holds that $I(S',\mathcal{P})\subseteq [\graphStartS{H''},\graphEndS{H''}]$ or $I(S',\mathcal{P}) \cap [\graphStartS{H''},\graphEndS{H''}]=\emptyset$.
Note that the second condition implies that $I(S',\mathcal{P})\cap I(S,\mathcal{P})=\emptyset$, which contradicts our assumption.
Therefore  we obtain that $I(S',\mathcal{P})\subseteq [\graphStartS{H''},\graphEndS{H''}] \subseteq I(S,\mathcal{P})$.
Note that this shows the second claim of the lemma.

\subparagraph*{Subcase B2: $S \setminus S' \neq \emptyset$.} Let $C$ be the connected component of $G-S'$, for which it holds $\bigcup_{H' \in \branches{S}\setminus H} V(H') \cup S \setminus S' \subseteq V(C)$, whose existence is guaranteed by Remark~\ref{rem:all_branches}.

If $C$ is an in-branch for $S'$, we observe that $I(S,\mathcal{P}) \subseteq [\graphStartS{C}, \graphEndS{C}] \subseteq I(S',\mathcal{P})$, because $\mathcal{P}$ is $S'$-structured.
On the other hand, if $C$ is not an in-branch for $S'$, then all in-branches of $S$ wait in $I(S',\mathcal{P})$. This is because all subgraphs but in-branches of $S'$ wait in $I(S',\mathcal{P})$, and every in-branch for $S$ is vertex-disjoint with every in-branch for $H$, since they are all contained in $V(C) \cup S'$. Thus, since $I(S,\mathcal{P}) \cap I(S',\mathcal{P}) \neq \emptyset$, we conclude that $I(S',\mathcal{P}) \subseteq I(S,\mathcal{P})$, which completes the proof.
\end{proof}

In the next lemma, we show that we can apply a series of $F$-transformations, one for each bottleneck, so that the structure obtained in previous $F$-transformations is not 'destroyed' during the subsequent $F$-transformations.

\begin{lemma}\label{lem:final_structured}
Let $S,S'$ be bottlenecks and let $\mathcal{P}$ be an $S$-structured $\mathcal{I}$-connected path decomposition. Let $\mathcal{P}' = F(S',\mathcal{P})$.
\begin{enumerate}
\item If $I(S',\mathcal{P}) \subseteq I(S,\mathcal{P})$, then $\mathcal{P}'$ is $S$-structured and $I(S',\mathcal{P}') \subseteq I(S,\mathcal{P}')$. \label{case:nested}
\item If $\botEnd{S}{\mathcal{P}} < \botStart{S'}{\mathcal{P}}$, then $\mathcal{P}'$ is $S$-structured and $\botEnd{S}{\mathcal{P}'} < \botStart{S'}{\mathcal{P}'}$. \label{case:disjoint1}
\item If $\botEnd{S'}{\mathcal{P}} < \botStart{S}{\mathcal{P}}$, then $\mathcal{P}'$ is $S$-structured and $\botEnd{S'}{\mathcal{P}'} < \botStart{S}{\mathcal{P}'}$. \label{case:disjoint2}
\end{enumerate}
\end{lemma}
\begin{proof}
Let $\mathcal{P} = (X_1,\ldots,X_l)$ be an $\mathcal{I}$-connected path decomposition of $G$, let $S, S' \in \mathcal{S}$ and $\mathcal{P}' = F(S',\mathcal{P})$. Moreover, assume that $\mathcal{P}$ is $S$-structured.

First, let us prove case \ref{case:nested}, i.e. we assume that $I(S',\mathcal{P}) \subseteq I(S,\mathcal{P})$.
Observe that by Lemma \ref{lem:structured} we obtain that $S' \nsubseteq S$.
By Lemma~\ref{lem:one_component}, there exists exactly one connected component $H$ of $G-S$ such that $S' \subseteq S \cup V(H)$. We observe that $H$ is an in-branch for $S$, otherwise $H$ would wait in $I(S,\mathcal{P})$, which contradicts the assumption that $I(S',\mathcal{P}) \subseteq I(S,\mathcal{P})$ and that $\mathcal{P}$ is $S$-structured. We are going to show now that every $S'$-branch $H'$, which is an in-branch, is a subgraph of $H$. If $S \subsetneq S'$, then we obtain it immediately from Lemma~\ref{lem:subsets_bottlenecks}, so let $S \setminus S' \neq \emptyset$. Let $C$ be a connected component of $G-S'$, such that $\bigcup_{H' \in \branches{S}\setminus H} V(H') \cup S \setminus S' \subseteq V(C)$, whose existence is guaranteed by Remark~\ref{rem:all_branches}. Recall that $C$ might  or might not be an $S'$-branch, but for sure it is not an in-branch for $S'$, because then $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$, which is a contradiction. Thus, by Remark~\ref{rem:all_branches}, every in-branch for $S'$ is a subgraph of $H$.

Because every in-branch for $S'$ is a subgraph of $H$, we conclude that $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}]$ and the only changes made by the transformation $F(S',\mathcal{P})$ concern the vertices of $H \in \branchesin{\textup{in}}{S}$. Every connected component of $G-S'$, apart from in-branches (for $S'$), waits in $I(S',\mathcal{P}')$, so $F(S',\mathcal{P})$ is $S$-structured and $I(S',\mathcal{P}') \subseteq [\graphStart{H}{\mathcal{P}'}, \graphEnd{H}{\mathcal{P}'}]\subseteq I(S,\mathcal{P}')$.

To see that cases \ref{case:disjoint1} and \ref{case:disjoint2} hold as well, notice that the prefix $(X_1,X_2,\ldots,X_{\botStart{S'}{\mathcal{P}}-1})$ and suffix $(X_{\botEnd{S'}{\mathcal{P}}+1}, X_{\botEnd{S'}{\mathcal{P}}+2},\ldots,X_l)$ of $\mathcal{P}$ are just copied into $\mathcal{P}'$ without any changes.
\end{proof}

In the following lemma it is crucial that the path decomposition $\mathcal{P}$ is not only $S$-structured but has been obtained by by applying the transformation described in \eqref{eq:prefix}-\eqref{eq:suffix} to $\mathcal{P}_0$. In particular, the bags added in \eqref{eq:minimal1} and~\eqref{eq:minimal2} will play a crucial role in ensuring that the path decomposition returned by $F(S',\mathcal{P})$ remains $S$-structured.
\begin{lemma}\label{lem:final_structured2}
Let $S,S'$ be bottlenecks and let $\mathcal{P}_0$ be any $\mathcal{I}$-connected path decomposition. Let $\mathcal{P} = F(S, \mathcal{P}_0)$ and $\mathcal{P}' = F(S',\mathcal{P})$.
If $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$, then $\mathcal{P}'$ is $S$-structured and $I(S,\mathcal{P}') \subseteq I(S',\mathcal{P}')$ or $I(S,\mathcal{P}') \cap I(S',\mathcal{P}') = \emptyset$.
\end{lemma}
\begin{proof}
Let $\mathcal{P} = (X_1,\ldots,X_l)$ be an $\mathcal{I}$-connected path decomposition of $G$, let $S, S' \in \mathcal{S}$ and $\mathcal{P}' = F(S',\mathcal{P})$. Moreover, assume that $\mathcal{P} = F(S, \mathcal{P}_0)$ for some $\mathcal{I}$-connected path decomposition $\mathcal{P}_0$. In particular, this implies that $\mathcal{P}$ is $S$-structured.
Finally, assume that $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$.

\paragraph*{Case A: $S' \subsetneq S$.} By Lemma~\ref{lem:subsets_bottlenecks} there exists an $S'$-branch $H$ such that $\bigcup_{H' \in \branches{S}} V(H') \cup S  \setminus S' \subseteq V(H)$.
If $H$ is an in-branch for $S'$ then $I(S,\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}] \subsetneq I(S',\mathcal{P})$.
However, recall that $F$-transformation applied to $S'$ and $\mathcal{P}$ does not change the structure of the bags restricted to $H$ (or any other in-branch of $S'$). Therefore we conclude that $I(S,\mathcal{P}') \subseteq [\graphStart{H}{\mathcal{P}'}, \graphEnd{H}{\mathcal{P}'}] \subsetneq I(S',\mathcal{P}')$ and $\mathcal{P}'$ is $S$-structured.

Now assume that $H$ is a pre-branch or a post-branch for $S'$. From the construction of $\mathcal{P}$ we have that $\cMin{(S',\mathcal{P})} \not\in I(S,\mathcal{P})$.
Because every in-branch $H'$ for $S'$ either waits in $I(S,\mathcal{P})$ or $[\graphStart{H'}{\mathcal{P}}, \graphEnd{H'}{\mathcal{P}}] \cap I(S,\mathcal{P}) = \emptyset$, we obtain that $I(S,\mathcal{P}') \cap I(S',\mathcal{P}') = \emptyset$ and $\mathcal{P}'$ is $S$-structured.

\paragraph*{Case B: $S' \nsubseteq S$ and $S \nsubseteq S'$.}
By Lemma~\ref{lem:one_component} there exists exactly one connected component $H$ of $G-S$ such that $S' \subseteq S \cup V(H)$. Because $V(H) \cap S' \neq \emptyset$ we have that $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}]$. We observe that $H$ cannot be an in-branch for $S$, otherwise $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}] \subseteq I(S, \mathcal{P})$, which contradicts the assumption that $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$.
Thus, $H \not\in \branchesin{\textup{in}}{S}$.

From the facts that $\mathcal{P}$ is $S$-structured and $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}]$, we observe that $H$ waits in $I(S,\mathcal{P})$.
By Remark~\ref{rem:all_branches} there exists a connected component $C$ of $G-S'$ such that $\bigcup_{H' \in \branches{S} \setminus H} V(H') \cup S \setminus S' \subseteq V(C)$. Because $H$ is not an in-branch for $S$, all in-branches of $S$ are subgraphs of $C$. If $C$ is an in-branch for $S'$ then $I(S,\mathcal{P}) \subseteq [\graphStart{C}{\mathcal{P}}, \graphEnd{C}{\mathcal{P}}] \subsetneq I(S',\mathcal{P})$. Because $F$-transformation does not change bags inside one in-branch, we have that $I(S,\mathcal{P}') \subseteq [\graphStart{C}{\mathcal{P}'}, \graphEnd{C}{\mathcal{P}'}] \subsetneq I(S',\mathcal{P}')$ and $\mathcal{P}'$ is $S$-structured. On the other hand, assume that $C$ is not an in-branch for $S'$. From construction of $\mathcal{P}$ we have that $\cMin{(S',\mathcal{P})} \not\in I(S,\mathcal{P})$ Because every in-branch $H'$ for $S'$ either waits in $I(S,\mathcal{P})$ or $[\graphStart{H'}{\mathcal{P}}, \graphEnd{H'}{\mathcal{P}}] \cap I(S,\mathcal{P}) = \emptyset$, we obtain that $I(S,\mathcal{P}') \cap I(S',\mathcal{P}') = \emptyset$ and $\mathcal{P}'$ is $S$-structured.

\paragraph*{Case C: $S \subsetneq S'$.} From Lemma~\ref{lem:subsets_bottlenecks} there exists an $S$-branch $H$ such that $\bigcup_{H' \in \branches{S'}} V(H') \cup S'  \setminus S \subseteq V(H)$, i.e., $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}]$. We observe that $H$ cannot be an in-branch for $S$, otherwise $I(S',\mathcal{P}) \subseteq [\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}] \subseteq I(S, \mathcal{P})$, which contradicts the assumption that $I(S,\mathcal{P}) \subsetneq I(S',\mathcal{P})$.

Let then $H$ be a pre-branch or a post-branch for $S$, which means that $H$ waits in $I(S,\mathcal{P})$ (notice that it is impossible that $[\graphStart{H}{\mathcal{P}}, \graphEnd{H}{\mathcal{P}}] \cap I(S,\mathcal{P}) = \emptyset$, because then  $ I(S',\mathcal{P}) \cap I(S,\mathcal{P}) = \emptyset$). From construction of $\mathcal{P}$ we have that $\cMin{(S',\mathcal{P})} \not\in I(S,\mathcal{P})$. Because every in-branch $H'$ for $S'$ either waits in $I(S,\mathcal{P})$ or $[\graphStart{H'}{\mathcal{P}}, \graphEnd{H'}{\mathcal{P}}] \cap I(S,\mathcal{P}) = \emptyset$, we obtain that $I(S,\mathcal{P}') \cap I(S',\mathcal{P}') = \emptyset$ and $\mathcal{P}'$ is $S$-structured.
\end{proof}

Now we are ready to prove  Lemma~\ref{lem:main_transformation}.

\begin{proof}[Proof of Lemma~\ref{lem:main_transformation}.] Let $\mathcal{P}$ be an $\mathcal{I}$-connected path decomposition. Let $\mathcal{S} = \{S_1,S_2,\ldots,S_{n'}\}$ be the set of all bottlenecks.
We define a path decomposition $\mathcal{P}' := \mathcal{P}_{n'}$ in the following, recursive way:
\begin{align*}
\mathcal{P}_0 &= \mathcal{P}; \\
\mathcal{P}_i &= F(S_i,\mathcal{P}_{i-1}),\ \text{ for } i \in \{1,\ldots,n'\}.
\end{align*}

We are going to prove now that $\mathcal{P}_q$ is $S_j$-structured and $S_i, S_j$ are well-nested in $\mathcal{P}_q$
for every $1 \leq j \leq q \leq n'$ and $1 \leq i \leq n'$.

Induction on $q$. If $q=1$, then obviously $j=1$ and thesis holds for every $1 \leq i \leq n'$ from Lemma~\ref{lem:structured}.
So assume that $q > 1$ and the claim holds for $q - 1$.

Let $j \in \{1,\ldots,q - 1\}$. For every $S_j$
we have, by the induction assumption, that $S_q, S_j$ are well-nested in $\mathcal{P}_{q-1}$ and $\mathcal{P}_{q-1}$ is $S_j$-structured.
By Lemma~\ref{lem:final_structured2}, if $I(S_j,\mathcal{P}_{q-1}) \subsetneq I(S_q,\mathcal{P}_{q-1})$, then  $\mathcal{P}_q = F(S_q,\mathcal{P}_{q-1})$ is $S_j$-structured.
By Lemma~\ref{lem:final_structured}, if $I(S_q,\mathcal{P}_{q-1}) \subseteq I(S_j,\mathcal{P}_{q-1})$  or  $I(S_j,\mathcal{P}_{q-1}) \cap I(S_q,\mathcal{P}_{q-1}) = \emptyset$, then  $\mathcal{P}_q = F(S_q,\mathcal{P}_{q-1})$ is $S_j$-structured.

Because $\mathcal{P}_q$ is $S_j$-structured, then from Lemma~\ref{lem:structured} for any $i \in \{1,\ldots,n'\}$ we have that $S_i, S_j$ are well-nested in $\mathcal{P}_q$.

So $\mathcal{P}'$ is $S$-structured for every bottleneck $S \in \mathcal{S}$.
Note that Lemma~\ref{lem:reorganizing} ensures that $\mathcal{P}'$ is an $\mathcal{I}$-connected path decomposition of width at most $\width{\mathcal{P}}$, which finishes the proof.
\end{proof}

Now we are ready to show the correctness of our algorithm. We will prove it in two steps.

\begin{lemma} \label{lem:induction-dec-totab}
If $G$ has an $\mathcal{I}$-connected path decomposition of width at most $k-1$, then $Tab[s]=true$ for some state $s$ such that $\cover{s} = V(G)$.
\end{lemma}
\begin{proof}
Suppose that $G$ has an $\mathcal{I}$-connected path decomposition of width $k-1$.
By Lemma~\ref{lem:main_transformation}, there exists an $\mathcal{I}$-connected path decomposition $\mathcal{P}=(X_1,\ldots,X_l)$ that has width $k-1$ and is $S$-structured for each bottleneck $S$.

By Lemma~\ref{lem:structured}, the set $\mathcal{S}$ of all bottlenecks with relation $S \prec S'$ if and only if $I(S,\mathcal{P}) \subseteq I(S',\mathcal{P})$ forms a partial order (a assuming that any ties, i.e., when $I(S,\mathcal{P})=I(S',\mathcal{P})$ are resolved arbitrarily).
Let $S_1,\ldots,S_t$ be the maximal elements with respect to this partial order.
Note that for $i\neq j$, $I(S_i,\mathcal{P})\cap I(S_j,\mathcal{P}) = \emptyset$ and for any bottleneck $S'\notin\{S_1,\ldots,S_t\}$ we have $I(S',\mathcal{P})\subseteq I(S_i,\mathcal{P})$ for some $i\in\{1,\ldots,t\}$.
Assume without loss of generality that the `maximal' bottlenecks are ordered according to the left endpoints of their intervals,
\[\botStartS{S_1} \leq \botStartS{S_2} \leq \cdots \leq \botStartS{S_t}.\]

We show how to arrive at the desired state $s$.
To that end we argue, by induction on $j$, that for each
\[j\in J:=\{1,\ldots,l\}\setminus\bigcup_{i=1}^{k}\left\{\botStartS{S_i},\ldots,\botEndS{S_i}-1\right\}\]
there exists a state $s_j$ such that $\cover{s_j}=G[X_1\cup\cdots\cup X_j]$, $\bag{s_j}=X_j$ and $Tab[s_j]=true$.

Since the first bag of $\mathcal{P}$ consists of a vertex in $\mathcal{I}$, this clearly holds for $j=1$ so take $j>1$ and assume that the claim is true for each $j'\in J\cap\{1,\ldots,j-1\}$.
We consider two cases.
In the first case suppose that $j\notin I(S_i,\mathcal{P})$ for each $i\in\{1,\ldots,t\}$.
Hence we have $j-1\in J$.
This implies, according to Lemma~\ref{lem:small}, that for each bottleneck $S$, either there are at most $2k$ $S$-branches $H$ such that $\graphStartS{H}\leq j$, or there are at most $2k$ $S$-branches such that $j\leq\graphEndS{H}$.
Thus, there exists a state $s_{j}$ such that $\cover{s_{j}}=G[X_1\cup\cdots\cup X_{j}]$ and $\bag{s_{j}}=X_{j}$.
The step extension rule and $Tab[s_{j-1}]=true$, which holds by the induction hypothesis, imply $Tab[s_{j}]=true$ as required.

In the second case we have $j\in I(S_i,\mathcal{P})$ for some bottleneck $S_i$.
By the definition of the set $J$, $j=\botEndS{S_i}$.
Hence, the preceding index of $j$ in the set $J$ is $j'=\botStartS{S_i}-1$.
Again, by the definition of $I(S_i,\mathcal{P})$, Lemma~\ref{lem:small}, and the maximality of $S_i$ with respect to the partial order, we have that for each bottleneck set $S$ either at most $2k$ $S$-branches $H$ satisfy $\graphStartS{H}\leq j'$, or at least $|\branches{S_{i'}}|-2k$ $S$-branches $H$ are contained in $[1,j']$, i.e., satisfy $\graphEndS{H}\leq j'$, depending whether $\botEndS{S}\leq j'$ or $\botStartS{S}>j'$.
Thus, there exists a state $s_{j}$ such that $\cover{s_j}=G[X_1\cup\cdots\cup X_j]$ and $\bag{s_j}=X_j$.
Consider the jump extension rule constructed for $S'=S_i$.
For the set $B_{S'}$ in~\ref{jump:green} and~\ref{jump:otherS} take all $S'$-branches that are not in-branches, i.e., those that are covered in $[j'+1,j]$ in $\mathcal{P}$.
Note that each $S$-branch of each bottleneck $S\neq S_i$ such that $S\subseteq X_{j'}$ waits in the interval $I(S_i,\mathcal{P})$ because $\mathcal{P}$ is $S_i$-structured, which ensures the condition \ref{jump:other}.
Condition~\ref{jump:rec} holds because the decomposition $\mathcal{P}_H$ in~\ref{jump:rec} exists which is certified by the decomposition $\mathcal{P}$, namely $\mathcal{P}_H=(X_{\graphStartS{H}}\cap V(H),\ldots,X_{\graphEndS{H}}\cap V(H))$.
Thus, $Tab[j']=true$ (which holds by the induction hypothesis) ensures that $Tab[j]=true$.

Finally observe that $l\in J$, $\cover{s_{l}}=G[X_1\cup\cdots\cup X_l]=V(G)$ and $Tab[s_l]=true$.
Thus, $s=s_l$ is the required state.
\end{proof}

\begin{lemma} \label{lem:induction-tab-todec}
For any state $s$, if $Tab[s]=true$, then $G_s$ has an $\mathcal{I}$-connected path decomposition of width at most $k-1$.
\end{lemma}

\begin{proof}
Proof by induction on the position of $s$ in the ordering $\prec_s$. First, let $\cover{s} = \{v\}$ for some $v \in V(G)$ (notice that such states are smallest, according to $\prec_s$).
If $v \in \mathcal{I}$, then $Tab[s]$ was set true in the initialization step. This is justified by considering connected path decomposition consisting of a single bag $\{v\}$, which is a proper connected path decomposition of the single-vertex graph $(\{v\},\emptyset)$.
On the other hand, if $v \notin \mathcal{I}$, then $Tab[s]$ is never set $true$, as the extension rules apply only to states with $|\cover{s}| > 1$.
This is also correct, as no decomposition of $G_s$ contains a vertex of $\mathcal{I}$.

Now suppose that $|\cover{s}| \geq 2$, and the Lemma holds for all states $w \prec_s s$. Since $Tab[s]=true$, its value must have been set by one of the extension rules. Consider two cases.

\paragraph{Case 1: $Tab[s]$ was set by step extension.}
Consider the state $w$. If $\bag{s} \not\subseteq \bag{w}$, then since by~\ref{step:4}, $\bag{s} \cap \cover{w} \subseteq \bag{w}$, we have that $\bag{s} \not\subseteq \cover{w}$. Therefore, $\cover{s} = \cover{w} \cup \bag{s}$ implies that $|\cover{s}| > |\cover{w}|$, which means that $w \prec_s s$.
On the other hand, if $\bag{s} \subseteq \bag{w}$, we have $\cover{s} = \cover{w}$ due to~\ref{step:3}. However, since $s$ and $w$, are distinguishable, we have $\bag{s} \subsetneq \bag{w}$, so $|\bag{s}| < |\bag{w}|$ and thus $w \prec_s s$.

So, by the inductive assumption, $Tab[w]$ was set properly and there exists an $\mathcal{I}$-connected path decomposition $\mathcal{P} = (X_1,X_2,\ldots,X_l)$ of $G_w$ that has width at most $k-1$, where $X_l = \bag{w}$. Let $X_{l+1} := \bag{s}$ and let $\mathcal{P}' := (X_1,X_2,\ldots,X_l,X_{l+1})$.

We claim that $\mathcal{P}'$ is an $\mathcal{I}$-connected path decomposition of $G_s$.
Indeed, $\bigcup_{i=1}^{l+1} X_i = \bigcup_{i=1}^{l} X_i \cup X_{l+1} = \cover{w} \cup \bag{s} = \cover{s}$.
Now, consider an edge $vu$ of $G_s$. If both $v,u$ belong to $\cover{w}$, they appear in some $X_i$ for $i \leq l$ (by the inductive assumption). If both $v,u$ belong to $\bag{s}$, we are done too. Finally, if $v \in \cover{w}$ and $u \in \bag{s} \setminus \cover{w}$, we know from~\ref{step:2} that $v \in \border{w} \subseteq \bag{s}$, so we are again in the previous case.
Now suppose for a contradiction that there are some $1 \leq i < j \leq l$, such that $X_i \cap X_{l+1} \not\subseteq X_j$. This means that $\bag{s}=X_{l+1}$ contains a vertex of $\cover{w} \setminus \bag{w}$, which is a contradiction with~\ref{step:4}.

Moreover, since $\width{\mathcal{P}} \leq k-1$ and $|\bag{s}| \leq k$, we have $\width{\mathcal{P}'} \leq k-1$. Finally, since $\mathcal{P}$ is $\mathcal{I}$-connected and (according to~\ref{step:1}) every connected component of $X_{l+1}$ either contains a vertex of $X_l$, or is adjacent to one, or belongs to $\mathcal{I}$, we observe that $\mathcal{P}'$ is also $\mathcal{I}$-connected.
Finally, we immediately obtain from induction hypothesis that $\mathcal{P}'$ starts with $\mathcal{I}$.
This justifies setting $Tab[s]=true$.

\paragraph{Case 2: $Tab[s]$ was set by jump extension.}
Let $w=(X,\{B_S\}_S,\{f^B_S\}_S)$, $s=(X,\{B_S\}_S,\{g^B_S\}_S)$ and let $S' \subseteq X$ be defined as in the definition of the jump extension. To simplify the notation, set $\mathcal{B}' := \branches{S'} \setminus B_{S'} = \{H_1,H_2,\ldots,H_m\}$.
Observe that since $S'$ is a bottleneck, we have $|\branches{S'}| \geq 2k+1$, thus there is at least one $H \in \mathcal{B}'$.
Since $V(H) \not\subseteq \cover{w}$ and $V(H) \subseteq \cover{s}$ by~\ref{jump:green} and \ref{jump:other}, we have $|\cover{w}| < |\cover{s}|$ and thus $w \prec_s s$. So, by the inductive assumption, $Tab[w]$ was set properly to be $true$ and there exists an $\mathcal{I}$-connected path decomposition $\mathcal{P} = (X_1,X_2,\ldots,X_l)$ of $G_w$ with width at most $k-1$, where $X_l = X = \bag{w}$. By~\ref{jump:rec}, for every $H \in \mathcal{B}'$ there is a path decomposition $\mathcal{P}_H = (X^H_1,X^H_2,\ldots,X^H_{l(H)})$ of width at most $k-|X|-1$, such that $X^H_1$ contains a neighbor of $S'$, i.e., $\mathcal{P}_H$ is $N_G(S')\cap V(H)$-connected.

We claim that
\[ \mathcal{P}' = \mathcal{P} \circ \left(\prod_{i=1}^m \prod_{j=1}^{l(H_i)} (X_l \cup X^{H_i}_j)\right) \circ X_l,
\]
where both $\circ$ and $\prod$ denote concatenation of appropriate sequences, is an $\mathcal{I}$-connected path decomposition of $G_s$ of width at most $k-1$.

First, observe that $\cover{s} = \cover{w} \cup \bigcup_{H \in \mathcal{B}'} V(H)$ due to~\ref{jump:otherS} and~\ref{jump:other}. By the definition of $\mathcal{P}$ and decompositions $\mathcal{P}_H$ for $H \in \mathcal{B}'$, we observe that $\mathcal{P}'$ covers exactly $\cover{s}$.

Now consider an edge $vu$ of $G_s$. If both vertices $v,u$ belong to $\cover{w}$, or to $V(H)$ for some $H \in \mathcal{B}'$, then, by the definition of $\mathcal{P}$ and $\mathcal{P}_H$, both $v$ and $u$ appear in some bag of the decomposition $\mathcal{P}'$.
If $v \in \cover{w}$ and $u \in V(H)$ for some $H \in \mathcal{B}'$, then we know that $v \in \border{w}$ and therefore $v \in X_l$, so both vertices appear in every bag containing $u$. Finally, we observe that there are no edges joining vertices from different $S'$-branches.

The third condition of the definition of path decomposition follows directly from the definition of $\mathcal{P}$ and $\mathcal{P}_H$ and the fact that subgraphs $H$ are $S'$-branches.

Observe that $|X_i| \leq k-1$ for $i \leq l$ (by the definition of $\mathcal{P}$), and since $|X^H_j| \leq k-|X|-1$ for every $H$ and $j$, we have $| X \cup X^H_j| \leq k-1$, so $\width{\mathcal{P}'} \leq k-1$.

Note that $\mathcal{P}$ is $\mathcal{I}$-connected according to the induction hypothesis. Moreover, each $\mathcal{P}_H$ is $N_G(S')\cap V(H)$-connected for each $H \in \mathcal{B}'$ for some $S' \subseteq X$.
Thus, $\mathcal{P}'$ is $\mathcal{I}$-connected.

This completes the proof.
\end{proof}

Combining Lemmas \ref{lem:induction-dec-totab} and \ref{lem:induction-tab-todec}, we obtain the following corollary.
\begin{corollary}\label{cor:correct}
The algorithm is correct, i.e., the value of $Tab[s]$ is $true$ for some state $s$ with $\cover{s}=V(G)$ if and only if $\cpw{G}\leq k-1$.
\qed
\end{corollary}

Now let us estimate the computational complexity of our algorithm.
\begin{lemma}\label{lem:complexity}
For every fixed $k \geq 1$, a graph $G$ with $n$ vertices, and $\mathcal{I} \subseteq V$, there is an algorithm deciding in time $f(k) \cdot n^{O(k^2)}$ whether $G$ has an $\mathcal{I}$-connected path decomposition of width at most $k-1$, where $f$ is a function depending on $k$ only.
\end{lemma}

\begin{proof}
We do induction on $k$.
First, observe that for a connected graph $G$, $\cpw{G} = 0$ if and only if $G$ is a single-vertex graph.
Moreover, $\cpw{G} = 1$ if and only if $G$ is a caterpillar, and optimal connected path decompositions of caterpillars have very simple structure, so we can verify in polynomial time whether there is an $\mathcal{I}$-connected one.

So assume that $k \geq 2$ and that the claim holds for $k-1$.
For every vertex $s^* \in V$, we run the dynamic programming algorithm that we described in Section~\ref{sec:algorithm}.
The correctness of the algorithm follows from Corollary \ref{cor:correct}. Now let us estimate its computational complexity.
Recall that the total number of states is $O(n^{3k})$, so the total number of pairs of states is $O(n^{6k})$. For each pair of states we check if one of the two extension rules can be applied.

Observe that for each state $s$, we can compute $\cover{s}$, $\bag{s}$ and $\border{s}$ in polynomial time. Thus checking if the step extension can be applied can also be done in polynomial time.

Now consider the possible jump extension from a state $w$ to a state $s$.
Verifying the first three conditions can be clearly done in polynomial time. We check in~\ref{jump:rec} if the appropriate path decomposition $\mathcal{P}_H$ of each $S'$-branch $H$ exists by calling the algorithm recursively with the initial set $N_G(S')\cap V(H)$. By the inductive assumption, this can be done in total time bounded by $n^{O(1)} \cdot f'(k-1) n^{c \cdot (k-1)^2}$, for some function $f'$ and a constant $c'$.
This gives total time complexity
\[n^{O(1)} \cdot n^{6k} \cdot f'(k-1) \cdot n^{c' (k-1)^2} = f(k) \cdot n^{O(k^2)}\]
for some function $f$.
\end{proof}

Now, the main result of the paper follows easily from Lemma \ref{lem:complexity}.
\begin{theorem}\label{thm:main}
For every fixed $k \geq 1$, there is an algorithm deciding in time $f(k) \cdot n^{O(k^2)}$ whether $\cpw{G} \leq k-1$, for some function $f$ depending on $k$ only, i.e., in time polynomial in $n$.
\end{theorem}

\begin{proof}
For every vertex $s^* \in V$, we run the dynamic programming algorithm for $\mathcal{I} = \{s^*\}$, i.e., we exhaustively guess a vertex in the first bag of some fixed solution.
By Lemma \ref{lem:complexity}, the total running time is as claimed.
\end{proof}

Let us point out that we did not try to optimize the dependence of the degree of the polynomial function in Theorem \ref{thm:main} on $k$, as we were only interested in finding a polynomial algorithm.

\section{Open problems} \label{sec:open-problems}

As pointed out, both pathwidth and connected pathwidth are asymptotically the same for an arbitrary graph $G$, namely $\cpw{G}/\pathwidth{G}\leq 2+o(1)$.
However, there are several open questions regarding the complexity of exact algorithms for connected pathwidth.
One such immediate question that is a natural next step in the context of our work is whether connected pathwidth is FPT with respect to this parameter?
Also, it is not known if connected pathwidth can be computed faster than in time $O^*(2^n)$ for an arbitrary $n$-vertex graph (recall that this is possible for pathwidth).

The notion of connected pathwidth appeared in the context of pursuit-evasion games called node search, edge search or mixed search.
A challenging and long-standing open question related to those games is whether their connected variants belong to NP?
See~\cite{BFFFNST12} for more details regarding this question.

\section*{Acknowledgements}
This research has been partially supported by National Science Centre (Poland) grant number 2015/17/B/ST6/01887.

\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


Tips for Taking Care of a Horse.
For some of us, it is logical to say that we have wished to own a horse since childhood. With some of us, therefore, it is critical to say that we have been accumulating funds with intention of buying a horse. To learn more about taking care of the animal, read more now here.
When it comes to costs of taking care of a horse, there is a need to say that such is increased. The initial cost of acquiring the animal is exaggerated and the costs do not stop there. Taking care of the animal is equally expensive as you have to ensure that the animal is well fed, maintained, trained as well as its medical expenses are met. Consequently, you may expect to spend thousand dollars when it comes to taking care of the animal. However, there exist these tips that can come in handy for those seeking to reduce such costs that you can learn.
In the second place, it is logical to mention that taking care of the animal is long lasting. One thing that you need to know is that the animal will depend on you for care. Usually, the lifespan of a horse may range from twenty to thirty years during which you ought to take care of the animal. To add to this, those that may be planning to travel, you may need to appoint a person who will help you take care of the animal as it needs daily care.
Again, the space needed is huge. One of the elements that make such a detail crucial is the fact that the animal needs to exercise. If you own a horse and you live in an area that is crowded, you may need to find an extra space. Some of the elements that call for a lot of space include feeding and equipment to be used in this line.
Significantly, understand the animal needs a lot of specialized medical care. When you consider taking care of the horse as a first timer, this is not a hobby you will like. Such ensure the detail that the animal has a list of special requests that they want to be met. For this reason, some of the key medical areas that need a lot of attention are the hooves as well as their dental formula. In a case where they are hurt, they may need emergency care from a professional in this line.
Finally, understand that the animal has a lot of appetites. One of the elements that you need to ensure that there is continuous supply is the hay and supplements. On the other hand, you have a duty to make sure that you ensure balance the hay, grains and the pastures that the animal get.


text:
Q: How can I cancel a Device.BeginInvokeOnMainThread()? I have this code:
Device.BeginInvokeOnMainThread(() => Show().ContinueWith((arg) => { }));

public async Task Show()
{
   while (true)
   {
      await Task.Delay(500);
      Debug.WriteLine("test1");
      while (true)
      {
         await Task.Delay(500);
         Debug.WriteLine("test2");
      }
   }
}

I know if I have a task that I can cancel it but for this code. How can I cancel the execution of Show() if for example it was running in a loop and I wanted to cancel from outside of that method?
Note that I added
.ContinueWith((arg)

As it stops my IDE from giving an error.
For reference here's the class for DEVICE from Xamarin
public static class Device
{
    //
    // Static Fields
    //
    public const string iOS = "iOS";

    public const string Android = "Android";

    public const string WinPhone = "WinPhone";

    public const string UWP = "UWP";

    public const string WinRT = "WinRT";

    public const string macOS = "macOS";

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static DeviceInfo info;

    private static IPlatformServices s_platformServices;

    //
    // Static Properties
    //
    [EditorBrowsable (EditorBrowsableState.Never)]
    public static IReadOnlyList<string> Flags {
        [CompilerGenerated]
        get;
        [CompilerGenerated]
        private set;
    }

    public static TargetIdiom Idiom {
        [CompilerGenerated]
        get;
        [CompilerGenerated]
        internal set;
    }

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static DeviceInfo Info {
        get;
        set;
    }

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static bool IsInvokeRequired {
        get;
    }

    [Obsolete ("TargetPlatform is obsolete as of version 2.3.4. Please use RuntimePlatform instead.")]
    public static TargetPlatform OS {
        get;
    }

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static IPlatformServices PlatformServices {
        get;
        set;
    }

    public static string RuntimePlatform {
        get;
    }

    //
    // Static Methods
    //
    public static void BeginInvokeOnMainThread (Action action);

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static Assembly[] GetAssemblies ();

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static double GetNamedSize (NamedSize size, Type targetElementType, bool useOldSizes);

    public static double GetNamedSize (NamedSize size, Element targetElement);

    public static double GetNamedSize (NamedSize size, Type targetElementType);

    internal static Task<Stream> GetStreamAsync (Uri uri, CancellationToken cancellationToken);

    [Obsolete ("OnPlatform is obsolete as of version 2.3.4. Please use switch(RuntimePlatform) instead.")]
    public static void OnPlatform (Action iOS = null, Action Android = null, Action WinPhone = null, Action Default = null);

    [Obsolete ("OnPlatform<> (generic) is obsolete as of version 2.3.4. Please use switch(RuntimePlatform) instead.")]
    public static T OnPlatform<T> (T iOS, T Android, T WinPhone);

    public static void OpenUri (Uri uri);

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static void SetFlags (IReadOnlyList<string> flags);

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static void SetIdiom (TargetIdiom value);

    [EditorBrowsable (EditorBrowsableState.Never)]
    public static void SetTargetIdiom (TargetIdiom value);

    public static void StartTimer (TimeSpan interval, Func<bool> callback);

    //
    // Nested Types
    //
    public static class Styles
    {
        public static readonly string TitleStyleKey;

        public static readonly string SubtitleStyleKey;

        public static readonly string BodyStyleKey;

        public static readonly string ListItemTextStyleKey;

        public static readonly string ListItemDetailTextStyleKey;

        public static readonly string CaptionStyleKey;

        public static readonly Style TitleStyle;

        public static readonly Style SubtitleStyle;

        public static readonly Style BodyStyle;

        public static readonly Style ListItemTextStyle;

        public static readonly Style ListItemDetailTextStyle;

        public static readonly Style CaptionStyle;
    }
}

A: It's not really related to Device, but how to cancel an Action.
You would use CancellationTokenSource. (Since it's in Xamarin's doc, I believe it's available for you to use)
private CancellationTokenSource _cts;

void Handler1()
{
    _cts = new CancellationTokenSource();
    Device.BeginInvokeOnMainThread(() => Show(_cts.Token).ContinueWith((arg) => { }));
}

void Handler2()
{
    if (_cts != null)
    {
        _cts.Cancel(); // <---- Cancel here
    }
}

public async Task Show(CancellationToken ct)
{
    while (true)
    {
        await Task.Delay(500, ct); // <-- Thanks to @Evk's suggestion
        Debug.WriteLine("test1");

        if (ct.IsCancellationRequested)
        {
            // another thread decided to cancel
            Console.WriteLine("Show canceled");
            break;
        }
    }
}

Reference post: https://stackoverflow.com/a/4783890/2710486

redpajama_set_name: RedPajamaStackExchange


text:
Hancockia (botanica) – genere di piante della famiglia Orchidaceae
Hancockia (zoologia) – genere di molluschi nudibranchi della famiglia Hancockiidae

redpajama_set_name: RedPajamaWikipedia


Every so often the worst will happen and your computer fails in such a way that only reinstalling Windows will solve the problem. Hard drives don't last for ever, so you can be sure that eventually you'll face a catastrophic crash. To guard against the worst effects of this, you need a backup. FBackup is an application designed to help you backup your personal files and protect them. These can be saved on a hard drive or on your local network.


text:
EUnewsBelgium
What's cooking? An 8 days recap.
Posted By: editor June 3, 2019
It's been a week since little Belgium woke up to a new political reality. An explosion of analyses, opinions, forecasts and suggestions have been spilled all over the media. Let's refresh and make a recap of strategic and less strategic moves.
Federal formation: mission impossible, Tom Cruise not found yet.
King Philip might have sunken a bit more into his throne as soon as he started to hear the results come in. But with fresh enthusiasm he took up his task next day. He started inviting all party leaders, even Tom van Grieken (Vlaams Belang). Much to the disgust and despair of French speaking Belgium.
As expected NV-A brought the idea of confederalism to the table. In an excellent column journalist Wouter Verschelden points out that although party leader Bart De Wever didn't win the elections, his analysis did. De Wever has been arguing that Belgium is "hardly more than the sum of two different countries". Pointing out the difference in style, media, interests etc. makes governing on a federal level to be nearly impossible. Concluding that the system is the cause of the malfunctioning. From that perspective the Gordian knot to form a new federal coalition is only more proof that Belgium Inc. doesn't work. The morning after the elections De Wever, never too shy to throw in a one-liner, joked: "The king will need Dafalgans, those of one gram, the heavy ones."
Meanwhile Elio Di Rupo (PS) openly advocated the idea of forming a coalition with CD&V, Open-Vld, sp.a & Groen ignoring NV-A even as this would mean that the Flemish still wouldn't have a majority in parliament in such coalition. This added to further frustration and mistrust between both biggest parties of the country. With Jan Jambon (NV-A) stating this would be "a negation of the will of the people". Adding that this is clearly another sign of the French speaking socialists 'unworldliness'. Needless to say that after a mere three days it already appeared that the formation of the federal government found itself in a deadlock.
Even though Thursday was officially a holiday, it did not our king from making an official first move by appointing Johan Vandelanotte en Didier Reynders as 'formateurs'. Both eminent politicians have been in and around Belgian politics for decades but have set aside further ambitions on that level. Vandelanotte bid farewell to national politics after losing his position as mayor of Ostend. Reynders on the other hand is hoping to be in pole-position for a top function in the next EU Commission.
That way their personal ambitions shouldn't hinder the public good too much, so the wisdom goes. Vlaams Belang was quick to point out that they don't reflect the voter's choice of preference. Yet most observers see it as a strategic move to improve talks between the different parties on both sides of the language border. With Vandelanotte having good relations with PS and Reynders having worked together, relatively well, with NV-A in the past years.
Formateurs are sent into the political minefield to defuse as many tensions as possible in order to enhance coalition talks in a next stage by the 'formateur'. Interesting enough the previous record breaking round of formation talks in 2010-11 gave birth to all kinds of concepts for the appointed experts to defuse the situation: political explorers, a royal helpers, 'mine-defusers', mediators… We can only start imagining which royal creativity there is in store for us the coming months.
Be the first to comment on "What's cooking? An 8 days recap."
European election, Belgian results: same same but different
King Phillip invites Vlaams Belang to Royal Palace
Wallonia: loss for PS but still biggest party
Vlaams Belang big winner of elections. Now what?
EP post-Brexit: the End of Centre-Left Majority
Source: EUelectionsPoland
Source: EUelections Italy
Poland loses interest in EU
What kind of Geopolitical Commission?
EPP in Crisis
2 Commissioners missing

redpajama_set_name: RedPajamaCommonCrawl


Explore our wealth of career resources to help you take charge of your career now.
Get professional career advice and guidance to help you build your career, your way. Learn more about how we can help you with your career change, exploring your options and in helping you to find your next executive job.
Are you ready to commit to making a career change?
Do you need help in exploring your career options?
Do you need help in your executive job search?
Whether you're looking for executive coaching, mentoring or want access to online resources to support your staff, we can help.
Do you want virtual career development tools at your fingertips?
Are you looking for executive coaching and mentoring for your top talent?
Do you want to offer exceptional career support to your alumni?
Here at Position Ignition we offer personal and professional careers advice to career conscious professionals. We help people to take control of their career development and career choices. Whether you're looking to change careers, find a new job or develop your skills and move up in your career, we can help.


text:
Williams to test Robert Kubica and Paul di Resta's 2018 potential
Oct 03, 2017 Oct 03, 2017
Williams to test Robert Kubica and Paul di Resta's 2018 potential
The Williams team will test Robert Kubica at Silverstone before moving to the Hungaroring to evaluate the Pole, and Paul di Resta, for a 2018 drive
by admin Oct 03, 2017 Oct 03, 2017
Kubica gets another chance to impress
News has emerged today that Williams are set to give Robert Kubica two opportunities to show them what he is capable of before they make the final decision on their 2018 driver lineup.
The Pole will test for one day in Silverstone after the Japanese Grand Prix, before moving to a two-day test at the Hungaroring, where current reserve driver Paul di Resta will also drive on one of the days.
This not only suggests that Williams want to get an idea of Kubica's performance, but by lining him up against di Resta, they are also giving the Scot his chance to show that he would be the better choice.
Question marks still remain
The choice of circuits is very telling for Williams, as it is a circuit both drivers have driven on recently (Kubica when he tested for Renault and di Resta when he deputised for Felipe Massa at this year's grand prix), so the team are obviously keen to give them as level a playing field as possible to show what they can do.
It is also a circuit that keeps the drivers busy in the cockpit, with very few straights separating the track's 14 corners. The variety of corners will no doubt have been another consideration when choosing to run here; the circuit features a mix of long, sweeping corners, quick changes of direction, and tight hairpins, which will test Kubica's range of motion to its limits.
This has been the main concern surrounding a potential comeback for the Pole. Following his rally accident that originally ended his F1 career, he almost lost his right arm and although he has made miraculous progress with its motion, there were worries that he wouldn't be able to operate the car properly, especially in the tight confines of an F1 cockpit.
Kubica showed in the Hungary test that he is more than capable of driving the car, but by now pairing him with one of their current drivers over two days Williams are likely to have the clearest picture yet of just how competitive he might be.
End of the line for Massa?
This would appear to signal the end of the road for Felipe Massa, but that might not necessarily be the case. Williams are essentially on a data gathering exercise during these tests, and the one driver in contention for 2018 who they already have plenty of data on is the popular Brazilian.
That definitely doesn't mean he won't be feeling the pressure though, and will head into Japan knowing that he is fighting for his F1 career. Earlier in the season he was dominating his rookie teammate, but recently those tables have turned and Lance Stroll has now finished ahead of Massa in the last three races. Undoubtedly some of this is down to Felipe's mentoring role, not to mention a myriad of private tests conducted by the Strolls, but either way, Massa needs to pick up his game if he is to stay with the team.
He has said previously that he only wants to remain with the team if they want him to stay i.e. if he is not just the only option available as happened at the end of last season. It appears that now would be that time to really make them want him.
Who do you think will drive for Williams next year? Let us know in the comments below!
Next: Japanese Grand Prix 2017: The RealSport Preview »« Previous: Japanese Grand Prix 2017: 5 drivers who need a good race
F1 2018 Monaco Grand Prix: Weekend Awards
RealSport F1 Reviews: Williams (2017)
F1 2018 Team Preview: Williams
F1 2018: Williams next up to launch with their FW-41


Hey readers, we welcome to you to our website and you can freely check everything on this page where below you can find Cannonball singer ___ Michele crossword clue answers and solutions. The idea behind it is very simple based on trivia app. You are given 4 pictures and you have to guess the common words to solve the puzzle. We highly recommend you to get all the answers and solutions of Crosswords Daily Clues and we also have solutions of Word Whizzle Answers 2017.
Already solved Cannonball singer ___ Michele? Click here to go back to the main post and find other answers Daily Pop Crosswords February 12 2019 Answers.
Have you ever wonder why you love to play Crosswords Daily Clues game because it is certainly worth it. We have made sure you get every single solution and answer whenever you need on daily basis. But still if you require more answers then check out ++PR1++, ++PR2++, ++NX1++ and ++NX2++ and try using them to know more about games then keep visiting our website.


Is there one microphone that will work for everything?
The short answer is no, that's why we make different types of microphones!
With that said, providing you pick a microphone that doesn't have an obvious tonal character, you can usually match its characteristics to a recording to a useful degree by how you position it. For example, cardioid mics all exhibit a bass boost when used close up due to something called "the proximity effect", so if your mic sounds too bright (lacking bass) with a particular recording, try getting it closer to the source as this will warm up the sound.
Cardioid mics also have their best high end response on axis so you can reduce the amount of high end by twisting the mic around slightly so that the signal is directed slightly into the side of the mic rather than directly into the front. Placing a thin, vertical physical obstruction right in front of the mic, such as a plastic pen, also tames the high end slightly and can even help reduce sibilance.
When you need to achieve a brighter effect, you can use a broad EQ boost at 10 to 12kHz to add what engineers call 'gloss' or 'sheen' to the sound, but be careful with EQ, if you add too much it will sound harsh or shrill.
The real answer is that different microphones have different tonal characteristics, so the best way to achieve the perfect sound is to try out the recording with a range of different microphones and then pick the one that suits best. If you are running a home studio to produce your own music, then you can pick whatever mic works best for you, but in a professional facility, it helps to have a range of different microphones available.


I am like, many, many others in this country, really all over the world to be more precise!
I tried all sorts of diets and slimming aids. The doctor even wrote out prescriptions for me, sometimes they worked sometimes they didn't. As soon as I stopped the diets the weight continued to rise. So I'd start to diet again, each time I stopped I would weigh more than I did before.
In 2010 I became a mother for the first time. My weight did not go up as much during pregnancy, however afterwards it did!! So, in October 2010, I signed up for grete roede (a type of diet) courses. It went so well. I continued doing this for over a year because I managed to lose weight. My weight had decreased by 40kg! I was both proud and happy. I was overweight yes, but I felt so good!
However it was not long before the kilos began to creep back on. I became pregnant again in 2014 and had my second child in June 2015. Once again I struggled with increasing weight, poor self-esteem, etc.
After much thought, I decided to have weight loss surgery. The cost of the surgery would be covered by the state, but I simply could not wait much longer. I decided to pay for the surgery myself and have private care.
I read the information on the internet and got in touch with Katrine. It would prove to be my way to a new and better life! A few weeks later I decided to have the operation. So, on 2nd January 2017, I went with a girlfriend to Riga, for gastric bypass surgery.
So, to the rest of you out there who like me have tried everything over the years, please contact overvekts-operasjoner.no, and ask them every question you have. I recommend going to Riga, good people who take good care of you from start to finish :).


text:
Esanatoglia est une commune italienne de la province de Macerata dans la région des Marches.

Géographie
la commune d'Esanatoglia se trouve dans la vallée située entre le Mont Gemmo et le Mont Corsegno, dans l'arrière-pays des Marches, entouré par les communes de Matelica, de Fiuminata et de Fabriano, à environ 450 m d'altitude.

Sur son territoire naît le fleuve Esino, précisément du Monte Cafaggio.

Entre le centre-ville et les sources de la rivière Esino se trouve le Parc des Veines, importante destination touristique.

Histoire
Selon la légende, Esus, le dieu celte de la guerre, serait à l'origine du nom de la rivière Esino, sur les rives de laquelle il est censé habiter une communauté qui à l'époque romaine était appelée Aesa.

Des preuves d'activités humaines remontant à la période paléolithique ont été découvertes en surface dans la localité de Monte Sant'Angelo, au Néolithique dans la localité de Piani di Calisti et à l'Eneolitico dans la localité de Crocifisso-Case Popolari.

Le toponyme actuel, Esanatoglia, est né en 1862 de la combinaison de l'Aesa et de l'Anatolie, en remplacement du nom de Santa Anatolia (martyr du  après J.-C.), par lequel il était appelé le Castrum Médiéval.

Le premier document connu concernant sainte Anatolie remonte à 1015, à propos de la fondation du monastère de Sant'Angelo infra hostia par le comte Atto et son épouse Berta. Le monastère devint bientôt le plus important établissement religieux de la région.

La ville fut gouvernée par la famille des Malcavalca jusqu'en 1211, année où les Ottons de Matelica se succédèrent. Trois ans plus tard, et pendant trois siècles, la puissante famille de Varano di Camerino gouverna la ville.

Sous les Varano, la ville de Santa Anatolia conserve une certaine autonomie : la première collection de normes statutaires date de 1324. La citadelle resta immunisée contre les guerres et les pillages pendant longtemps ; ce n'est qu'en 1443 qu'elle fut conquise par Francesco Ier Sforza, aidé par les habitants de Matelica : le monastère de Sant'Angelo - avec sa prestigieuse bibliothèque - ne fut pas sauvé de la dévastation.

En 1502, le Castrum entre dans les États pontificaux.

Démographie
La commune comptait 2147 habitants en 2011

Administration
Luigi Nazzareno Bartocci est Maire Centre Droit de la Commune

Hameaux

Communes limitrophes
Fabriano, Fiuminata, Matelica

Notes et références

Commune dans la province de Macerata
Localité adhérant à l'association I Borghi più belli d'Italia