Sin título 1
Classified in Computers
Written at on English with a size of 3.52 KB.
-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