5
$\begingroup$

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that does have a coffee machine. (For any two meeting rooms, the architect has told us whether or not they are close enough.) Our problem is to determine among all the meeting rooms of any university campus, which ones should have coffee machines so that we use as few coffee machines as possible. Specify this problem as an optimization problem on a graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee). Prove that the Coffee Machine Decision Problem is NP-complete.

Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.

I'm confused at the hint given and why this problem isn't just a straight reduction from Vertex Cover. What's the point of adding two more edges and a vertex for every edge?

$\endgroup$
  • $\begingroup$ Deleted my nonsense answer. You should post your correct observation as an answer (and accept it!) $\endgroup$ – Luke Mathieson Apr 19 '13 at 14:38
  • $\begingroup$ The given problem is not identical to the original vertex cover problem. Recall that in vertex cover, we want to choose a subset of vertices from a graph in such a way that all edges are incident to at least one vertex of the set. Here, we are not interested in a subset of vertices that covers all edges, but in a subset of vertices to have all vertices covered by a neighbor vertex. Hence the need for a reduction. As an example, consider a "triangle"-graph. If we choose one vertex, we have a cover as needed in the given problem, but not a vertex cover. $\endgroup$ – Cornelius Brand Apr 19 '13 at 18:46
5
$\begingroup$

As I already pointed out in my comment, there is in fact a need for a transformation of the problem. The problem you ask for is not known as vertex cover, but as dominating set. The proof then goes as follows:

We transform an instance of vertex cover $(V, E, k)$ as follows (we assume that the graph $(V,E)$ is connected). For every edge - just as the hint says - add two edges and one vertex. More precisely, for an edge $uv \in E$, add a new node $w \not\in V$ and edges $vw, wu$ to the graph. The resulting graph constitutes an instance of Coffee in the obvious way, that is, the "close-enough"-relation is represented by edges and the meeting rooms are represented by vertices. Let $(V', E', k)$ denote the instance of coffee produced by the transformation.

We now need to show now that $(V, E)$ has a vertex cover of size $\leq k$ if and only if for $(V', E')$ it suffices to use $\leq k$ coffee machines.

"$\Rightarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a vertex cover of $(V,E)$. It is clear that the same choice of nodes produces a valid choice for coffee machine placement on $(V', E')$, as we assumed $(V, E)$ to be connected.

"$\Leftarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a valid choice for coffee machine placement. WLOG, assume that $\forall i \in \{1, \ldots, l\}: v_i \in V$, for if $v_s \in V' - V$ with $1 \leq s \leq l$, we can obtain another valid choice for coffee machine placement by replacing $v_s$ with $v \in V$ such that $vv_s \in E' - E$, that is, with one of the two nodes "between" which $v_s$ was inserted by the transformation. Note that these two nodes were also precisely the ones that were covered by choosing $v_s$ to have a coffee machine. By construction, there must have been an edge between the two nodes and an edge between $v_s$ and each of the two nodes. So by replacing $v_s$ with one of them, we don't shrink the set of covered nodes. Then, $v_1, \ldots, v_l$ constitutes a vertex cover of $(V, E)$. To show this, let $uv \in E$. By construction, there is $w \in V' - V$ and $uw, wv \in E' - E$, and no other edges are incident to $w$. As $(V', E')$ covers $w$, one of $u$ or $v$ need must have been chosen as places for a coffee machine, and thus, $uv$ is incident to at least one node in $\{v_1, \ldots, v_l\}$. Thus, $v_1, \ldots, v_l$ is a vertex cover of size $l \leq k$.

$\endgroup$
  • 6
    $\begingroup$ The tl;dr version is that the coffee machine problem is just Dominating Set and the construction is the standard VC to DS construction. $\endgroup$ – Luke Mathieson Apr 21 '13 at 10:19
  • $\begingroup$ I was not aware that the described problem is usually referred to as dominating set. This might indeed be helpful, thank you. $\endgroup$ – Cornelius Brand Apr 21 '13 at 12:09
  • $\begingroup$ Then I'd give you another +1 for that answer if I could. $\endgroup$ – Luke Mathieson Apr 21 '13 at 13:09
  • $\begingroup$ @LukeMathieson: There you go. ;) $\endgroup$ – Raphael Apr 21 '13 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.