## 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