2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.