G12FCO -- Formal Computation

coursework 2 -- NP-completeness

Dominating sets: You are given a network of roads and villages and an integer n. DS is the decision problem of determining whether or not there is a set of n villages that dominate the network. That is, if we build a fort in each of these villages, then every unfortified village is joined by a [single stretch of] road to a fortified village. Show that DS is NP-complete. [Compare DS with VC, where it is the roads not the villages that are controlled. Hint: You can start with either VC or 3SAT, but be warned, the transformation is not trivial -- this is a different problem from VC!]
Set splitting: You are given some people who have various properties -- some are left-handed, some have red hair, some are butchers, some bakers, some candlestick-makers, etc. Of course, some people may have several, or even all, of the properties, some may have none. The SS decision problem is to determine whether or not it is possible to split the people into two teams [not necessarily of equal numbers] such that each team has at least one person with each property. Show that SS is NP-complete. [Hint: start from either SAT or 3SAT. Think of the teams as being the True and False teams. You should find this easier than Q.1.]

Hand in no later than Thursday, April 22nd.