The Branch & Bound algorithm as we saw it in the lecture uses linear programming as a relaxation to solve integer linear programs. Actually, the arguments behind the algorithm would work in different settings where the "relaxation" is not in form of a linear program. To keep the notation simple, we want to consider a slight variant of the TSP problem, which is called TSP PATH. For the TSP PATH problem, the input is an undirected graph G = (V, E) (which does not need to be a complete graph with non-negative edge cost c: E rightarrow R greaterthanorequalto 0. The goal is to compute a path P E that visits each node exactly once (we allow any pair from V as end points. Note that this problem is NP-complete. We want to design a variant of the Branch & Bound algorithm to solve it. For a subset of edges E' CE, let MST(E') be the minimum spanning tree in the subgraph (V, E'). Recall that MST (E') can be computed in polynomial time using Kruskal's algorithm. For a set of edges C E, we denote c(C) = sigma_e elementof c c^e as the sum of its cost. The algorithm for TSP PATH is now as follows: Set C* as being undefined. Initialize a stack with {E} WHILE stack is non-empty DO Take and remove an item (= an edge set) from the stack and call it E' If the graph (V, E') is not connected, goto (3) Compute T:= MST (E') IF T is a path and c(T)