## Exercise ‹19›:

VERTEX COVER $\leq$ SET COVERING
Reduce the VERTEX COVER problem to the SET COVERING problem. These problems are defined as follows:
• VERTEX COVER: given a natural $k$ and an undirected graph $G$, is there a cover for $G$ of size at most $k$? In other words, is there a subset $S$ of nodes with size at most $k$ such that each edge of $G$ involves a node from $S$?
More formally, this problem can be defined as the following set:
$\{ \langle k,G=\langle V,E\rangle\rangle \mid \exists S\subseteq V: (|S|\leq k\;\wedge\;\forall \{u,v\}\in E: (u\in S\;\vee\;v\in S)) \}$
• SET COVERING: given a natural $k$ and a collection of finite sets $S_1,\ldots,S_n$, is there a cover for $S_1\cup\ldots\cup S_n$ of size at most $k$? In other words, is there a selection of at most $k$ of such sets $S_i$ such that their union equals the union of all the sets $S_1,\ldots,S_n$?
More formally, this problem can be defined as the following set:
$\{ \langle k,\langle S_1,\ldots,S_n\rangle\rangle \mid S_1,\ldots,S_n\text{ finite sets}\;\wedge\;\exists \{i_1,\ldots,i_m\}\subseteq\{1,\ldots,n\}: (m\leq k\;\wedge\;(S_1\cup\ldots\cup S_n)=(S_{i_1}\cup\ldots\cup S_{i_m})) \}$
The input and output of the reduction conform to the following data types:
• in: struct {
k: int
numnodes: int
edges: array of array [2] of int
adjacents: array of array of int
adjacencymatrix: array of array of int
}

The input is a natural number in.k and an undirected graph. The graph is given by means of four different kinds of information: the number of nodes in.numnodes, the list of edges in.edges, for each node the list of its adjacent nodes in.adjacents, and the adjacency matrix in.adjacencymatrix. The nodes are integers between $1$ and in.numnodes, and thus, the $0$’th position of in.adjacents does not contain useful data and should be ignored; for any other position $p$, in.adjacents[p] is the list of nodes adjacent to $p$. For the same reason, the $0$’th row and column of in.adjacencymatrix do not contain useful data and should be ignored; for any other row $r$ and column $c$, in.adjacencymatrix[r][c] is $0$ when there is no edge between the nodes $r$ and $c$, and $1$ otherwise.

Note: The input graph has at least one node, no repeated edges, nor self-loop edges, and the value of in.k is at most the number of nodes of the graph.
• out: struct {
k: int
sets: array of array of string
}

The output is a natural number out.k and a list of sets out.sets. The elements of the sets are integers or strings.

Note: If the output out.k is negative, then no such set covering exists. Empty sets are ignored.
Authors: Carles Creus / Documentation:
 main { // Write your reduction here... } To be able to submit you need to either log in, register, or become a guest.