16.1. Branching Numbers and Branching Vectors

In this section, we revisit the simple algorithm for the vertex cover problem already discussed in Section 8.3 and show that essentially the same algorithm can be used also to solve the maximum independent set problem. The algorithms themselves are not particularly exciting. The main goal of this section is to introduce you to two useful tools for analyzing the running times of branching algorithms: branching numbers and branching vectors. The "normal" tool for analyzing the running times of recursive algorithms is recurrence relations, which you should have been introduced to in CSCI 3110. Branching algorithms usually give rise to recurrence relations of one particular type, and branching numbers and branching vectors allow us to obtain solutions of these recurrence relations without solving these recurrences from scratch.