Exercise 30 | RACSO

Exercise _‹30_›:

choose

\{

CLIQUE,DS,VC,3C,UHC,SAT

\}

\leq

Watching Out For Thieves

Consider the following problem:

Watching Out For Thieves: John Doe is concerned about the recent robberies at the office. He suspects that one of his sleazy co-workers is responsible for the disappearance of some of the office supplies (even including fire extinguishers). In order to prove it, he is planning on installing cameras at a few strategic spots. Since he is short on budget, he has decided to install omnidirectional cameras at hallway intersections in order to record multiple hallways with a single camera. John Doe knows how many of such cameras he can afford, and he has located all the strategic spots by consulting a map of the building. With this information, is it possible to install the available cameras at some of the spots such that each hallway is recorded by at least one camera?

Prove to John Doe that he is facing an NP-hard problem with a reduction from one of the following problems:

CLIQUE: 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 connected by an edge in $G$ ?
DOMINATING SET: given a natural $k$ and an undirected graph $G$ , is there a subset $S$ of size at most $k$ of nodes that dominates $G$ ? In other words, is there a subset $S$ of nodes with size at most $k$ such that any node of $G$ is either in $S$ or adjacent to a node in $S$ ?
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$ ?
3-COLORABILITY: given an undirected graph $G$ , is $G$ $3$ -colorable? In other words, is there a mapping $M$ from the nodes of $G$ to $\{1,2,3\}$ satisfying $M(u)\neq M(v)$ for each edge $\{u,v\}$ of $G$ ?
UNDIRECTED HAMILTONIAN CIRCUIT: given an undirected graph $G$ , is there a cycle that visits each node of $G$ exactly once? In other words, is it possible to order the nodes of $G$ such that there is an edge between each $2$ contiguous nodes and an edge between the last and the first nodes?
SAT: given a boolean formula $F$ in conjunctive normal form, is $F$ satisfiable?

The input and output of the reduction conform to the following data types, where for each field of the input it is shown in parentheses the starting problems where such field is present:

```
in: struct {
     (1,2,3)      k: int
     (1,2,3,4,5)  numnodes: int
     (1,2,3,4,5)  edges: array of array [2] of int
     (1,2,3,4,5)  adjacents: array of array of int
     (1,2,3,4,5)  adjacencymatrix: array of array of int
     (6)          numvars: int
     (6)          clauses: array of array of int
    }
```
The input may include a natural number in.k, an undirected graph, or a boolean formula in conjunctive normal form. 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. The boolean formula is described with the number in.numvars of variables occurring in the formula, and with the list of clauses in.clauses. Each clause is a list of literals, and each literal is a positive or negative integer: a positive integer $x$ represents the $x$ ’th variable, and a negative integer $-x$ represents the negation of the $x$ ’th variable. Such an $x$ takes values between $1$ and in.numvars.

Note: The input graph has at least one node ( $2$ in CLIQUE and UHC, $4$ in 3C), no repeated edges, nor self-loop edges, the value of in.k is at most the number of nodes of the graph (and at least $2$ in CLIQUE), and the boolean formula has at least one clause, with every clause having at least one literal and no repeated literals.
```
out: struct {
       cameras: int
       spots: array of string
       hallways: array of array [2] of string
     }
```
The output is a number of cameras out.cameras, a list of spot names out.spots, and a list of hallways out.hallways. A hallway is identified by the names of the two spots it connects. The list of spot names out.spots is optional, and contains names that may or may not appear in the list of hallways. This list of spot names could be useful, for example, for including the names of the isolated spots, if this is considered necessary.

Note: If the generated number of cameras is negative, then it is not possible to install them. If there are circular hallways that connect a spot with itself, then such hallways must also be recorded by a camera. Repeated hallways are ignored.

Authors: Carles Creus / Documentation:

Exercise ‹30›:

Exercise _‹30_›: