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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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