# Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?

Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following: given a graph $$(V, E)$$, selecting a set of vertices $$S$$ such that every edge $$e \in E$$ in the graph is connected to some vertices in $$S$$. The problem of minimizing the vertex cover problem is a well-known NP-hard problem.

My question is the following: given a graph $$(V, E)$$, selecting a set of vertices $$S$$ such that every node $$v \in V$$ is either in $$S$$ or connected to the nodes in $$S$$. Is this problem of minimizing the set of $$S$$ NP-Hard? This problem seems to be quite intuitive after learning the vertex cover problem, but I didn't find a similar question after searching. I apologize if I asked duplicated questions.

## 1 Answer

This is called the Dominating Set problem, and it is indeed NP-hard. In fact, it's in some sense harder than Vertex Cover, since it's not fixed parameter tractable (FPT) with respect to the solution size $$k$$.

• Fixed parameter tractable in which parameter? The size? – 6005 Apr 9 at 1:39
• @6005: That's right, I updated the answer. Thanks! – j_random_hacker Apr 9 at 8:56