Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3

In this paper we propose an O(n1.0892)O(1.0892n) algorithm solving the Maximum Independent Set problem for graphs with maximum degree 3 improving the previously best upper bound of O(n1.0977)O(1.0977n). A useful secondary effect of the proposed algorithm is that being applied to 2k   kernel, it improves the upper bound on the parameterized complexity of the Vertex Cover problem for graphs with maximum degree 3 (VC-3). In particular, the new upper bound for the VC-3 problem is O(k1.1864+n)O(1.1864k+n), improving the previously best upper bound of O(k2∗k1.194+n)O(k2∗1.194k+n). The presented results have a methodological interest because, to the best of our knowledge, this is the first time when a new parameterized upper bound is obtained through design and analysis of an exact exponential algorithm.