Assertion: The original graph has a vertex cover of size n if and only if the new graph has a dominating set of size E+n. Proof: If there is a vertex cover of size n, then fortifying these same villages dominates at least one of the new villages on each road; we can dominate the other new villages and, if necessary, the other original village by adding a fort at the farthest new village, so there is a dominating set of size E+n. Conversely, suppose there is a dominating set of size E+n. This must clearly include at least one of the new villages on each edge. If it includes at least two, then we can do at least as well by fortifying the two new villages which are at junctions; and we can then again do at least as well by moving one of the forts [which may then become redundant] to its corresponding original village. So, there is a dominating set of size no more than E+n in which exactly one of the new villages on each edge is fortified, and therefore at least one is guarded by a fort in an old village. Hence, there are no more than n forts in original villages, and at least one covering each edge. QED.
Discussion: If you're transforming from VC, you clearly need to add a little construction to each edge [otherwise you can't get back from a dominating set to a vertex cover -- for a trivial example, note that a triangle needs only one fort to cover all the vertices, but two to cover the roads]. This has to have the `if and only if' nature of the above proof, so we need a construction in which one extra fort covers the new construction if and only if at least one end of the road is fortified. Then you just have to play around, discovering that one extra village, then two, then three in a triangle or a straight line don't work, but that four in a diamond do. [Better alternative construction: A simpler alternative is to build a by-pass for each current road, and put a village on each by-pass (effectively, turn each road into a triangle). This has the same properties as the above diamond. Thanks to Carina Salt, who produced a correct solution along these lines.]
It's also possible to transform directly from 3SAT. You have again to be quite careful. You obviously want a triangle for each clause and a line for each variable, much as in the proof for VC, with the variables joined up to the triangles somehow. But you then need to make sure that one of the variables is fortified -- the easiest way is to add a third village for each variable, making a triangle. Then you need to attach the triangle to the variables in such a way that it can be done with, say, two forts if and only if one vertex is connected to a fortified variable and cannot be done with fewer forts even if all vertices are connected to fortified variables [else you may get some spare forts to make some variables both true and false]. Over to you -- ingenuity needed! Note: You cannot expect to get many marks for `merely' slapping down `the same' proof as for the transformation from 3SAT to VC; it's a different problem!
Marks: Top and tail, DS is in NP and `transforms so is NP-complete'', and the observation that the transformation can be done in polynomial time -- 3 marks each, total 9. For the actual transformation, 16 marks, split 6, 5, 5 between the construction, the `VC implies DS' and the `DS implies VC' parts; total 25. Part-marks for incorrect transformations, depending on ingenuity. No marks for null transformations -- the example of the triangle is too obvious!
Marks: As above, 9 [a gift!] for the surrounding paraphernalia. For the transformation, 11 -- this is a much more obvious transformation than that for DS! --, total 20.
Note: If it makes it clearer, think of A and notA as a `husband and wife' pair, and so on for each variable, and the clause groups such as A, notB, C and false [from the above example] as being the butchers [or the bakers or the candlestickmakers or ...]. Then the sets to be split are each pair and each profession.
G12FCO home page.
Previous solutions.
Next solutions.
This coursework.