COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 10 School of Computer Science
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Extensions of flow networks
(a) What is flow networks with node supplies and demands?
(b) What is a circulation in a network with supplies and demands?
(c) How can one use flow networks to model supply and demand? 2. Reduction.
(a) What is a polynomial time reduction? (b) Is polynomial time reductions transitive?
(c) What is a reduction by simple equivalence?
3. Polynomial-time equivalence of search, optimization and decision problems
(a) What are the search, optimization and decision versions of maximum bipartite matching?
(b) What are the reductions to prove Decision ≤P Optimization ≤P Search?
(c) What are the reductions to prove Search ≤P Optimization ≤P Decision?
(d) What are the search, optimization and decision versions of other problems we have seen in the class?
Tutorial
Problem 1
In the circulation with demands problem, we are given a directed graph G = (V, E), edge capacities c(e) and demands d(v) for each vertex v, where the demands d(v) can be positive, zero, or negative. A circulation is a function f on edges that satisfies:
• 0 ≤ f(e) ≤ c(e) (capacity constraints)
• f (e) − f (e) = d(v) (conservation constraints)
e intov e outofv
The goal is to determine if a circulation exists.
In the circulation with demand and lower bounds problem, we are also given lower bounds l(e) on edges
and a circulation has to satisfy f(e) ≥ l(e) in addition to the above constraints.
Give a reduction from the circulation with demand and lower bounds problem to the circulation with
demands problem.
1
Solution: (Sketch.) Consider an initial circulation f0 where f0(e) = l(e) for each edge e. If this satisfies the conservation constraints, then we are done. Otherwise, we need to adjust f0 as follows. Let d′(v) = d(v) − (e into v f0(e) − e out of v f0(e)), this is the additional amount of flow that needs to go into v to satisfy its conservation constraint. Now, construct a circulation with demands instance on the same graph, edges capacities c′(e) = c(e) − l(e) and demands d′(v). We now argue that there exists a circulation for the original problem if and only if there exists a circulation for the new problem.
( =⇒ ) Suppose that there exists a circulation f for the original problem. Define a circulation f′ for the new problem by f′(e) = f(e) − f0(e). Then, f′ satisfies the capacity constraints since the capacity constraints on f are that f(e) ≤ c(e). Using the definition of d′(v) and the fact that f satisfies its conservation constraints, we also have
f′(e)− f′(e)= f(e)− f(e)− f0(e)− f0(e)
e into v e out of v e into v e out of v e into v e out of v
=d(v)− f0(e)− f0(e) e into v e out of v
= d′(v),
so it satisfies the conservation constraints as well.
( ⇐= ) Suppose that there exists a circulation f′ for the new problem. Define a circulation f for the original problem by f(e) = f′(e) + l(e). Then, f satisfies the capacity constraints since the capacity constraints on f′ are that f′(e) ≤ c(e)−l(e). Note that f(e) ≥ l(e) since f′(e) ≥ 0 so the lower bound constraints are still satisfied. Consider a vertex v. Using the definition of d′(v) and the fact that f′ satisfies its conservation constraints, we also have
f(e)− f(e)= f′(e)− f′(e)+ f0(e)− f0(e) e into v e out of v e into v e out of v e into v e out of v
=d(v)− f0(e)− f0(e) + f0(e)− f0(e)
e into v e out of v e into v e out of v
= d(v),
so it satisfies the conservation constraints as well.
Problem 2
Suppose you’re in charge of managing a fleet of airplanes and you’d like to create a flight schedule for them. Here’s a very simple model for this. Your market research has identified a set of m particular flight segments that that would be very lucrative if you could serve them; flight segment j is specified by four parameters: its origin airport, its destination airport, its departure time, and its arrival time. An example of six flights segments you’d like to serve with your planes over the course of a single day may include:
1. Brisbane (depart 6 am) – Sydney (arrive 7 am)
2. Sydney (depart 6:30 am) – Melbourne (arrive 8 am) 3. Sydney (depart 8 am) – Cairns (arrive 11 am)
4. Melbourne (depart 12 am) – Adelaide (arrive 2 pm) 5. Townsville (depart 2:15 pm) – Brisbane (arrive 4 pm)
2
6. Adelaide (depart 4:00 pm) – Perth (arrive 7 pm)
It is possible to use a single plane for a flight segment i, and then later for flight segment j, provided that:
1. the destination of i is the same as the origin of j and there’s enough time to perform maintenance on the plane in between; or
2. you can add a flight segment in between that gets the plane from the destination of i to the origin of j with adequate time in between.
For the example above you can group flights 1, 3, and 5 together by allocating an hour maintaince between each flight and adding an additional 1 hour flight between Cairns and Townsville for example.
Your goal based on the two conditions stated above is to determine if it is possible to service all m flights using at most k planes. In order to do this you will need to reuse planes as efficiently as possible.
Solution: Put capacity on source
The solution is based on the following idea. Units of flow will correspond to airplanes. We will have an edge for each flight, and upper and lower capacity bounds of 1 on these edges to require that exactly one unit of flow crosses this edge. In other words, each flight must be served by one of the places. If (ui, vi) is the edge representing flight i, and (uj , vj ) is the edge representing flight j, and flight j is reachable from flight i, then we will have an edge from vi to ui with capacity 1.
For the example above we get the following s − t capacitated network where it is possible to achieve a flow of 2. Although we use max flow this problem is a minimisation problem in the sense that the aim is to find the minimum max flow for the following graph where all the edges that are solid are 1.
BNE 6 SYD 7 SYD 8
CNS 11
TSV 2:15 BNE 2:15
st
Problem 3
SYD 6:30
MEL 8 MEL 2 ADL 2 ADL 4 PER 7
We have seen dynamic programming algorithms for several sequence problems.
• In the Longest Common Subsequence (LCS) problem, we are given two sequences A and B and want
to find the longest sequence S that is a subsequence to both A and B.
• In the Longest Increasing Subsequence (LIS) problem, we are given a sequence A of integers and want
to find the longest subsequence S whose elements appear in sorted order from lowest to highest.
3
• A palindrome is a string that reads the same left to right as right to left. In the Longest Palindrome (LP) problem, we are given a string A and we want to find the longest subsequence S that is a palindrome.
In this tutorial problem, we will show that LIS and LP are special cases of LCS. Suppose that there exists an algorithm for LCS that runs in time T(N) where N is the length of the longer of the input sequences A and B.
1. Give an algorithm for LIS that runs in T (n) + O(n log n) time, where n is the length of the input sequence A to LIS, by reducing LIS to LCS.
2. [Hard] Give an algorithm for LP that runs in T (n) + O(n) time, where n is the length of the input sequence A to LP, by reducing LP to LCS.
Solution: (Sketch.)
1. To find the LIS of an integer sequence A, let B = sort(A) and return the LCS of A and B. Any increasing subsequence of A corresponds to a common subsequence between A and B and vice versa.
2. To find the longest subsequence of A that is a palindrome, compute the LCS S of A and rev(A), where rev(A) denotes the reverse of A. If S has even length, let X and Y be the first and second halves of S so S = XY . Since S is a subsequence of rev(A), we also have that rev(S) = rev(XY ) = rev(Y ) rev(X) is a subsequence of A. Now, either all of X appears in A before all of rev(X) or all of rev(Y ) appears before all of Y . In the former case, we return X rev(X), and in the latter, we return rev(Y )Y .
If S has odd length, let c be the middle element of S and X be the subsequence of StotheleftofcandY totherightsoS=XcY. Asbefore,rev(S)=rev(XcY)= rev(Y)crev(X) is a subsequence of A. Thus, either all of Xc appears in A before all of rev(X) or all of rev(Y)c appears before all of Y. In the former case, we return Xc rev(X), and in the latter we return rev(Y )cY .
Problem 4
Decision problems involve answering yes/no questions. For example, the independent set problem is “Given an undirected graph G and a number t, does G have an independent set of size t?”. In practice we are usually interested in solving optimization problems. For example, the maximum independent set problem is “Given an undirected graph G, find the largest in independent set in G”.
Assuming you have a polynomial time algorithm for the independent set problem, show how to solve the maximum independent set problem.
Solution: Let A be the algorithm for the decision version of the independent set problem. Let G = (V, E) be our input graph, and let t∗ be the cardinality of the largest independent set in G.
First, we find the value of t∗ using binary search and A; this takes log2 n calls to A. Having computed t∗ , we pick an arbitrary vertex u and call A on (G − u, t∗ ). If it returns “yes” then we know that there is a maximum independent set that does not use u; otherwise, if it returns “no” we know that any maximum independent set must use u. Therefore, if the answer is “yes” we can ignore u and find a maximum independent set in G − u. On the other hand, if the answer is “no” we can find a maximum independent set in G − u − N (u) and then add u to it.
Notice that we perform polynomial amount of computation plus we make a polynomial number of calls to A. Thus if A runs in polynomial time, so does our algorithm.
4
Problem 5
Recall that in the knapsack problem, we are given a set of n items with values and weights (the i-th item has value vi and weight wi), and a weight limit W.
• In the decision version of knapsack Knapsack-D, we are also given a query value q and our task is to determine if there exists a subset of items with total weight at most W and value at least q. Note that the required output is a Boolean (true/false).
• In the optimization version of knapsack Knapsack-O, our task is to compute the largest-possible value of any subset of items whose total weight is at most W. Note that the required output is a number.
• The search version Knapsack-S asks to find a subset of items whose total weight is at most W and whose value is as large as possible. Note that the required output is a subset of items.
Just as for the maximum bipartite matching problem, these versions are equivalent under polynomial-time reductions. Your task is to prove the harder direction of the equivalence.
1. Show that Knapsack-O ≤P Knapsack-D, i.e. given a black-box algorithm for Knapsack-D, construct an algorithm for Knapsack-O that uses at most a polynomial number of computational steps and a polynomial number of calls to the black-box algorithm.
2. Show that Knapsack-S ≤P Knapsack-O, i.e. given a black-box algorithm for Knapsack-O, construct an algorithm for Knapsack-S that uses at most a polynomial number of computational steps and a polynomial number of calls to the black-box algorithm.
Problem 6
Given a graph, a clique is a subset S of vertices that forms a complete subgraph (i.e. every pair of vertices u, v in S share an edge), and an independent set is a subset S of vertices such that no pair of vertices u, v in S share an edge.
• In the Clique decision problem, we are given a graph G and an integer k and our goal is to determine whether G has a clique of size at least k.
• In the Independent Set decision problem, we are given a graph G and an integer k and our goal is to determine whether G has an independent set of size at least k.
Your task is to show a simple equivalence between these problems:
1. Given a graph G = (V, E) and an integer k, construct a graph G′ and an integer k′ such that G has a
clique of size at least k if and only if G′ has an independent set of size at least k′.
2. Given a graph G = (V,E) and an integer k, construct a graph G′ and an integer k′ such that G has
an independent set of size at least k if and only if G′ has a clique of size at least k′.
Solution: The solution for this problem follows the same outline as the one for the indepen- dent set problem. Note that using binary search in part (1) in order for the reduction to be polynomial time. Doing a linear scan of all possible values will result in a pseudopolynomial time reduction.
Solution: (Sketch.) Observe that S is an independent set in G iff S is a clique in the “complement graph” G′ = (V ′, E′) where E′ = {e : e ∈/ E}, and vice versa.
5
Problem 7
Consider a generalization of the interval scheduling problem where requests are not a single interval but a collection of d intervals. The objective is to choose a maximum number of requests that do not create any conflicts. More formally, we have n requests. The ith request has associated intervals I1i , I2i , . . . , Idi . A subset Sofrequestsisfeasibleifforalli,j∈S,anda,b∈[1,d]wehaveIai ∩Ibj =∅. Theobjectiveistoselecta maximum size set of feasible requests. In the decision version of this problem, we are also given an integer k and we need to determine if there exists a set of feasible requests of size at least k. Give a polynomial-time reduction from the Independent Set problem to the decision version of this problem.
Solution: We reduce independent set to the decision version of this problem. Recall that an instance (G, k) of the independent set problem is to determine whether there is an independent set of cardinality k. Given (G,k), we label the edges e1,…,em of the graph G. Now we construct an instance of the multiple interval scheduling problem as follows: For each vertex u in G we create a request ru in our instance; if ei is incident on u we let [i, i + 1] be one of the time intervals associated with ru.
Let S be a set of vertices in G and JS the set of requests induced by those vertices. It is easy to see that S is independent if and only if JS is feasible. Therefore, (G,k) is a “yes instance”if and only if we can find a feasible schedule with k requests. Thus Independent Set≤P Interval Scheduling with multiple Intervals.
Problem 8
[Advanced] In this tutorial problem, we will show a simple equivalence between the vertex cover problem and the maximum matching problem in bipartite graphs. Let G = (V, E) be a bipartite graph with n vertices on each side, and let C be the size of the minimum vertex cover and M be the size of the maximum matching.
1. Show that C ≥ M.
2. Show that C ≤ M.
3. Conclude that on bipartite graphs, the Vertex Cover, Independent Set and Clique problems admit polynomial-time algorithms.
4. Give an example of a non-bipartite graph where the minimum vertex cover is larger than the maximum matching.
Solution: This problem was not discussed during this week’s advanced tutorials so the answer is deferred to next week.
6