Exercise 31 | RACSO

Exercise _‹31_›:

choose

\{

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

\}

\leq

Separating Troublesome People

Consider the following problem:

Separating Troublesome People: After some recent firings, John Doe has noticed that the morale at the office is quite low, that the employees show small interest in their tasks, and that they exhibit harsh demeanors against the co-workers that they don’t like. In order to improve the situation and avoid possible conflicts, John Doe has decided to rearrange everyone such that any two employees that are not friends work in different floors of the office. To this end, he has figured out which co-workers are befriended but, since the current building only has $3$ floors, is it possible to rearrange all the employees such that, at each floor, all the people is befriended?

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 {
       people: array of string
       friendship: array of array [2] of string
     }
```
The output is a list of proper names out.people and a list of friendship relations out.friendship. A friendship relation is a pair of proper names from two friends. The list of proper names out.people is optional, and contains names that may or may not appear in the list of friendship relations. This list of proper names could be useful, for example, for including the names of the people without friends, if this is considered necessary.

Note: If the generated output has no people, it is considered possible to rearrange everyone. Repeated friendship relations and self-friendship relations are ignored (it is considered that everyone is friend with himself/herself).

Authors: Carles Creus / Documentation:

Exercise ‹31›:

Exercise _‹31_›: