16.3. Better Branching Rules

All algorithms in the previous section were obtained using fairly elementary branching rules based on fairly elementary analyses. In this section, we show that a more careful analysis of the graph structure allows us to obtain algorithms with running time \(O^*(1.47^n)\) for computing a minimum vertex cover or maximum independent set and with running time \(O^*\bigl(1.62^k\bigr)\) for computing a minimum vertex cover. We also discuss how to use similar ideas to obtain a solution for the \(k\)-SAT problem that takes \(o^*(2^n)\) time.