CSE 101 Class NotesBacktrackingMay 12, 2004Backtracking is a generic method that can be applied to many problems.Finding a backtracking algorithm can often be a first step towards finding agreedy or dynamic-programming algorithm.However, backtracking does not usually result in optimal algorithms or dra-matic running-time improvements over the naive approach. Furthermore, exacttime analysis can be difficult, since it is difficult to exactly determine the rangeof the search.Examples of backtracking include depth-first search, branch-and-bound, andother similar approaches that perform a search by exhaustive case analysis.Example: Maximal Independent SetGiven a graph with nodes representing people, and edges representing enmities,find the largest set of people having no mutual animosity, i.e. the largest set ofunconnected nodes.Greedy approachWhile some people remain, choose the person with the fewest enemies.1 S <- { all nodes of G }2 P <- { }3 while S not empty4 s <- node in S with smallest degree5 add(P, s)6 S <- S - s - adj(s)This is fast (O(n log n)). However, it doesn’t always find the be best solution,because it is possible to back oneself into an algorithmic corner by making achoice that prevents you from making better choices later.Exhaustive searchMake up a list of every possible subset of people, and choose the largest compat-ible subset. This will find the solution, but requires exponential time (O(2n)).1Backtracking approachThis exhaustive approach is wasteful, though: by choosing one person, we elim-inate all of its neighbors at once – i.e. 2|adj(s)|rows of the exhaustive truthtable can be handled equivalently. The backtracking approach systematizesthis process of exhaustive, sequential choice as a tree of decisions.More precisely, let G = (V, E) be an undirected graph. We want to finda set I ⊂ V such that if (u, v) ∈ E, then either u /∈ I or v /∈ I. Call thisI a maximal independent set for G (note that I may not be unique). Thebacktracking approach finds I with the following algorithm:1 MIS(G = (V, E))2 if V = NIL3 return NIL4 if |V| = 15 return V6 for x in V7 S_in <- union(MIS(G - x - adj(x)), x)8 S_out <- MIS(G - x)9 return largest(S_in, S_out)This takes T (n) ≤ 2T (n −1) + O(1), since each of the two recursive calls hassize at most n − 1. We can’t apply the master theorem (why? ), but by notingthat in the worst-case the call tree forms a complete binary tree of depth n, MISis O(2n).While this is not better than the exhaustive approach above, a more carefulimplementation can yield a win by handling a special case: if x has degree 0,then it should always be included in I, so we can skip the recursive call on line 8.So the recurrence becomes T (n) ≤ T (n −1) + T (n −2) + O(1) (hm... Fibonaccistrikes again), i.e. T (n) = O(Fn) = O1+√52n≈ O(20.7n). We can provethe magic number by guess-and-check, guessing that T (n) is exponential in n:T (n) = ωn= T (n −1) + T (n − 2) = ωn−1+ ωn−2=⇒ ω2− ω − 1 = 0=⇒ ω =1 +√52Aside: DES ChallengeTo get some idea how much of an improvement 20.7nis over 2n, the DES chal-lenge cracked a 56-bit key by exhaustive search over 256 using 1000 computersand 3 months. At this rate, breaking an 80-bit key takes 280 steps (56/0.7), or16 million times more resources. You might as well just set your computers onfire. In the other direction, 240 (56 ∗0.7) would take only a few hours.2In other words, those constants in the exponent matter! Can we find otherheuristics to improve the constant? The current worst-case graph is a straightline of linked nodes. In this case, we really only need to consider either the evenor the odd elements in the “list”.Generalizing this idea, if x has only a single neighbor y in G, then we canreturn the MIS for G −{x}, which must be of the same size as union(MIS(G -x - y ), x). This reduces the running time to O(20.6n). However, we don’thave an instance of a graph exhibiting this worst-case behavior, so we might beable to do