## Exercise ‹32:

choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Firing Married Couples
Consider the following problem:
• Firing Married Couples: The recent restructuring of the company has not made it more profitable. According to the managers, the productivity is still terribly low because some of the employees are married couples: the managers argue that having the spouse working at the same place necessarily becomes a distraction for both members of the couple. For this reason, John Doe has been asked to end the distractions by firing one member of each couple. This uneasy task is made even more complicated by the following restriction: since the company is working on several projects, the layoffs must be done in such a way that at least one of the employees working on each project is not fired.

John Doe has the list of married couples in the company and knows the different projects each employee is working on (one person might be involved in several projects). With this information, is it possible to fire one member of each couple such that no project loses all its workers?
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 {
couples: array of struct {
wifeprojects: array of string
husbandprojects: array of string
}
singles: array of struct {
projects: array of string
}
}

The output is a list of married couples out.couples and singles out.singles. For each couple the field wifeprojects is the list of projects where the wife is involved, and the field husbandprojects is the list of projects where the husband is involved. For each single, the field projects is the list of projects where he/she is involved.

Note: If the output has no married couples, then the layoffs are possible. If neither the wife nor the husband are involved in any project, then both of them can be fired. No single will be fired, so any project where a single is involved will always have an employee involved after the firings.
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.