The maximum independent set problem is one of the most important
problems in worst-case analysis for exact algorithms.
Improvement on this problem in low-degree graphs can be used to get
improvement on the problem in general graphs.
In this paper, we show that the maximum independent set problem in an
$n$-vertex graph with degree bounded by $4$ can be solved in $O^*(1.1376
^n)$ time and polynomial space, improving all previous exact algorithms
for this problem.
As most fast exact algorithms, this algorithm is a branch-and-search
algorithm and analyzed by using the measure and conquer method. To
effectively analyze the running time bound, we use the idea of `shift'
to save some decreasing on the measure from some good branches to some
bad branches. After treating cycles of length 3 and 4 in the graph, we
check carefully what will happen after branching on a degree-4 vertex
(without any local structure), and then we can get the claimed
improvement.