Exercise 19 | RACSO

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:

Authors: Carles Creus / Documentation: