Algorithms Tutorial 5
Solutions
1. In the country of Pipelistan there are several oil wells, several oil refineries and
many distribution hubs connected by oil pipelines. To visualise Pipelistan’s
oil infrastructure, just imagine a directed graph with k source vertices (the oil
wells), m sinks (refineries) and n vertices which are distribution hubs linked
with one way pipelines. You are given the graph and the capacity C(i, j) of
each pipeline going from a vertex i to a vertex j. You want to instal the small-
est possible number of flow meters on some of these pipelines so that the total
throughput of oil from all the wells to all refineries can be computed exactly
from the readings of all of these meters. Each meter shows the direction of
the flow and the quantity of flow per minute. Design an efficient algorithm for
deciding on which pipelines to place the flow meters.
2. Given an undirected graph with vertices numbered 1, 2, . . . , n, partition the ver-
tices into two disjoint subsets such that vertex 1 and n are in different subsets,
and the number of edges with both ends in the same subset is maximised.
3. Assume that you are given a network flow graph with a source s, a sink t
and two other distinct vertices u and v. Design an algorithm which returns a
smallest capacity cut among all cuts for which the vertex u is in the same side
of the cut as the source s and vertex v is in the same side as the sink t and
which runs in polynomial time.
4. Assume that you are given a network flow graph with a source s, a sink t
and two other distinct vertices u and v. Design an algorithm which returns a
smallest capacity cut among all cuts for which vertices u and v are in the same
side of the cut.
5. You know that n + 2 spies S, s1, s2, . . . , sn and T are communicating through
certain number of communication channels; in fact, for each i and each j you
1
know if there is a channel through which spy si can send a secret message to
spy sj or if there is no such a channel (i.e., you know what the graph looks like,
with spies as vertices and communication channels as directed edges).
(a) Your task is to design an algorithm which finds the fewest number of
channels which you need to compromise (for example, by placing a listen-
ing device on that channel) so that spy S cannot send a message to spy
T through a sequence of intermediary spies without the message being
passed through at least one compromised channel.
(b) Assume now that you cannot compromise channels because they are en-
crypted, so the only thing you can do is bribe some of the spies. Design
an algorithm which finds the smallest number of spies which you need to
bribe so that S cannot send a message to T without the message going
through at least one of the bribed spies as an intermediary.
6. There are N cities (labelled 1, 2, . . . , N), connected by M bidirectional roads.
Each road connects two different cities. A pair of cities may be connected by
multiple roads. A well known criminal is currently in city 1 and wishes to get
to city N via road. To catch the criminal, the police have decided to block the
minimum number of roads possible to make it impossible to get from city 1 to
city N. However, some roads are major roads. In order to avoid disruption, the
police cannot close any major roads. Find the minimum number of roads to
block to prevent the criminal from going from city 1 to city N, or output -1 if
the police cannot stop the criminal.
7. An n×n grid is an undirected graph consisting of n rows, each row containing n
vertices, with vertices connected with edges to all of their immediate neighbours
(2 at all of the 4 corners, 3 at all of the 4 sides and 4 in the interior of the grid).
Vertices with exactly 4 neighbours are called the internal vertices; vertices with
exactly 3 neighbours are called the side vertices. The escape problem is, given
m ≤ 4(n − 1) many internal vertices in the grid and m side vertices on the 4
sides of the grid, connect each of m many distinct internal vertices with distinct
m side vertices by non intersecting paths or return impossible when there is no
such a solution. Note that any of m internal vertices can be connected to any
of m side vertices.
8. A band of M criminals has infiltrated a secure building, which is structured as
an N × N square grid of rooms, each of which has a door on all of its sides.
Thus: from an internal room, we can move to any of the four neighbouring
2
rooms, from a room on the side of the building, we can move to three other
rooms or leave the building, and from a corner room, we can move to two
other rooms or leave the building. The criminals were able to shut down the
building’s security system before entering, but during their nefarious activities,
the security system became operational again, so they decided to abort the
mission and attempt to escape. The building has a sensor in each room, which
becomes active when an intruder is detected, but only triggers the alarm if it
is activated again. Thus, the criminals may be able to escape if they can all
reach the outside of the building without any two of them passing through a
same room. Given the M different rooms which the criminals occupy when the
security system is reactivated, determine whether all M criminals can escape
without triggering the alarm.
9. Several families are coming to a birthday celebration at a restaurant. You have
arranged that v many tables will serve only vegetarian dishes, p many tables
will not serve pork and r many remaining tables will serve food with pork. You
know that V many families are all vegetarians, P1 many families do not eat pork
but do not mind eating vegetarian dishes, P2 many families do not eat pork
but hate vegetarian dishes. Also R1 many families have no dietary restrictions
and would also not mind eating vegetarian dishes or food without pork, R2
many families have no dietary restrictions but hate vegetarian dishes but can
eat food without pork. Finally, S many families are from Serbia and cannot
imagine not eating pork. You are also given the number of family members in
each family and the number of seats at each table. Your conundrum is to place
the guests at the tables so that their food preferences are respected and no two
members from the same family sit at the same table. In case the problem has
no solutions your algorithm should output statement “no solution”.
10. Today was just a regular day for everyone in Krypton until a news flashed that
a meteor is going to destroy Krypton in X days. Krypton has N cities, some
of which are connected by bidirectional roads. You are given a road map of
Krypton; for every two cities Ci and Cj which are connected by a (direct) road
from Ci straight to Cj you are given the value t(i, j) which is the number of
days to travel from city Ci to city Cj. (You can of course also go from a city Cm
to city Ck without a direct road from Cm to Ck by going through a sequence
of intermediate cities connected by direct roads.) In each city Ci the Krypton
Government built qi pods to carry inhabitants in case of any calamity, which
will transport them to Earth. City Ci has population pi. As soon as the people
hear this news they try to save themselves by acquiring these pods either at
3
their own city or in other city before the meteor destroys everything. Note
that a pod can carry only one person. Find the largest number of invaders the
Earth will have to deal with. (20 pts)
11. You have been told of the wonder and beauty of a very famous painting. It
is painted in the hypermodern style, and so it is simply an N by N grid of
squares, with each square coloured either black or white. You have never seen
this picture for yourself, but have been told some details of it by a friend. Your
friend has told you the value of N and the number of white squares in each
row and each column. Additionally, your friend has also been kind enough to
tell you the specific colour of some squares: some squares are black, some are
white, and the rest she simply could not remember. The more details she tells
you, the more amazing this painting becomes but you begin to wonder that
perhaps it’s simply too good to be true. Thus, you wish to design a polynomial
time algorithm that determines whether or not such a painting can exist.
4