Parameterized algorithms and kernels for almost induced matching.

The Almost Induced Matching problem asks whether we can delete at most k vertices from the input graph such that each vertex in the remaining graph has a degree exactly one. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. We give a 7 k -vertex kernel and an O ⁎ (1.7485 k) -time and polynomial-space algorithm, both of which are the best-known results. The linear-vertex kernel is obtained by using an extended crown decomposition and careful analysis, and the parameterized algorithm is based on a branch-and-search paradigm. [ABSTRACT FROM AUTHOR]