Path Contraction Faster than $2^n$

A graph $G$ is contractible to a graph $H$ if there is a set $X\subseteq E(G)$, such that $G\mathrm{/}X$ is isomorphic to $H$. Here, $G\mathrm{/}X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs $\mathcal{F}$, the $\mathcal{F}$-$\text{textsc}Contraction$ problem takes as input a graph $G$ on $n$ vertices, and the objective is to output the largest integer $t$, such that $G$ is contractible to a graph $H\in \mathcal{F}$, where $\mathrm{\mid }V(H)\mathrm{\mid }=t$. When $\mathcal{F}$ is the family of paths, then the corresponding $\mathcal{F}$-$\text{textsc}Contraction$ problem is called $\text{textsc}PathContraction$. The problem $\text{textsc}PathContraction$ admits a simple algorithm running in time $2^n\cdot n^{\mathcal{O}(1)}$. In spite of the deceptive simplicity of the problem, beating the $2^n\cdot n^{\mathcal{O}(1)}$ bound for $\text{textsc}PathContraction$ seems quite challenging. In this paper, we design an exact exponential time algorithm for $\text{textsc}PathContraction$ that runs in time ${1.99987}^n\cdot n^{\mathcal{O}(1)}$. We also define a problem called \textsc{$3$-Disjoint Connected Subgraphs}, and design an algorithm for it that runs in time ${1.88}^n\cdot n^{\mathcal{O}(1)}$. The above algorithm is used as a sub-routine in our algorithm for {\sc Path Contraction}