CSOR-W4231 Homework 5 Solution

Homework Instructions.
1. For all algorithms that you are asked to “give” or “design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Argue correctness, even if you don’t give an entirely formal proof.
• Give the best upper bound that you can for the running time.
2. If you give a reduction, you should do so as we did in class, that is
(a) Give the inputs to the two problems.
(b) Describe in English the reduction transformation and argue that it requires polynomial time. (You do not need to give pseudocode but you’re encouraged to do so.)
(c) Prove carefully equivalence of the original and the reduced instances.
3. You should submit your assignment as a pdf file on Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
4. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your handwriting is very clear and that your scan is high-quality.
Homework Problems
A circulation with demands is a function f : E → R+ that satisfies
(a) capacity constraints: for each e ∈ E, 0 ≤ f(e) ≤ ce.
(b) demand constraints: For each v ∈ V , fin(v) − fout(v) = dv.
We are now concerned with a decision problem rather than a maximization one: is there a circulation f with demands that meets both capacity and demand conditions?
i. (10 points) Derive a necessary condition for a feasible circulation with demands to exist.
ii. (30 points) Reduce the problem of finding a feasible circulation with demands to max ffow.
2. (45 points) In this problem, the input is a standard flow network G = (V,E,s,t,c) with integer edge capacities.
(a) (25 points) An edge in a flow network is called critical if decreasing the capacity of this edge results in a decrease in the value of the maximum flow.
On input a flow network G = (V,E,s,t,c), you ran Ford-Fulkerson and computed a maximum flow f.
i. Give an efficient algorithm that finds a critical edge in G.
ii. Give an efficient algorithm that finds every critical edge in G.
(b) (20 points) Suppose we have already found the maximum s-t flow in G. However, we made a mistake in the capacity value of edge (u,v): we used cuv but the capacity is only cuv − 1. Moreover, the max flow f uses edge (u,v) at full capacity. Can you find a new optimal flow faster than by recomputing max flow in G?
3. (35 points) In the MAX SAT problem, the input is a SAT formula φ with m clauses over n variables and the output is a truth assignment that maximizes the number of satisfied clauses.
Here is a simple randomized algorithm that returns a truth assignment for the n variables. for each variable do set its truth value to either 0 or 1 by flipping a coin
end for
(a) (12 points) Give the expected number of clauses satisfied by the above algorithm in terms of m,n,kj. Then lower bound this expectation in terms of m and n only.
(b) (23 points) Next, suppose we de-randomize the above algorithm as follows: instead of flipping a coin to assign a truth value to each variable, we assign to the variable the truth value that satisfies the most as-yet-unsatisfied clauses.
Give a lower bound for the number of clauses satisfied by this deterministic algorithm.
4. (20 points) On the hardness of MAX SAT.
(a) (5 points) Formulate the decision version of MAX SAT (see Problem 3 above).
(b) (13 points) Prove that MAX SAT(D) is NP-complete.
(c) (2 points) Is the algorithm in Problem 1 an efficient algorithm? If your answer is yes, does this contradict what you proved in part b) of this problem? Explain your answer.
RECOMMENDED exercises: do NOT return, they will not be graded.)
1. Run the Ford-Fulkerson algorithm on the following network, with edge capacities as shown, to compute the max s-t flow. At every step, draw the residual graph and the augmenting paths. Report the maximum flow along with a minimum cut.

2. There are many variations on the maximum flow problem. For the following two natural generalizations, show how to solve the more general problem by reducing it to the original max-flow problem (thereby showing that these problems also admit efficient solutions).
• There are multiple sources and multiple sinks, and we wish to maximize the flow between all sources and sinks.
• Both the edges and the vertices (except for s and t) have capacities. The flow into and out of a vertex cannot exceed the capacity of the vertex.
3. You are asked to assist in the following crisis event.
Give an efficient algorithm for this problem.
4. (Using reductions to prove NP-completeness)
(a) A clique in an undirected graph G = (V,E) is a subset S of vertices such that all possible edges between the vertices in S appear in E. Computing the maximum clique in a network (or the number of cliques of at least a certain size) is useful in analyzing social networks, where cliques corresponds to groups of people who all know each other.
State the decision version of the above maximization problem and show that it is NPcomplete. Hint: reduction from Independent Set.
(b) We say that G is a subgraph of H if, by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of the vertices, identical to G.
The following problem has applications, e.g., in pattern discovery in databases and in analyzing the structure of social networks.
Subgraph Isomorphism: Given two undirected graphs G and H, determine whether G is a subgraph of H and if so, return the corresponding mapping of vertices in G to vertices in H.
Show that Subgraph Isomorphism is NP-complete.
(c) Similarly, consider the following problem.
Dense Subgraph: Given a graph G and two integers a and b, find a set of a vertices of G such that there are at least b edges between them.
Show that Dense Subgraph is NP-complete.
5. Suppose you are given n cities and a set of non-negative distances dij between pairs of cities.
(a) Give an O(n22n) dynamic programming algorithm to solve this instance of TSP; that is, compute the cost of the optimal tour and output the actual optimal tour.
(b) What are the space requirements of your algorithm?
Hint: Let V = {1,...,n} be the set of cities. Consider progressively larger subsets of cities; for every subset S of cities including city 1 and at least one other city, compute the shortest path that starts at city 1, visits all cities in S and ends up in city j, for every j ∈ S.