The problem is to select the minimum number of nodes from a graph such that, the selected nodes and their neighbors consists of all the nodes of the graph.

Any straight forward algorithm for this? Repeatedly selecting the node with highest degree centrality doesn't work.

Thank you.

  • $\begingroup$ I don't know if this is helpful, but it is possible to construct in polynomial time a dominating set $D$ of size $|D| \leq n \dfrac{1+\ln (\delta+1)}{\delta+1}$, where $n$ is the number of vertices and $\delta$ the minimum degree. This is due to Alon (1990), I think. $\endgroup$
    – Juho
    Commented Sep 29, 2015 at 16:30

1 Answer 1


This depends on what you mean by "straight forward". There's a very straight forward brute force algorithm - it just doesn't have very good performance.

As to which problem this is, I would say it is Dominating Set. A vertex cover is also a dominating set, but not every dominating set is a vertex cover (i.e. a vertex cover might be significantly larger than a dominating set).

As for straight forward algorithms with good performance, you're not in a good spot.

  • It is NP-complete, so no polynomial-time algorithm unless $P = NP$.
  • It is $W[2]$-complete, so no $FPT$-algorithm unless $W[2] = FPT$.
  • It has no $n^{o(k)}$ algorithm unless the Exponential Time Hypothesis fails.
  • It is also $Log$-$APX$-complete, so no $o(\log n)$ approximation algorithm unless $P = NP$.

The best algorithm I know of at the moment is a $O(1.4969^{n})$ exact algorithm, but I don't think that would satisfy the "straight forward" criterion.

Even on restricted classes of graphs, you're unlikely to get good running times.

If you graphs happen to have very small treewidth, local treewidth, or are planar, then there are FPT algorithms, but again, they're not exactly "straight forward".

If you do want to solve Vertex Cover however, then it's still hard, but you have a few more possibilities:

  • Vertex Cover has a 2-approximation (find any maximal matching, and take all the vertices in the matching).
  • Vertex Cover is FPT, and has a number of kernelization algorithms of varying complexity (the more complex ones give significantly better running times). This paper contains details on a relatively simple one and this one the current best.
  • It is also amenable to a number of optimization approaches, and if you have access too something like CPLEX, then the ILP is easy to formulate, and relatively fast to solve.
  • $\begingroup$ In the paper you cited for exact algorithm, I see that they solve the problem of finding minimal 'Independent' dominant set. I haven't read the paper fully, (seems out of my league) but I am wondering if it is same as just 'minimal dominant set' which is actually what I need. I feel like the former might sometime be larger than necessary. I am a Graph Theory Newbie, so please bear with me. Anyway, Can you please explain in plain words the exact algorithm (or any other) which is better than brute force to find the minimal dominanting set? BTW, I don't think I am looking for Vertex Cover.?! $\endgroup$
    – nepee
    Commented Sep 27, 2015 at 6:47
  • 1
    $\begingroup$ Not only FPT, unless FPT = W[2], but I even think we don't expect it to be solvable in $n^{o(k)}$ unless something something something. $\endgroup$ Commented Sep 27, 2015 at 9:49
  • 1
    $\begingroup$ @PålGD, I wish that was the accepted phrasing: "Therefore the problem has no polynomial-time algorithm unless something something something." :) $\endgroup$ Commented Sep 27, 2015 at 9:55
  • 1
    $\begingroup$ @LukeMathieson Or just " ... unless it does. Then it does." $\endgroup$ Commented Sep 27, 2015 at 10:34
  • 2
    $\begingroup$ @PålGD : ​ ​ ​ It's not solvable in n$^{o(k)}$ unless the ETH is false. ​ Also, see this paper. $\hspace{1.49 in}$ $\endgroup$
    – user12859
    Commented Sep 27, 2015 at 14:07

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.