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.
2006-10-19
02:50:03
·
1 answers
·
asked by
Z R
1
in
Mathematics