Solve a & b.

(25 pt) A vertex cover of an undirected graph G = (P, E) is a subset VCV such that if (u, v) e E then or veV (or both). The Vertex-Cover Problem (VC) is to find a vertex cover of minimum size in G. a. Formally describe the decision problem of VC. Let it be VCD. b. The 3-CNF-SAT problem (3SAT) is defined as follows: Definition: 3SAT-. Boolean formula in 3-conjunctive normal form is satisfiable Use the reduction from 3SAT shown below to prove that VCD is NP-complete. No partial credit for reduction from any other NP-complete problem. (Hint: What is the size of the vertex cover for the reduced graph?) r (r