Exercise ‹29›:

choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Placing Fire Extinguishers
Consider the following problem:
• Placing Fire Extinguishers: After some unfortunate fire-related accidents during the last business dinner party, John Doe has been asked to improve the safety at the office. His task looks simple enough: place brand-new extinguishers at each room. However, due to the recent budgets cuts, his co-workers are afraid that he will not have enough extinguishers for all the rooms, and none of them wants to be left without an extinguisher at his/her room. After some heated discussions, everyone has settled for the following solution: if a room has no extinguisher, then at least one of the adjacent rooms must have one. John Doe has managed to obtain the number of new extinguishers and a map of the building. With this information, is it possible to place the extinguishers meeting the co-workers demands?
Prove to John Doe that he is facing an NP-hard problem with a reduction from one of the following problems:
1. 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$?
2. 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$?
3. 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$?
4. 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$?
5. 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?
6. 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 {
extinguishers: int
rooms: array of string
adjacents: array of array [2] of string
}

The output is a number of fire extinguishers out.extinguishers, a list of room names out.rooms, and a list of pairs of adjacent rooms out.adjacents. The list of room names out.rooms is optional, and contains names that may or may not appear in the list of adjacent rooms. This list of room names could be useful, for example, for including the names of the isolated rooms, if this is considered necessary.

Note: If the generated number of extinguishers is negative, then it is not possible to place them. Repeated adjacency information is ignored, as well as stating that a room is adjacent to itself.
Authors: Carles Creus / Documentation:
 main( // Choose the problem to reduce from by uncommenting the // corresponding line: // CLIQUE // DOMINATINGSET // VERTEXCOVER // THREECOLORABILITY // UNDIRECTEDHAMILTONIANCIRCUIT // SAT ) { // Write your reduction here... } To be able to submit you need to either log in, register, or become a guest.