Exercise 20 | RACSO

Exercise _‹20_›:

VERTEX COVER

\leq

INDEPENDENT SET

Reduce the VERTEX COVER problem to the INDEPENDENT SET 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)) \}$
INDEPENDENT SET: given a natural $k$ and an undirected graph $G$ , is there a subset $S$ of nodes with size at least $k$ such that any two distinct nodes of $S$ are not connected by an edge in $G$ ?
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|\geq k\;\wedge\;\forall u,v\in S: (u\neq v\;\Rightarrow\;\{u,v\}\notin E)) \}$

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
       edges: array of array [2] of string
       nodes: array of string
     }
```
The output is a natural number out.k and an undirected graph, which is described with the list of edges out.edges and with the list of nodes out.nodes. An edge is a pair of nodes, and each node is represented by either an integer or a string. The list of nodes out.nodes is optional, and contains nodes of the graph, that may or may not appear in the list of edges. This list of nodes could be useful, for example, for including the nodes that are not connected to any other node, if this is considered necessary.

Note: If the output out.k is greater than the number of nodes, then no such independent set exists. Repeated edges and self-loop edges are ignored.

Authors: Carles Creus, Nil Mamano / Documentation:

Exercise ‹20›:

Exercise _‹20_›: