Time allowed:  2 hours.

Answer ONE question from Section A and TWO questions from Section B. USE SEPARATE ANSWERBOOKS for Sections A and B

Indicate clearly which three questions you have answered. Among the questions attempted, only the first one in Section A and the first two in Section B (in their order of appearance in the answer book) will be marked.

Read carefully the instructions on the answer books.

Calculators are not allowed.

Section A

Answer ONE question from this section.

1. Imagine that you are preparing for a canoeing trip going from the source of a river to the sea.  There are n villages along the river, numbered from n (at the source of the river) to 1 (on the sea).  In every village you can rent a canoe which can be returned at any other village downstream.  For every pair of villages i and j  (such that i > j , that is, such that j is downstream from i) we know the price p[i,j] of renting a canoe in village i and returning it in village j .

A schedule from n to 1 is a list of villages whose rental shops you should use on your way down the river from village n to village 1. For example, if n = 4 then (4, 3, 1) is a schedule in which you rent a canoe from village 4 to village 3, and then you rent one from village 3 to village 1.

(a)  [7 marks] Let n = 4 and consider the following array p of rental prices:   1  2  3  4

that is, assume that the cost of renting a canoe from 3 to 2 is 4, the cost of renting a canoe from 4 to 1 is 8, etc.

The total rental cost of a schedule is defined as the sum of all the individual rental prices; for example the total rental cost of the schedule (4, 3, 1), for the above array of prices, is p[4, 3] + p[3, 1] = 3 + 7 = 10.

How many schedules are there for a canoe trip from 4 to 1? List all of them and calculate their total rental costs.

What is the total rental cost of the optimal schedule—the schedule that minimises the total rental cost? Which schedule is optimal?

(b)  [5 marks] For every n ≥ 2, how many schedules are there from n to 1 as a function

of n?

(c)  [13  marks] Design a polynomial-time algorithm that—given an array p[i,j] of prices, for n ≥ i > j ≥ 1, as input—computes the total rental cost of an optimal schedule from n to 1.

(d)  [5 marks] Illustrate the behaviour of your algorithm on the example from part (a).

2. Suppose that you are consulting for a company that wants to organize an annual party for its employees. You have agreed with the management that a good party is such that both of the following two conditions hold:

❼ for each participant, there are at least two other participants whom she knows;

❼ for each participant, there are at least two other participants whom she doesn’t

know.

We assume throughout, that the acquaintance relation is symmetric, that is, any two employees either both know each other, or they both don’t know each other.

(a)  [5 marks] Consider a company with six employees:

❼ employees 1, 2, and 3 who all know each other; and

❼ employees 4, 5, and 6 who all know each other;

and nobody in the first group knows anybody in the other group (and vice versa).

Draw the (undirected) graph in which the vertices correspond to the six employees, and there is an edge between two of them if and only if they know each other.

Argue that if you invite all six employees to the party then it will be a good party.

(b)  [7 marks] Consider a company with eight employees: the six that we have con-

sidered in part (a), as well as employees 7 and 8, such that:

❼ employee 7 knows only employee 1; and

❼ the only people that employee 8 does not know are employees 6 and 7.

Explain why inviting employee 7 to a party (of any size) at this eight-person com- pany would prevent it from being a good party.

Can any party to which employee 8 is invited be a good party?

What is the size of the biggest possible good party at this company? Who should be invited to it?

(c)  [14 marks] Design a polynomial-time algorithm that—given an (undirected) graph G = (V,E) in which vertices correspond to employees, and edges join employees who know each other—computes the size of the largest possible good party, and lists the employees who should be invited to it.

You may assume that the graph is given as an adjacency lists data structure. For maximum credit, the running time of your algorithm should be linear in |V |+|E|.

(d)  [4 marks] Illustrate the behaviour of your algorithm on the example from part (b) that is, explain how your algorithm computes the list of employees who should be invited to the biggest possible good party.

Section B

4. A path in a graph is simdle if it does not visit any vertex more than once.

The HAMILTONIAN-PATH decision problem is—given an undirected graph G—to determine if there is a simple path that visits every vertex in the graph G.  It is well- known that the HAMILTONIAN-PATH problem is NP-complete, and you may assume this fact below.

For a fixed integer k, the k-SPANNING-TREE decision problem is—given an undirected graph G—to determine if there is a spanning tree of G in which every vertex has degree no larger than k .

(a)  [8 marks] Draw the graph G = (V,E) where V = {1, 2, 3, 4, 5, 6, 7, 8} and    E = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 7}, {2, 4}, {2, 7}, {3, 4}, {4, 6}, {4, 8}}.

Give a spanning tree of G in which every vertex has degree no larger than 3.     Is there a spanning tree of G in which every vertex has degree no larger than 2?

(b)  [8 marks] Prove that for every fixed integer k, the k-SPANNING-TREE decision

problem is in NP.

(c)  [9 marks] Prove that the 2-SPANNING-TREE decision problem is NP-complete.

(d)  [10 marks] Prove that the 3-SPANNING-TREE decision problem is NP-complete.

5.   (a)  [4 marks] Consider the following flow network. The numbers labelling the edges are their capacities, and s and t are the source and sink vertices.