Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs

We present an O∗(1.0836n)-time algorithm for finding a maximum independent set in an n-vertex graph with degree bounded by 3, which improves all previous running time bounds for this problem. Our approach has the following two features. Without increasing the number of reduction/branching rules to get an improved time bound, we first successfully extract the essence from the previously known reduction rules such as domination, which can be used to get simple algorithms. More formally, we introduce a procedure for computing “confining sets”, which unifies several known reducible subgraphs and covers new reducible subgraphs. Second we identify those instances that generate the worst recurrence among all recurrences of our branching rules as “bottleneck instances” and prove that bottleneck instances cannot appear consecutively after each branching operation.