Please answer All the parts , its compulsory to solve (a,b). because these are short questions.and Related to each other, I can't post them separately. i will give you thumbs up vote for this, if you will solve all the above parts.

(d) Based on the reduction shown in the appendix, what is the Boolean expression o corresponding to this diagram: C51 C53 C61 C63 C71 C73 C81 C83 C52 C62 C72 C82 11 21 22 12 13 T3 14 14. C12 C22 C32 C42 C11 C13 C21 C23 C31 C33 C41 C43 Solution 21 22 C3 24 11 22 23 24 Ci C2 C3 C4 C5 C6 C7 Cs Here, o=C1 1 C2 C3 C4 C5 AC61C7 A Cg. Put a tick under xi or , in the c; row if it is included in the clause cj. 10 THE VERTEX COVER PROBLEM a If G is an undirected graph, a vertex cover of G is a subset of the nodes where every edge of G touches one of those nodes. The vertex cover problem asks whether a graph contains a vertex cover of a specified size: VERTEX-COVER = {{G,k)| G is an undirected graph that has a h-node vertex cover}. THEOREM 7.44 VERTEX-COVER is NP-complete. PROOF IDEA To show that VERTEX-COVER is NP-complete, we must show that it is in NP and that all NP-problems are polynomial time reducible to it. The first part is easy; a certificate is simply a vertex cover of size h. To prove the second part, we show that 3SAT is polynomial time reducible to VERTEX-COVER. The reduction converts a 3cnf-formula o into a graph G and a number ki, so that o is satisfiable whenever G has a vertex cover with k nodes. The conversion is done without knowing whether o is satisfiable. In effect, G simulates o. The graph contains gadgets that mimic the variables and clauses of the formula. Designing these gadgets requires a bit of ingenuity. For the variable gadget, we look for a structure in G that can participate in the vertex cover in either of two possible ways, corresponding to the two pos- sible truth assignments to the variable. The variable gadget contains two nodes connected by an edge. That structure works because one of these nodes must appear in the vertex cover. We arbitrarily associate TRUE and FALSE with these two nodes. For the clause gadget, we look for a structure that induces the vertex cover to include nodes in the variable gadgets corresponding to at least one true literal in the clause. The gadget contains three nodes and additional edges so that any ver- tex cover must include at least two of the nodes, or possibly all three. Only two nodes would be required if one of the variable gadget nodes helps by covering an edge, as would happen if the associated literal satisfies that clause. Other- wise, three nodes would be required. Finally, we chose k so that the sought-after vertex cover has one node per variable gadget and two nodes per clause gadget. PROOF Here are the details of a reduction from 3SAT to VERTEX-COVER that operates in polynomial time. The reduction maps a Boolean formula o to a graph G and a value k. For each variable r in o, we produce an edge connecting two nodes. We label the two nodes in this gadget x and 7. Setting .r to be TRUE corresponds to selecting the node labeled x for the vertex cover, whereas FALSE corresponds to the node labeled 7. 12 (d) Based on the reduction shown in the appendix, what is the Boolean expression o corresponding to this diagram: C51 C53 C61 C63 C71 C73 C81 C83 C52 C62 C72 C82 11 21 22 12 13 T3 14 14. C12 C22 C32 C42 C11 C13 C21 C23 C31 C33 C41 C43 Solution 21 22 C3 24 11 22 23 24 Ci C2 C3 C4 C5 C6 C7 Cs Here, o=C1 1 C2 C3 C4 C5 AC61C7 A Cg. Put a tick under xi or , in the c; row if it is included in the clause cj. 10 THE VERTEX COVER PROBLEM a If G is an undirected graph, a vertex cover of G is a subset of the nodes where every edge of G touches one of those nodes. The vertex cover problem asks whether a graph contains a vertex cover of a specified size: VERTEX-COVER = {{G,k)| G is an undirected graph that has a h-node vertex cover}. THEOREM 7.44 VERTEX-COVER is NP-complete. PROOF IDEA To show that VERTEX-COVER is NP-complete, we must show that it is in NP and that all NP-problems are polynomial time reducible to it. The first part is easy; a certificate is simply a vertex cover of size h. To prove the second part, we show that 3SAT is polynomial time reducible to VERTEX-COVER. The reduction converts a 3cnf-formula o into a graph G and a number ki, so that o is satisfiable whenever G has a vertex cover with k nodes. The conversion is done without knowing whether o is satisfiable. In effect, G simulates o. The graph contains gadgets that mimic the variables and clauses of the formula. Designing these gadgets requires a bit of ingenuity. For the variable gadget, we look for a structure in G that can participate in the vertex cover in either of two possible ways, corresponding to the two pos- sible truth assignments to the variable. The variable gadget contains two nodes connected by an edge. That structure works because one of these nodes must appear in the vertex cover. We arbitrarily associate TRUE and FALSE with these two nodes. For the clause gadget, we look for a structure that induces the vertex cover to include nodes in the variable gadgets corresponding to at least one true literal in the clause. The gadget contains three nodes and additional edges so that any ver- tex cover must include at least two of the nodes, or possibly all three. Only two nodes would be required if one of the variable gadget nodes helps by covering an edge, as would happen if the associated literal satisfies that clause. Other- wise, three nodes would be required. Finally, we chose k so that the sought-after vertex cover has one node per variable gadget and two nodes per clause gadget. PROOF Here are the details of a reduction from 3SAT to VERTEX-COVER that operates in polynomial time. The reduction maps a Boolean formula o to a graph G and a value k. For each variable r in o, we produce an edge connecting two nodes. We label the two nodes in this gadget x and 7. Setting .r to be TRUE corresponds to selecting the node labeled x for the vertex cover, whereas FALSE corresponds to the node labeled 7. 12