Suppose that someone gives you a black-box algorithm A that takes an undirected

Question

Suppose that someone gives you a black-box algorithm A that takes an undirected graph G = (V, E), and a number k, and behaves as follows. If G is not connected, it simply returns "G is not connected." If G is connected and has an independent set of size at least k, it returns "yes." If G is connected and does not have an independent set of size at least k, it returns "no." Suppose that the algorithm A runs in time polynomial in the size of G and k. Show how, using calls to A, you could then solve the Independent Set Problem in polynomial time: Given an arbitrary undirected graph G, and a number k, does G contain an independent set of size at least k?

Explanation / Answer

Theorem If G = (V, E) is a graph, then S is an independent set V S is a vertex cover.Proof. = Suppose S is an independent set, and let e = (u, v) be some edge. Only one of u, v can be in S. Hence, at least one of u, v is in V S. So, V S is a vertex cover. = Suppose V S is a vertex cover, and let u, v S. There can’t be an edge between u and v (otherwise, that edge wouldn’t be covered in V S). So, S is an independent setIndependent Set P Vertex Cover To show this, we change any instance of Independent Set into an instance of Vertex Cover: • Given an instance of Independent Set hG, ki, • We ask our Vertex Cover black box if there is a vertex cover V S of size |V| k. By our previous theorem, S is an independent set iff V S is a vertex cover. If the Vertex Cover black box said: yes: then S must be an independent set of size k. no: then there is no vertex cover V S of size |V| k, hence there is no independent set of size k.

Actually, we also have: Vertex Cover P Independent Set Proof. To decide if G has an vertex cover of size k, we ask if it has an independent set of size n k. So: Vertex Cover and Independent Set are equivalently difficult.

Def. We say X is NP-complete if: • X NP • for all Y NP, Y P X. If these hold, then X can be used to solve every problem in NP. Therefore, X is definitely at least as hard as every problem in NP. Theorem If X is NP-complete, then X is solvable in polynomial time if and only if P = NP. Proof. If P = NP, then X can be solved in polytime. Suppose X is solvable in polytime, and let Y be any problem in NP. We can solve Y in polynomial time: reduce it to X. Therefore, every problem in NP has a polytime algorithm and P = NP.Theorem If Y is NP-complete, and 1 X is in NP 2 Y P X then X is NP-complete. In other words, we can prove a new problem is NP-complete by reducing some other NP-complete problem to it. Proof. Let Z be any problem in NP. Since Y is NP-complete, Z P Y . By assumption, Y P X. Therefore: Z P Y P X.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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