A Bisection Approach to Subcubic Maximum Induced Matching

In this paper, we present a faster exact algorithm which solves the Maximum Induced Matching problem for subcubic graphs. Here let n be the overall number of vertices and k be the number of those vertices of degree 3 where all neighbours have also at least degree 2. Then the runtime is at most \(O(1.2335^k) \cdot Poly(n)\) , giving an FPT bound for the time used by the algorithm; the algorithm uses the result of Monien and Preis combined with a bound obtained by applying the measure and conquer technique where the number k replaces n as the measure used; note that \(k \le n\) .