A factory laid out in a large circular room contains n work stations against the walls, each of which

produces some component of a gadget. In order to increase production, the firm is exploring au$-$

tomation to move components between stations, but the transporting robots aren$$t very smart, and

can$$t avoid collisions. Therefore, they wish to select a set of roads, each connecting $2$ different sta$-$

tions that the robots can travel along, but such that none of the roads cross each other $($although

multiple roads may leave$/$enter the same station$).$

The stations are labeled $1,...,$ n by their position around the edge of the factory floor. For each

unordered pair of stations i$,$ j$,$ there is some benefit Bi$,$j $>0$ that can be derived from building a road

between stations i and j$,(1<=$ i$,$ j $<=$ n$).($One can imagine that certain stations need access to the

outputs of others$).$ Let a feasible $($non$-$intersecting$)$ set of roads be maximal if you cannot add another

road to it without ruining feasibility $($i$.$e$.,$ without causing an intersection$).$

$($a$)$ Prove that there are exponentially $($specifically$,$ e$($n$))$ maximal feasible sets of roads.

$($b$)$ Give an O$($n$3)-$time algorithm to find the feasible set of roads maximizing total benefit. You

may assume the $$word model,$$ that is$,$ arithmetic operations on the benefits take unit time.

$\backslash$