# 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 Av,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