# That clause postmodifier

Classified in Computers

Written at on English with a size of 2.46 KB.

- SAT
_{p }Ind. Set. -**2** - Ind.Set
_{p }Vertex Cover -**1** - Vertex Cover
_{p }Set Cover - Vertex Cover
_{p}Hitting Set - SAT
_{p}3-COL - SAT
_{p}Ham. Cycle - Ham. Cyc.
_{p }Ham. Path - Ham. Cyc.
_{p }TSP - Hamiltonian Path With Specified Extremes
**- 3** - Independent Set to Diverse Subset
**- 4**

**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 3:

.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