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.
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
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)
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.
Problem 3
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.
• 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.
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.
2
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′.
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.
3
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.
4