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.
Solutions: Note that the readings have to provide an accurate estimate of the
total flow from all oil wells to all refineries for every flow, not just the maximal
flow. This is ensured by constructing a flow network as a directed graph where
the oil wells, oil refineries and hubs are the vertices of the graph and each
pipeline is represented by TWO directed edges of opposite orientation and each
of capacity equal to 1. The oil wells will play the role of multiple sources and
the refineries will play the role of multiple sinks. Thus, we add a super source
S and a super sink T and connect S with all the wells with edges of infinite
capacity and similarly all the refineries with T . We now run the Edmons-Karp
algorithm to find the maximal flow through such a network (note that we have
ignored the actual capacities of the edges). After the algorithm has converged,
we construct the last residual network flow and look at all the vertices to which
there is a path from the source S. This will define a minimal cut, so we look
at all the edges crossing such a minimal cut. The number of such edges (in
the forward direction only) determines the minimal number of meters needed
to accurately compute the total flow from S to T .
1
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.
Solution: We again make a corresponding network flow with the source at
vertex 1 and the sink at vertex n and two directed edges replacing each undi-
rected edge. The problem is now equivalent to minimising the number of edges
between the two subsets; since all the edges appear in pairs of edges with the
same end points but opposite direction, whenever there is an edge from the
sink side to the source side, there will also be an edge in the opposite direction
which min cut will take in the account.
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.
Solution: Connect the source s with vertex u with an edge of infinite capacity
and similarly connect vertex v with the sink t with an edge also of infinite
capacity. Use the Edmons-Karp algorithm to find the maximal flow through
such a network and then the corresponding minimal cut. Clearly the two added
edges of infinite capacity cannot belong to the min cut which ensures that u
stays at the same side as s and v at the same side as t.
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.
Solution: Connect vertex u with vertex v and also vertex v with vertex u,
both with directed edges of infinite capacity. Note that if we add only an edge
of infinite capacity from u to v, v can still end up on the source side and u
on the sink side and so the edge of infinite capacity will not belong to the cut
because it is from the sink side to the source side. To prevent this we need
edges between u and v in both directions.
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
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).
2
(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.
(a) Solution: This is just a max flow/min cut problem, in a flow network
with an edge from a spy i to a spy j just in case there is a communication link
from i to j, with a unit capacity. We find a maximal flow in such a network
and the corresponding min cut. The edges that have to be compromised are
those that cross the min cut.
(b) Solution: This is again a max flow/min cut problem, with a unit ver-
tex capacity and infinite capacity of all edges. Such problems are solved as
explained in the lectures, by splitting each vertex other than the source and
the sink into two vertices, one incident to all incoming edges and one incident
to all outgoing edges with these two vertices connected by an edge of capacity
equal to the capacity of that vertex, in this problem the unit capacity.
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.
Solution: We first construct a corresponding flow network with the cities as
vertices and with city 1 as the source and city N as the sink. If there are k
roads between two cities i and j but none of the roads is a major road, we
connect i and j with two directed edges in opposite directions and of capacity
each equal to k. If one of the roads is a major road the capacity of the two
directed edges is set to M + 1. We now find max flow in such a network; if it is
3
at most M then the problem has a solution and roads that need to be blocked
are those that cross the corresponding min cut. If the flow is more than M
then at least one edge of capacity M + 1 has been crossed, which indicates
that every cut is crossed by a major road which cannot be blocked and thus
we cannot catch the criminal and we must output -1.
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.
Solution: This is very similar to a problem with blue and red vertices from
the lecture slides. We add a super source vertex and a super sink vertex. Super
source is connected to all of m internal chosen vertices and the super sink to
all of m side vertices. Each edge of the grid is replaced with two directed
edges in opposite directions, all at unit capacity. Finally, every internal vertex
is assigned capacity of 1. We now find max flow in such a network using the
vertex splitting method described on the lecture slides. All edges occupied with
a flow form the connecting paths and if the flow is equal to m the problem has
a solution.
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
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
4
security system is reactivated, determine whether all M criminals can escape
without triggering the alarm.
Solution: Producing the flow graph: First replace all the edges with two
directed edges in opposite directions, thus making the graph directed and set
the weights of all edges to 1. Either first assign capacity 1 to all vertices, or
directly replace each vertex v with two vertices, v1 and v2; all edges which were
incoming to vertex v will be now made incoming to vertex v1 and all the edges
outgoing from vertex v will be made outgoing from vertex v2. Finally, connect
vertex v1 with vertex v2 with an edge going from v1 to v2 also of capacity 1.
Having done that for all vertices, add a supper source and connect it to the M
internal vertices (where the robbers are) with edges of unit capacity as well;
also add a super sink and connect all the side vertices to the super sink with
edges of capacity 1 as well. Now find max flow in such a network; the problem
has a solution if the flow is exactly equal to M . Note that our construction
insures that every vertex and every edge can belong to only one path, so such
paths will be disjoint, sharing neither edges not vertices.
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”.
Solution: This is a typical max flow problem. Make a bipartite graph with
vertices on the left side representing families and vertices on the right side
representing tables. Introduce a super source and a super sink and connect
each family with the super source by a directed edge of capacity equal to the
number of family members. Connect each table with the super sink with a
directed edge of capacity equal to the number of seats at that table. Further,
connect each family vertex with all the tables compatible with the dietary
5
preference of that family using directed edges of capacity 1 (to ensure that no
table contains more than one family member from the same family. Now just
use max flow algorithm and look at occupied edges to determine placement of
guests.
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
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)
Hint: First apply the Floyd Warshall algorithm to the weighted graph with
cities as its vertices and edges representing roads, with each edge having a
weight equal to the time t(i, j) needed to traverse it. In this way we find the
shortest distance from every node to any other node and determine which of
these distances are less than X. Construct a bipartite graph; on the left there
will be N nodes li, one for each city ci representing population of city ci; on
the right there will be N nodes rj, again one for each city cj, but this time
representing the set of pods available in city cj.
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.
6
Solution This problem can be viewed as a network flow problem in disguise.
We begin by adjusting the count of the number of white squares in each row
and column based on the location of the known (white) squares. The sum of
the count in all rows must equal the sum of the count in all columns. Let this
sum be X so we can infer that there are precisely X white squares among the
squares of unknown colour. A common approach to such problems on a grid is
to consider the bipartite graph where every row is a vertex on the left side of
the graph and every column is a vertex on the right side, making 2N vertices
in total. Every square in the grid which is of unknown colour forms a directed
edge from its corresponding row to its corresponding column. We convert this
graph into a flow network as follows. Each edge has capacity of 1. We add
a source s and sink t to this graph. We add a directed edge from s to each
row with capacity equal to the adjusted number of white squares in that row.
Similarly, we add a directed edge from each column to t with capacity equal
to the adjusted number of white squares in that column. It is evident that
the saturated edges of the bipartite graph in any integer valued flow from the
source to the sink describes a possible colouring of the grid. Any such flow
has capacity at most X so a painting exists if and only if the maximum flow is
equal to X.
7