Sin título 1

-SAT (

)> - 2
-Ind.Set ()>- 1
-Vertex Cover ()>- 6
-Vertex Cover ()>-8
-SAT ()>
-SAT ()>
-Ham. Cyc. ()> - 9
-Ham. Cyc. ()>
-Hamiltonian Path With Specified Extremes - 3
-Independent Set to Diverse Subset - 4
-Independent Set to Clique - 5
-Set Cover to Efficient Recruiting - 7

1- input: graph G, integer k
    .call the black-box for Vertex Cover with input G,
    . N−k where n is the number of nodes of G
    .Return the result (’yes’ or ’no’) of the previous call

2- input: CNF F
    .Construct a graph G where the nodes of G are the literals occurring in F (with possible repetitions) and the following edges:
   - An edge joining every pair of complementary literals
   - An edge joining literals occurring in the same clause.
    .Call the black-box for Independent Set with input G, k where k is the number of clauses of F
.Return the result (’yes’ or ’no’) of the previous call

3- input: a graph G and two nodes x and y
    .Construct, using G, a new graph H in the following way: Initially, place in H all nodes and edges in G. Furthermore, we add to H two new nodes, that we call x' and y' , and the following new edges: (x', x) and (y', y)
    .Call the black-box for Hamiltonian Problem with input H
    .Return the result (yes or no) of the previous call

4- input: a graph G and a non-negative integer k
    .Construct a matrix A in the following way: Matrix A has one row for each node in G and one column for each edge in G. So, we can think that the customers of A correspond to nodes of G and the products of A correspond to edges of G. Finally, every entry of matrix A is assigned to a 0 or 1 in the following way. Let v be a node in G and e be an edge in G, then the entry A(v,e) is 1 if node v is incident to edge e and 0 otherwise.
    .Call the black box for the Diverse Subset Problem with input (A, k)
    .Return the result (yes or no) of the previous call

5: input: a graph G and a non-negative integer k
   .Construct the complementary, G, of G. That is, construct a graph G that has the same
nodes than G and contains precisely all those edges that are not in G.
  .Call the oracle for Clique with input (G, k)
  .Return the result (yes or no) of the previous call
6: input: a graph G, integer k >= 0
    .Construct a set U where each element of U is an edge of graph G (in short, U := E)
    .Construct a collection of subsets of U in the following way: we have a subset Si for each node i in G. Subset Si is constructed so that it contains all edges incident to node i.
    .Call the oracle for Set Cover with input U, S(i)i € V , and k
    .Return the result (yes or no) of the previous call