Another person who answered this question earlier didn\'t do part b because it w
ID: 3826035 • Letter: A
Question
Another person who answered this question earlier didn't do part b because it was "hard". I understand it is hard, that is why I need help!
Consider the following decision problem: given an undirected graph G (V, E), a set of terminal vertices TCV, and a fixed parameter K, determine whether there exists a subgraph G' of G such G connects all vertices in T (i.e., there exists a path between any ti,t2 E Tin Gl) and includes at most K non-terminal vertices. Prove that the above problem is NP-complete. Note that this involves showing: (a) (5 points) The above problem is in NP (b) Cl5 points) The above problem is NP-hard. (Hint: You can use the fact that the vertex cover problem that we saw in class is NP-hard.)Explanation / Answer
The brute-force algorithm takes
The verification algorithm takes G and a subset V’ of V vertices as the certificate. It checks whether V’ is a clique in polynomial time by checking whether, for each pair the edge
Let be a Boolean formula in 3-CNF with k clauses, where
For each clause Cr, place a triple of vertices V1r, V2r, V3r.
Regarding edges, 2 vertices iff
2. lir and ljs are consistent, i.e. lir is not the negation of ljs.
1.Supposehas a satisfying assignment. Therefore, each clauses Ci contains at least one literal lir that is assigned 1. Besides, any pair of such literals must be consistent. Therefore, pick one such literal from each clause yields a set of V’ of k vertices and V’ must be a clique.
2.Suppose G has a clique V’ of size k. V’ contains exactly one vertex per triple. Assigning 1 to each literal lir s.t. yields a satisfying assignment.