In the Deletion to induced matching problem, we are given a graph $G$ on $n$ vertices, $m$ edges and a non-negative integer $k$ and asks whether there exists a set of vertices $S \subseteq V(G) $ such that $\lvert S\rvert \le k $ and the size of any connected component in $G-S$ is exactly 2. In this paper, we provide a fixed-parameter tractable (FPT) $O^*(1.748^{k})$ running time and polynomial space algorithm for the Deletion to induced matching problem using branch-and-reduce strategy and path decomposition. We also extend our work to the exact-exponential version of the problem.

Preprint Link