主观题：Dominating set problem

**Dominating set problem**: given an undirected graph $$G=(V,E)$$ and an integer $$k$$, decide if there exists a subset $$D$$ of $$V$$, such that $$D$$ consists of $$k $$ vertices and for each vertex of $$V$$, it is either in $$D$$ or adjacent to some vertex in $$D$$. $$D$$ is called a $$k$$-domination set. 

Present a complete polynomial time reduction from the dominating set problem to the $$k$$-center problem on a network. 

With the reduction, show that 2-approximation is the best possible for the $$k$$-center metric problem assuming that P $$\ne$$ NP. If the $$k$$-center problem is not defined on a metric space, what approximation we can expect? 








答案：