This question is related with Introduction to the Theory of Computation 3rd This

Question

This question is related with Introduction to the Theory of Computation 3rd

This question is related with Introduction to the Theory of Computation 3rd INDEPENDENT-SET: INSTANCE: (G, k), where G is a graph and k in NP in N. QUESTION: Is there an independent in G of size k? (a set of vertices where no pair shares an edge) 2.2(a) Give two positive instances for INDEPENDENT-SET. 2.2(b) Give two negative instances for INDEPENDENT-SET. 2.2(c) Construct an algorithm that is a polynomial-time veri er for the INDEPENDENT-SET decision problem. 2.2(d) Conclude that INDEPENDENT-SET

Explanation / Answer

An independent set consists of a group of nodes where for any of the pair of nodes in the set there is not any edge between those nodes. A clique is a group of the nodes where for any pair of the nodes in the set there is any edge between those nodes. For this reason an independent set in the graph G is a clique in the complement of G and its vice-versa.

Thus a simple transformation would be given to G and k to produce Gc (i.e the complement of G) and k. So G has an independent set of size k if and only if the Gc has a clique of the size k.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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