Another math question?

Question

Problem 2 - Dominating Set Problem (DSP): A subset D of vertexes in a directed graph G
is a dominating set if every other vertex in G is adjacent to some vertex in D (for every x /2 D there
is an edge (y, x) for some y 2 D). We are asked ”Given an undirected graph G, does it contain a
dominating set of cardinality k?”
Is DSP in P? if not, is it in NP?
• If the problem is in P give a polynomial-time algorithm that decides it;
• If the problem is in NP, but you cannot show that it is in P give a polynomial-time verifier.

Answer 1

DSP is in NP, based on a reduction from vertex cover.