- 29 Mar, 2021
- 0 Comments
- 1 Min Read
Problem Set 6 /AN
1. [12 POINTS]
(a) (6 pts) Consider a flow network in which both edges and vertices have integer capacities.
In other words, the input is a directed graph G = (V, E) with source vertex s ∈ V and sink
vertex t ∈ V , a positive integer capacity c(e) on each edge e ∈ E, and a positive integer
capacity c
0
(v) on each vertex v ∈ V . A flow f in G is feasible if it satisfies the usual properties
of a feasible flow, and in addition, at each vertex v ∈ V − {s, t},
P
(u,v)∈E
f(u, v) ≤ c
0
(v),
i.e., the sum of the flow along incoming edges to v does not exceed c
0
(v).
Give an efficient algorithm to find a maximum flow in G with respect to both the edge
capacities and the vertex capacities by converting this problem to a standard maximum
flow problem. Be sure to argue correctness of your algorithm and bound its running time,
and make your algorithm as efficient as you can (in terms of an algorithm for the maximum
flow problem we saw in class).
(b) (6 pts) Let G = (V, E, s, t, c) be a flow network with an integer capacity c(e) on each
edge e ∈ E, and let a maximum flow f on G be given. In other words flow values along
each edge in G for this maximum flow are given to us.
Let e = (u, v) be an edge in E. Suppose we increase the capacity of e to c
0
(e) = c(e) + 1,
while leaving the capacities of the other edges unchanged. Let us use G0
to denote this flow
network, which is G with capacity of edge e increased to c
0
(e). Give a linear time algorithm
to update f to a maximum flow as well as a minimum cut in G0
.
2. [8 POINTS] In the Zero Halting Problem, the input is a binary string x, and the
output is yes if program x halts on the input string 0, and no otherwise.
Show that the Zero Halting Problem is undecidable. As seen in class, you can assume that
the Universal problem D and the Halting problem H are undecidable.
Be sure to justify your answer.