We mentioned in class that for purposes of complexity, it often helps to think o

Question

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.

Explanation / Answer

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 .

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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