Another person who answered this question earlier didn\'t do part b because it w

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.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.