## Exercise ‹28›:

choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Seating Shy Guests
Consider the following problem:
• Seating Shy Guests: John Doe must organize the next dinner party for his company. Unfortunately, he is facing the unexpected challenge that his co-workers are extremely shy, and none of them will sit next to someone with whom they do not feel confident. Through a lot of discreet questions and some gossiping, John Doe has managed to obtain a list of which co-workers are befriended. With this information, is it possible to seat everyone at a round table such that each person has a friend to his/her left and to his/her right?
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 {
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 seat everyone at a round table. In the particular case where there is only one person, it is taken into account if he/she is friend with himself/herself, in any other case such information is ignored. Repeated friendship relations are ignored.
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.