Description

1. In the country of Pipelistan there are several oil wells, several oil refineries and many distribution hubs all connected by oil pipelines. To visualise Pipelistan’s oil infrastructure, just imagine a undirected graph with k source vertices (the oil wells), m sinks (refineries) and n vertices which are distribution hubs linking (unidirectional) pipelines incoming to this vertex with the outgoing pipelines from that vertex. You are given the graph and the capacity C(i,j) of each pipeline joining a vertex i with vertex j. You want to instal the smallest 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. 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.
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 vertices u and v are in the same side of the cut.
4. Given an undirected graph with vertices numbered [1,2,…,n], partition the vertices 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.
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 with spies as vertices and communication channels as edges looks like).
(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 listening 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 encrypted, 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.
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 − 2) 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.
9. Several families are coming to a birthday celebration in 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. 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.