on -täydellinen
-palautusten suhteen.
Hallitseva joukko (engl. Dominating Set): Annettu suuntaamaton verkko G = (V,E) ja kokonaisluku k. Voidaanko verkosta G valita enintään k solmun joukko(Vihje: Vrt. solmupeiteongelma.)niin, että valitusta joukosta johtaa kaari jokaiseen joukon ulkopuolelle jäävään solmuun (so. jos
, niin jollakin
on
)?
(Vihjeitä: Cook, Wrathall, alternoivat ja/tai oraakkelikoneet.)
Pisteytys: tehtävät 1 ja 4 á 7 pistettä, tehtävät 2 ja 3 á 8 pistettä, yhteensä 30 pistettä.