COMPUTER SCIENCE TRIPOS Part IA – 2021 – Paper 1
Algorithms (djw1005)
Consider a directed graph in which each edge is labelled by a pair of non-negative
costs, for example a distance and a travel time.
We say that a path with costs (ca, cb) is Pareto dominated if there is another path
with the same start and end vertices and with costs (c
0
a
, c0
b
) such that c
0
a ≤ ca and
c
0
b ≤ cb and at least one of these inequalities is strict. A path is called Pareto efficient
if it is not Pareto dominated by any other path. (These concepts are named after
the economist Vilfredo Pareto.)
(a) In the graph shown here, find all Pareto efficient paths from s to t, and state
their costs. [1 mark]
(b) Show that, if v0 → v1 → · · · → vk is a Pareto efficient path from v0 to vk, then
v0 → · · · → vk−1 is a Pareto efficient path from v0 to vk−1. [3 marks]
(c) Let v0 → · · · → vk be a Pareto efficient path from v0 to vk, and let its costs
be (ca, cb). Show that there is a Pareto efficient path from v0 to vk with costs
(ca, cb) that has ≤ V − 1 edges, where V is the number of vertices in the graph.
[3 marks]
(d) We are given a start vertex s. Give an algorithm to compute all costs achievable
by Pareto efficient paths from s to every other vertex. [6 marks]
(e) Prove that your algorithm is correct. [7 marks]
[Note: The version of this question that appeared in the exam contained an error,
which has now been corrected.]