Algorithms and Data
Spring 2010

Due date: February 17, 2010
At beginning of lecture


Problem 5:

Decision Problems versus Search Problems

This is a continuation of the LeafCovering homework.
In the earlier homework we came up with a yes/no answer
for a given LeafCovering problem.
Now we want to find an uncovered leaf if one exists.
We want to solve a FNP problem and show that it is in FP.

Read:

in the lectures directory:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp10/lectures/On%20the%20Complexity%20of%20Search%20Problems.ppt

For satisfiability, if we have a polynomial-time algorithm for deciding satisfiable/unsatisfiable,
we have a polynomial-time algorithm to find a witness.
We choose a variable x and consider the Shannon cofactors F[x] and F[!x]. If F is satisfiable, one of them
must be satisfiable which tells us how to set x.
We iterate through all variables.

A similar idea works for LeafCovering. 
The algorithm can be viewed as a greedy algorithm.

We know there is a polynomial-time algorithm to solve LeafCovering(k),
where k, a constant, is the number of elements that are covering the leaves.

LeafCovering(k):
Input: A set of trees and M, where |M|=k.
Output: yes or no.

FLeafCovering(k):
Input: A set of trees and M, where |M|=k.
Output: An uncovered leaf or no, if none exists.

Give a polynomial algorithm for FLeafCovering(k).
In other words, show that FLeafCovering(k) is in FP.

Let's assume that each tree has max outdegree of c and 
let's assume the trees are of at most depth d.