Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Circulation with demands and lower bounds] (Research exercise) Consider a flow network G = (V, E, c, l, d) given to the problem of circulation with demands and lower bounds (see textbook pages 382-384). Here, V is the set of nodes, E is the set of edges, c(e) and l(e) are, respectively, the upper bound and the lower bound of flow on an edge e ∈ E, and d(v) is the demand at a node d ∈ V.
Briefly summarize the key idea for solving the circulation with demands and lower bounds problem by reducing (i.e., reformulating) it to the circulation with demands in the textbook pages 379-382.
Give a sketch of the reduction algorithm that constructs a flow network G’ = (V, E, c’, d’) from G = (V, E, c, l, d).
Give the runtime complexity of the reduction algorithm with an explanation, assuming an adjacency list representation of the graph (V, E). Note that G’ has no lower bounds on its edges.
(25) [Self-reducibility] Show how the optimization version of vertex cover problem is polynomial time-reducible to its decision version. The optimization version, known as min vertex cover problem, is “given a graph G, find the minimum set of vertices that cover all the edges in G”. The decision version is “given a graph G and a constant k, is there a vertex cover of at most k vertices?” Here, we say a vertex “covers” an edge if and only if the vertex is an end-node of the edge.
