We mentioned in class that for purposes of complexity it oft

We mentioned in class that for purposes of complexity, it often helps to think of decision versions of problems. We now see a justification of this (such results are true for many other problems).

Consider the Independent-Set problem, in which the input is an undirected graph G = (V, E) and a parameter k, and the goal is to determine if G has an independent set of size k. Suppose we have an oracle O for solving this decision version of independent set (think of it as a library function that takes input a graph G and k and answers YES/NO).

Prove that there exists an algorithm that can find an independent set of size k, if one exists, using a polynomial number of calls to the oracle O, and possibly a polynomial amount of computation of its own.

Solution

Input: (G, k) where G is an undirected graph and k an integer.

Question: Does G have a set of size k? A set is a subset of vertices such that every pair of vertices in the subset is joined by an edge.

Output: “Yes” or “no” as appropriate.

Again the “Yes” (or “Recognize”) answer is polynomial time verifiable, given the following additional information, or certificate: a list of k vertices which are claimed to form a set. To verify this it suffices to check that the list comprises k distinct vertices and that each pair of vertices is joined by an edge. This is readily done in O(k2n) time, and indeed in O(n3) time (for if k > n = |V |, then the graph does not have a k-set).

Again, if the graph does not have a k-set, then any set of k vertices will fail to be fully connected; there will be some pair of in the given k-vertex set with no edge between them. So any proposed certificate will fail to demonstrate that the graph has a k-set.

However, just because you are given a set of k-vertices that does not happen to form a k-set, you cannot then conclude that the graph has no k-set.

there for there exists an algorith to find an independent set of size k using a polynomial number of calls .