CS计算机代考程序代写 Homework 4B of cs 6382

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