[Solved]Given Oracle O E Blackbox Algorithm Takes Input Undirected Graph G V E Integer K Outputs Y Q37256222

You are given an oracle O (i.e., blackbox algorithm) that takesas input an undirected graph G(V, E) and an integer k and outputs”yes” iff the graph is connected and contains a set of kindependent nodes. It outputs ”no” in every other case. Your taskis to design an algorithm that takes any undirected graphG’ (V’ , E’ ) and integerk as an input and returns ”yes” if G’ contains an independent setof size k. We will ask you to come up with two different solutions.Your algorithm may take O as a subroutine and may make polynomialmany calls to O. Your algorithm – except for the unknown runningtime of O – has to run in polynomial time of the input size. Forboth parts of this problem describe your algorithm, prove that itis correct and analyze the running time.

1. First, we ask you to find this algorithm, but with theadditional requirement, that your solution cannot modify the graphG (i.e. you are not allowed to add or remove nodes or edges).

2. Now, find another algorithm to solve this problem. This timeyou may change the graph any way you see fit (as long as you do notmake more than polynomial many algorithmic steps) but can make onlya single call to O

Expert Answer

---

Answer to You are given an oracle O (i.e., blackbox algorithm) that takes as input an undirected graph G(V, E) and an integer k an… . . .