# 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