Homework 4B of cs 6382
(No late homework will be accepted)
1. Show that the following problem has no PTAS unless NP = P : Given a graph, find the
minimum vertex cover.
2. Consider a collection C of subsets of a finite set X. (X, C) is called a hypergraph. A
hypergraph (V, C) is 3-regular if every subset in C contains exactly three elements. A
subcollection M of C is a matching if all subsets in M are disjoint. Show that following
problem is APX-complete: Given a 3-regular hypergraph, find a matching with maximum
cardinality.
3. Does following problem have PTAS if NP 6= P?
Given two collections C and D of subsets of finite set X and a positive integer d, find a
subset A of X, with |A| ≤ d, to maximize
|{C ∈ C | A ∩ C = ∅} ∪ {D ∈ D | A ∩D 6= ∅}|.
(Hint: The Maximum Set Coverage problem has no polynomial-time ( e
1−e−ε)-approximation
for any ε > 0 unless NP = P .)
4. Given a graph G = (V,E), find the minimum subset D of vertices such that every vertex
is either in D or adjacent to a vertex in D. Such a vextex subset D is called a dominating
set. Show that this dominating set problem does not have a polynomial-time (ρ lnn)-
approximation for 0 < ρ < 1/2 unless NP=P.
5. Given a collection of subsets of a finite set X, find a maximum subcollection of disjoint
subsets in C. Show that this problem has no polynomial-time
√
n-approximation unless
NP=P.
1