CS 124 Homework 7: Spring 2023
Your name: Collaborators:
No. of late days used on previous psets:
No. of late days used after including this pset:
Homework is due Wednesday April 26 at 11:59pm ET. You are allowed up to twelve (college)/forty (extension school), but the number of late days you take on each assignment must be a nonnegative integer at most two (college)/four (extension school).
Try to make your answers as clear and concise as possible; style may count in your grades. Assign- ments must be submitted in pdf format on Gradescope. If you do assignments by hand, you will need to scan your papers to turn them in.
You may not write anything that you will submit within one hour of collaborating with other students, language models, the internet, etc., or using notes from such sources. That is, whatever you submit must first have been in your head alone, or notes produced by you alone, for an hour. Subject to that, you can collaborate with other students, e.g. in brainstorming and thinking through approaches to problem-solving.
For all homework problems where you are asked to give an algorithm, you must prove the correctness of your algorithm and establish the best upper bound that you can give for the running time. Generally better running times will get better credit; generally exponential-time algorithms (unless specifically asked for) will receive no or little credit. You should always write a clear informal description of your algorithm in English. You may also write pseudocode if you feel your informal explanation requires more precision and detail, but keep in mind pseudocode does NOT substitute for an explanation. Answers that consist solely of pseudocode will receive little or no credit. Again, try to make your answers clear and concise.
NP-c approximations NP-c heuristics Linear programming Network flows
1. Let G = (V,E) be a graph. A vertex cover of G is a set C ⊆ V such that all edges in E have at least one endpoint in C. That is, each edge is adjacent to at least one vertex in the vertex cover. The (Minimum) Vertex Cover problem is, given a graph G and a number K, to determine if G has a vertex cover of size at most K. The lecture 18 notes have a proof that Minimum Vertex Cover is NP-complete.
(a) (5 points) Recall that all NP-complete problems reduce to each other and thus are computationally equivalent in that a polynomial time algorithm for one implies a poly- nomial time algorithm for all. In this problem we will notice that this equivalence does not extend to approximations.
Consider the Independent Set problem and the Vertex Cover problem, whose definitions are recalled here. Given a graph G = (V, E), a set S ⊆ V is an independent set if there are no edges within S. The goal of the Indpendent Set problem is to output a largest independent set in an input graph. A set C ⊆ V is a vertex cover if every edge has at least one endpoint in C. The goal of the vertex cover problem is to output a smallest vertex cover in an input graph G.
These two problems are clearly equivalent. Given an algorithm A that outputs a min- imum vertex cover one every input graph G, the algorithm that outputs V \ A(G) on input G, solves the maximum independent set problem. Below you will prove that this equivalence does not extend to approximations and indeed a 2-approximation to vertex cover does not yield a c-approximation to Independent Set for any constant c.
For every constant c > 1, show that there exists a graph and a 2-approximation of its Minimum Vertex Cover such that the corresponding independent set is not within a factor of c of the Maximum Independent Set. TaketheexamplegraphG=(V,E)suchthatV ={u,v,w,x},E={(u,v),(v,w),(w,x)}. The the true minimum set cover Ctrue of size 2 contains vertices v,w. The size of the corresponding independent set of a vertex cover is given by |V \C|. The 2-approximation algorithm might first consider edges (u, v) and (w, x), in which case the approximation algorithm yields a minimum set cover Capprox of size 4, which is within a factor of 2 of thetruesize. Thenα=|V \Capprox|=0. Then∀c>1,c·α=c·0=0̸=|V \Ctrue|= 4 − 2 = 2.
Thus from this example, for every constant c > 1, there exists a graph and a 2- approximation of its Minimum Vertex Cover such that the corresponding independent set of size 0 is not within a factor of c of the Maximum Independent Set.
(b) (20 points) Prove that if there exists a polynomial time algorithm for approximating the size of the maximum independent set in a graph G to within a factor of 2, then for every ε > 0, there is a polynomial time algorithm for approximating the size of the maximum independent set in a graph to within a factor of (1 + ε). The degree of the polynomial may depend on ε. (Hint: for a starting graph G = (V,E), consider the graph G×G = (V′,E′), where the vertex set V′ of G×G is the set of ordered pairs V′ =V ×V,and{(u,v),(w,x)}∈E′ ifandonlyif
{u,w}∈E or {v,x}∈E.
If G has an independent set of size k, then how large an independent set does G′ have? If you have an α approximation to the independent set size in G′ what kind of approxi- mation to the independent set size in G do you get?)
The overall plan is to construct a sequence of graphs G0, G1, G2, · · · , Gk with Gi+1 = Gi × Gi and G0 = G. Letting α(Gi) denote the size of the largest independent set in Gi, we will show that α(Gi) = α(Gi−1)2 = α(G)2i, Thus if nk is a 2-approximation to
α(Gi), then n1/2k will be a 21/2k -approximation to α(G0). Picking k = O(log(1/ε)) will k
ensure that this is a 1 + ε-approximation to α(G0) as desired.
We start by proving that α(Gi) = α(Gi−1)2. To prove α(Gi) ≥ α(Gi−1)2, let I be an independent set of size α(Gi−1) in Gi−1. We note that I × I is an independent set in Gi. Toseethissuppose(u,v),(w,x)∈I×I. ThenbydefinitionofG×G,(u,w)isnotanedge
of Gi−1 (since either u = w or u,w are both in I) and also (v,x) is not an edge of Gi−1. We thus conclude I × I is an independent set in Gi and this has size |I| · |I| = α(Gi−1)2. Next we prove α(Gi) ≤ α(Gi−1)2. To do so let J be a maximum independent set in Gi. Let J1 = {(a|∃b such that (a,b) ∈ J} and J2 = {(b|∃a such that (a,b) ∈ J}. Note J1 and J2 are subsets of vertices of Gi−1 and furthermore, by the definition of edges in Gi J1 and J2 are both independent sets in Gi−1, and so have sizes |J1|, |J2| ≤ α(Gi−1). We also have J ⊆ J1 × J2 and so |J| ≤ |J1| · |J2|. Putting the above together we thus have
α(Gi) = |J| ≤ |J1| · |J2| ≤ α(Gi−1)2.
We thus conclude α(Gi) = α(Gi−1)2. Thus by induction we we get α(Gi) = α(G0)2i . Now let A be a 2-approximation algorithm for indedependent set size. Our new algorithm B for approximating independent sets is the following: Let k = O(log(1/ε)). Let nk =
A(Gk). Output n1/2k. k
We claim this is a polynomial time algorithm. This is so, since A runs in time O(Nc) for some constant c on graphs with N vertices. So B runs in time O((n2k )c + n2k+1 ) — it takes time at most O(n2k+1) to create the graph Gk and then O((n2k)c) time to run A on this graph. This is still a polynomial in n for every fixed ε > 0.
It remains to show this is a 1 + ε-approximation algorithm. Let a = α(G0) be the size of
the maximum independent set in G0. Then α(Gk) = a2k . Since nk is a 2-approximation,
we have a2k/2 ≤ nk ≤ a2k. Thus our output b = n1/2k satisfies a2k/2 ≤ b2k ≤ a2k. k
Taking 1/2kth roots we get a/21/2k ≤ b ≤ a, or output b is a 21/2k approximation to α(G0). Thus it suffices to verify that 21/2k ≤ 1 + ε, or equivalently (1 + ε)2k ≥ 2, to finish the proof and we do so below.
Wehave(1+ε)2k ≥1+2kε≥2provided2k ≥1/εwhichholdsfork≥log2(1/ε).
2. Consider the problem MAX-k-CUT, which is like the MAX CUT problem, except that we partition the vertices into k disjoint sets, and we want to maximize the number of edges between sets.
(a) (10 points) Give a deterministic algorithm that finds a partition within a factor of 1− k1 of optimal.
(b) (5 points) Give a randomized algorithm that’s a generalization of the randomized algorithm for MAX CUT from class that finds a partition that, in expectation, is within a factor of 1 − k1 of optimal.
(a) Our algorithm for approximating Max k-CUT is as follows: Start with an arbitrary partition of the vertices, say S1 = V and S2 = · · · = Sk = ∅. While there exists a vertex v and sets Si and Sj such v is currently in Si and moving it to Sj increases the size of the cut, switch v. Stop and output (S1, . . . , Sk) when no such cut exists.
Time complexity
We assume the graph is given in the adjanceny list representation. Further we maintain an array A[..] where A[v] ∈ {1, . . . , k} indicates which set v belongs to (currently). We now analyze the run time of our algorith with this representation.
Since at best we can have all edges cross a set, we make at most |E| switches, since we only make a switch if it increases the number of edges in the cut, and the cut size starts at 0 and reaches at most |E|. Checking whether there exists a switchable vertex requires us to enumerate all the vertices and for each vertex we need to find out how many neighbors are in each of the k sets. This takes time O(kdv) for a vertex v with dv neighbors for a total of O(k|E|) steps summing over all v. Thus, since we do this at most O(|E|) times, this overall takes at most O(k|E|2) time.
(The run time can be improved slightly to O(k|E||V |) by maintaining for each vertex k arrays counting the number of neighbors in set Si, and updating these number in O(k|V |) time when switching. If we do this each iteration takes only O(k|V |) time to find a vertex that is switchable (takes O(k) time vertex to be considered) and switching and updating (takes O(kdv) = O(k|V |) time if the vertex v being switched has degree dv ).)
Correctness
At the end of the algorithm let i(v) ∈ {1..k} denote the set that vertex v is in. For every
vertex v and index j ̸= i(v) we have that v has at least as many neighbors in Sj as it
does in Si(v) (or else we would have switched v from set Si(v) to Sj to increase the k-cut
value). We conclude that for every vertex v, at least k−1 of its edges must be to vertices k
in other sets.
Thus for every vertex, at least k−1 of its edges must go to another set, and since
k−1 = 1 − 1 , this ensures that at least (1 − 1 )|E| are included in the cut (since for kkk
all vertices at least 1 − k1 of their edges are in the cut, thus there must be at least this proportion of the total edges in the cut, since all edges are connected to some vertex in the graph), thus we find a partition within a factor of 1 − k1 as required.
(b) We initialize k empty sets. Then for each vertex v ∈ G, we randomly assign the vertex to one of the k sets.
Correctness
Consider any edge (u, v) ∈ E. Our algorithm assigns u, v each to one of k random sets, thus the probability that both these vertices are in the same set is (k1) (assign u to a random set, then v has a k1 chance of being put in the same set). Thus the probability that this edge is between two sets is simply 1 − k1 , since k1 is the probability that both vertices of an edge are in the same set (i.e. the edge is within one set).
Since this is true for any edge, this algorithm finds a partition that is, in expectation, within a factor of 1 − k1 of the optimal where at most all edges cross between two sets. This is clear since, for the optimal solution, at most all |E| edges are included in the cut (and therefore the probability that an edge crosses a set is at most 1), while with our algorithm, an edge crosses a set with probability 1 − k1 , thus in expectation our algorithm finds a cut of size |E|(1− k1) and thus we are within a factor of 1− k1 of the optimal. Polytime:
This is within polynomial time since it takes O(k) time to generate the sets, then we assign each vertex to one set, which can be done in constant time for each vertex (as- suming we can randomly generate a number between [1,k] in constant time, perhaps more reasonable to assume doable in O(k) time but either way it’s within polynomial
time), thus this takes O(n) time. Thus overall this algorithm requires O(n + k) time which is polynomial time on the length of the input.
3. Patients who require a kidney transplant but do not have a compatible donor can enter a kidney exchange. Usually, the demand for kidneys is far greater than the supply (in the US in 2010, more than 90,000 people were on the wait-list for a transplant, but only 15,000 kidneys were available). Thus, we must decide whom to allocate the kidneys to.
The kidney donation problem has as input a compatibility graph G(V, E), where each patient- donor pair is a vertex, and there is a directed edge e = (u, v) ∈ E if the donor in u can donate to the patient in v. We wish to maximize the number of transplants.
(a) (10 points) Give a (polynomial-time) reduction from the kidney donation problem to an integer linear program. (For this problem, donors are willing to donate a kidney regardless of whether their patient gets a kidney.)
(b) (5 points) Suppose that each donor is only willing to donate a kidney if their corre- sponding patient gets a kidney (so donations form a set of cycles in the graph). Give a (polynomial-time) reduction from this restricted kidney donation problem to an integer linear program.
(c) (15 points) Algorithmic matches are not guaranteed to work in practice (due to, e.g., tissue-type incompatibility). Therefore, for each edge e, there is an associated probabil- ity fe that the donation fails. If any of the donations in a cycle fails, the whole cycle fails and no transplants occur. To minimize the issue (and the logistical difficulty of having many transplants occurring at the same time and place), a hospital has decided to cap the length of kidney-donation cycles at 4. Again, each donor is only willing to donate a kidney if their corresponding patient gets a kidney. We wish to maximize the expected number of transplants that succeed. Give a (polynomial-time) reduction from this restricted kidney donation problem to an integer linear program.
(Hint: It may be helpful to calculate the set C = C1, C2, . . . of cycles in G of length at most 4. How big can the set C be?)
Consider the following algorithm R to convert a kidney donation problem to an integer linear program:
• Let the number of vertices in G be n. Then we construct n2 variables, xji , i, j ∈ [n]
• If ∃(i, j) ∈ E or if i = j then we construct the clause xji ≥ 0, else we construct the clause
xji = 0. (enforce donations to only occur between valid donor-patient pairs)
• Construct the clauses xj1 + xj2 + … + xjn ≤ 1 ∀j. (a patient never receives from more than one donor)
• Construct the clauses x1i + x2i + … + xni ≤ 1 ∀i. (a donor never donates to more than one patient)
• Then we aim to find max(Pi,j xji ).
Polytime: Constructing all the variables takes O(n2) time since we create a variable for every possible pair of vertices (u,v), of which there are O(n2) . We make one constraint for each variable to ensure that the variable is non-negative or enforce it to be zero (in case there is no edge from i, j, we should never be able to use this variable as 1), which again takes O(n2) time. Then for each vertex we create two clauses to ensure that there is only at most one incoming and one outgoing edge. Each vertex can have edges to at most the O(n) other vertices, thus each clause has O(n) variables, thus constructing these clauses for all O(n) variables takes time O(n2). Finally, we construct the objective function with all O(n2) variables we created, also in O(n2) time. Thus every step is within O(n2) time, thus this algorithm is polynomial as required.
Completeness
Claim:Let KD(G) denote the maximum number of kidney donations possible for our input G and let ILP(R(G)) denote the maximum value of our ILP on R(G). Then KD(G) = I LP (R(G)).
Let k = KD(G). This means that there exist a set S of k edges in G such that no two of these edges have the same starting point or the same endpoint (else a patient would be donated more than 1 kidney, or a donor would have to donate multiple kidneys). Then if we set xji = 1 if (i,j) ∈ S and xji = 0 otherwise then we have that Pi,j xji = k and all constraints of our ILP are satisfied (details below):
• xji ≥0∀i,jsinceweonlysetouredgesto1or0.
• xj1 +xj2 +…+xjn ≤ 1 ∀j since the set of edges we took can only have one donation to a recipient, it must be true that this sum is less than or equal to one since we only set variables to 1 if the corresponding edge was in the set used in G, and only one of these edges can be used as otherwise a recipient would have more than one donor.
• x1i + x2i + … + xni ≤ 1 ∀i since again the set of edges we took can only have one recipient per donor, it must be true that this sum is less than or equal to one since we only set variables to 1 if the corresponding edge was in the set used in G, and only one of these edges can be used as otherwise a donor would have more than one recipient.
Thus this assignment proves ILP(R(G)) ≤ k = KD(G).
In the converse direction, suppose ILP(R(G)) = k and let xji be a feasible integer solution to R(G) achieving Pi,j xji = k. We first claim that for every (i, j), xji ∈ {0, 1}. To see this,fixapairi,jandnotethatsincexji′ ≥0foreveryi′ ̸=iandPi′xji′ ≤1,weget xji ≤ 1 − Pi′̸=i xji′ ≤ 1 and so xji ∈ [0,1] and {0,1} are all the integers in this set. Now let
S be the set of all edges (i,j) such that xji = 1. The constraints enforce that no two edges in S have the same starting point or the same endpoint, and the objective function implies that this set has exactly k elements. So S is a valid solution to the kidney donation problem with k exchanges, thus showing ILP(R(G)) ≥ KD(G). This proves the claim and thus the correctness of our reduction.
(b) We take the ILP from the previous part and add the constraint
∀u, X xuv ≤ X xt,u. vs.t.(u,v)∈E ts.t.(t,u)∈E
(The left hand side describes the number of kidneys u donates, and the right side describes the number of kidneys that u receives. This captures the condition that at u only donates when they receive a kidney. ) It can be verified that this is still a polynomial time reduction and correctness is as before – every valid solution to the modified kidney donation problem is a valid solution to the ILP and vice versa.
Let C be the set of cycles of length at most 4 in the graph. Notice that there are at most |V |k k-cycles, so the size of C is O |V |4. For each cycle c ∈ C, create a variable xc. Then,
consider the ILP
(Above we use the notation u ∈ c to indicate that c is a vertex in the cycle c.) Since a valid set of transplants corresponds to choosing some cycles of length at most 4, every kidney donation plan can be converted to a solution to the ILP by setting xc = 1 for every cycle of transplants that occurs. This assignment will satisfy the constraint above since every donor-receiver pair (denoted by a vertex u only participates in one cycle). Conversely we can turn a solution {xc} into a transplant, by simply performing all transplants in cycles c fow which xc = 1. Notice that we only allow a vertex to participate in one cycle (by the constraint above). Then, since each vertex in a cycle receives an donates one kidney, all patients are happy. Finally, since each cycle c contributes |c| Qe∈c (1 − fe) transplants, the objective function captures the expected number of transplants.
While the expression for the objective function might not look linear, notice that |c| Qe∈c (1 − fe) is a constant for each cycle c so we can compute all of them in polynomial time. And the resulting objective function is linear in the variables xc which is what we care about. Since we make a polynomial number of variables and constraints, the reduction takes polynomial time.
4. In the Weighted Vertex Cover problem the input is a graph G = (V, E) with positive integer weights w = {w(u)|u ∈ V } on the vertices of G. The goal is to output a vertex cover of minimum total weight given the graph G and weights w. I.e., the output should be a vertex cover C and among all vertex covers it should output a cover of minimum total weight.
(a) (5 points) For every c > 1, give an example of a weighted graph G with weights w such that the 2-approximation algorith from the lecture of the (unweighted) Vertex Cover problem on G does not output a c-approximation to the weighted Vertex cover on G and w.
Let c ∈ N, where c > 1.
max|c|xc ·Y(1−fe) s.t.
∀u, X xc ≤ 1.
Code Help
Construct a weighted graph G = (V, E), where V = {u, v}, E = {(u, v)}, w(u) = c, w(v) = 1.
Correctness:
Since we have only one edge (u, v), the 2-approximation algorithm will output C = {u, v} with a total weight of c + 1.
The optimal weighted vertex cover for this graph is C′ = {v}, with a total weight of 1. Approximation Ratio = (weight of C) / (weight of C’) = c+1 > c.
Here, the 2-approximation algorithm for the unweighted Vertex Cover problem does not output a c-approximation for the weighted Vertex Cover problem for this specific graph and weights. This method allows us to construct a counterexample works for any c > 1.
(b) (10 points) Give a reduction from the weighted Vertex Cover problem to an Integer Program. I.e., describe an algorithm that take G and w as input and outputs an integer program whose value is exactly the minimum vertex cover size in G and w. (While your solution need not do this, for the next part it would be useful if your output integer program has a variable for every vertex in the graph along with a constraint for every edge that captures the requirement that at least one endpoint of the vertex is in the cover.)
To reduce the weighted Vertex Cover problem to an Integer Program, we can construct an integer program using binary variables and constraints that represent the vertices and edges of the input graph G = (V, E) with weights w.
Define a binary variable xu for each vertex u ∈ V , where xu = 1 if and only if the vertex u is in the vertex cover. Our goal is to minimize the total weight of the vertex cover. The integer program can be formulated as follows:
Minimize Objective Function: P(u∈V ) w(u) ∗ xu Constraints:
∀(u,v)∈E: xu+xv≥1
∀u∈V: xu ≥0,xu ≤1
Correctness: We claim that the optimum to the ILP above equals the weight of a minimum vertex cover. Suppose C ⊆ V is a minimum weight vertex cover, then the assignment xu = 1 if u ∈ C and xu = 0 otherwise satisfies all the constraints — we certainly have 0 ≤ xu ≤ 1 for every u, and the fact that every edge is covered implies that if (u, v) ∈ E then at least one of xu or xv is 1 and so xu + xv ≥ 1. Finally the value of the objective function for this solution is Pu∈C w(u) which equals the weight of the cover C. We thus get that the ILP has a solution of value equal to the weight of the minumum vertex cover. So the minimum value of the ILP objective is thus at most the value of the minmum vertex cover.
In the other direction, consider a solution to the ILP achieving the minimum value and let C = {u|xu ≥ 1}, We claim C is a cover: To see this suppose (u,v) is an edge and supposed u ̸∈ C (if u ∈ C we are done for this edge anyway); Then xu = 0 and so the constraint xu + xv ≥ 1 implies xv ≥ 1 implying v ∈ C. Thus each edge is covered and so C is a cover. The weight of the cover is Pu|xu≥1 w(u) ≤ Pu w(u)xu. We conclude that G has a vertex cover of weight at most the minimum value of the ILP and so the minimum vertex cover has value at most the minimum of the ILP.
Programming Help
Putting the two directions together we have a proof that the ILP is correct.
(c) (10 points) Give a deterministic polynomial time 2-approximation to the Weighted Vertex Cover problem. (Hint: You may use the fact that LPs are solvable in polynomial time to solve the LP relaxation of the integer program from Part (b). You should then show how to round the LP solution to an integer solution that only loses factor of 2.) Our approximation algorithm solves the LP relaxation of the ILP from the previous part, and if x∗ is an optimal solution to the LP, outputs the set C = {u|x∗u ≥ 1/2}. The ILP formulation took polynomial time to construct, solving the LP takes some more polynomial time, and then outputting C takes O(|V |) time, so the overall algorithm takes polynomial time.
To show correctness we need to show that the set output is always a cover and has value at most twice the value of the minimum vertex cover. To see that C is a cover we repeat the argument from part (b) with a minor modification: Suppose (u,v) is an edge with u̸∈C. Thenx∗u <1/2andsox∗v ≥1−x∗u ≥1/2andsov∈C. Thuseveryedgeis covered by C and so C is a vertex cover.
Finally we turn to the 2-approximation guarantee. Let W∗ = Pu∈V x∗uw(u) denote the LP optimum. Suppose C′ is a minimum weight vertex cover. We need to show that the weight of C is at most twice the weight of C′. We first claim that W∗ is at most the weightofC′. Toseethis(asinpart(b))weusethesolutionx′u =1ifu∈C′ and0 otherwise. As in Part (b) this is a valid solution to the (I)LP and achieves value equal to the weight of C′ and so we conclude that the LP optimum W∗ must be at most the value of this solution which equals the weight of C′. Next we claim that the weight of C is at most 2W∗. This is easily seen by the inequality chain:
X w(u) = X w(u) ≤ X 2x∗uw(u) ≤ X 2x∗uw(u) = 2W∗. u∈C {u|x∗u ≥1/2} {u|x∗u ≥1/2} u∈V
Thus we have that the weight of our cover is at most 2W∗ which is at most twice the weight of the cover C′, concluding the proof.
5. Sticking to the vertex cover theme, we now consider the Bipartite Weighted Vertex Cover Problem: Here the input graph G = (V, E) is bipartite, i.e., V = V1 ⊔ V2 where V1 and V2 are disjoint, and E ⊆ V1 × V2. As usual we have positive integer weights on vertices of V and we wish to find a vertex cover of minimum total weight.
(a) (5 points) Professor X claims to have found a reduction from Bipartite Weighted Vertex Cover to Maximum Flow, which goes as follows: Given the graph G with vertex weights w, construct a network H whose vertices are V ∪ {s, t} where s and t are two new vertices. H includes edges (s,u) with capacity w(u) for every u ∈ V1 and edges (v,t) with capacity w(v) for every v ∈ V2. Additionally it has edges (u, v) with capacity 1 for every (u, v) ∈ E. Professor X claims the max flow in the network H is the same as the weight of the minimum weighted vertex cover in G.
Give a counterexample, i.e., a weighted graph G, w such that the network H constructed by the reduction has max flow strictly less than the weight of the minimum vertex cover of G,w.
浙大学霸代写 加微信 cstutorcs
(Food for thought: Can you find a counterexample where maxflow is strictly greater than the min vertex cover?)
We consider the graph G = (V,E), with vertex sets V1 = u and V2 = v and weights w(u) = 2 and w(v) = 3. The edge set E contains one edge (u,v). The network H produced the reduction of Professor X to G is the following:
Vertices: V ∪s,t=u,v,s,t Edges with capacities:
(s, u) with capacity 2
(v, t) with capacity 3
(u, v) with capacity 1
The maximum flow in network H is 1, which can be achieved by sending 1 unit of flow fromstou,andthenfromutov,andfinallyfromvtot. (NotethatthecutS={s,u} and T = {v, t} has a capacity of 1 proving that the max flow in this network is at most 1.)
However, the weight of the minimum vertex cover of G,w is 2, which can be achieved by selecting vertex u. The vertex cover weight does not match the maximum flow value, and this counterexample shows that Professor X’s reduction is incorrect.
(Food for thought response: This cover value is higher than the flow value, and the reduction in the next part explains why this will always be the case.)
(b) (20 points) Correct the reduction above so as to make it correct. Prove the correctness of your reduction, i.e., that the Maximum Flow in H really equals the Minimum Vertex Cover in G, w. (Hint: There is a very small change that will make the reductions correct. And to prove correctness you may find duality and Max Flow = Minimum Cut theorem useful.)
Solution: Modify Professor X’s reduction as follows: instead of having capacities of 1 for the edges (u,v) ∈ E, set their capacities to ∞. The new network H is constructed as follows:
Vertices: V ∪s,t=u,v,s,t
Edges with capacities:
(s, u) with capacity w(u) (u, v) with capacity ∞ (v, t) with capacity w(v)
All of this can be done in O(n + m) time. Proof of Correctness:
We show that the minimum cut value in the network H equals the weight of the minimum vertex cover in G, w. The correctness then follows by the max-flow min-cut theorem. We first note that there is a natural 1-1 correspondence between subsets of vertices of V ands-tcutsinHasfollows.GivenC⊆V,letφ(C)=(S,T)whereS={s}∪(V1\ C)∪(V2 ∩C) and T is the rest of the vertices of H. Note that S,T is an s-t cut of H (since s ∈ S and t ∈ T and the two sets partition the vertices of H). Note further that φ is inverted by the function φ−1(S,T) = (S ∩V2)∪(T ∩V1), i.e., for every C ⊆ V φ−1(φ(C)) = C and furthermore φ is onto with respect to s-t cuts in H.
We now claim that for every s-t cut (S,T) in H, the capacity of the cut is finite if and only if C := φ−1(S,T) is a vertex cover of G. To see this consider a vertex cover C in G and let (S,T) = φ(C). For every edge (u,v) ∈ V1 ×V2 we must have u ∈ C or v ∈ C. Iftheformerthenwehaveu̸∈Sandifthelatterwehavet∈S. Soineithercasethe edge (u,v) does not cross from S to T. We conclude none of the infinite capacity edges cross from S to T. (Note we may have edges going from T to S but this does not count towards the capacity of the cut (S, T ).) To see the converse, suppose S, T is a cut with finite capacity. Again we have that if (u,v) is an edge then either u ̸∈ S or v ̸∈ T. By thedefinitionofφ−1 wehaveifu̸∈Sthenu∈C:=φ−1(S,T)andsimilarlyifv̸∈T then v ∈ C. This proves the claim in the first sentence of the paragraph.
Finally we note one more fact bef