Description
1 Flows and Min-Cuts
Let G = (V, E) be a directed graph with source s and T = {t1, . . . , tk} ⊆ V be a set of terminals.
For any X ⊆ E, let r(X) denote the number of vertices v ∈ T that remains reachable from s in
G − X.
1
Give an O(|T|·|E|) time algorithm to find a set X of edges that minimizes the quantity r(X)+|X|.
(Note that setting X equal to the empty-set is allowed). [20 marks]
Hint: Look at (s, t)-max-flow (and corresponding mi-cut) in an appropriate auxiliary graph H
computed from G.
2 Hitting Set
Consider a set U = {u1, . . . , un} of n elements and a collection A1, A2, . . . , Am of subsets of U.
That is, Ai ⊆ U, for i ∈ [1, m]. We say that a set S ⊆ U is a hitting-set for the collection
A1, A2, . . . , Am if S ∩ Ai
is non-empty for each i.
The Hitting-Set Problem (HS) for the input (U, A1, . . . , Am) is to decide if there exists a hittingset S ⊆ U of size at most k.
1. Prove that Hitting-Set problem is in NP class. [5 marks]
2. Prove that Hitting Set is NP-complete by reducing Vertex-cover to Hitting Set. [15 marks]
3 Feedback Set
Given an undirected graph G = (V, E), a feedback-set is a set X ⊆ V satisfying that G − X has
no cycle. The Undirected Feedback Set Problem (UFS) asks: Given G and k, does there exist a
feedback set of size at most k.
1. Prove that Undirected Feedback Set Problem is in NP class. [5 marks]
2. Prove that Undirected Feedback Set Problem is NP-complete by reducing Vertex-cover to
Undirected Feedback Set Problem. [15 marks]
Hint: Consider the polynomial time reduction of vertex-cover to dominating-set covered in Lecture.
1G − X is defined as (V, E \ X)
2