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.

o If G is no.t 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 6f 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 co!Is 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

We need to find if a graph contains an independent set of atleast size k.

The algorithm as mentioned in the question itself works in polynomial time
and returns yes if the graph contains an independent size of atleast k.The question
is asking to use calls to A to construct a polynomal time algorithm. The answer is
just to call A once and we will have our answer.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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