6
$\begingroup$

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.

$\endgroup$
  • $\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 Sep 29 '15 at 16:30
4
$\begingroup$

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.
$\endgroup$
  • $\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 Sep 27 '15 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$ – Pål GD Sep 27 '15 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$ – Luke Mathieson Sep 27 '15 at 9:55
  • 1
    $\begingroup$ @LukeMathieson Or just " ... unless it does. Then it does." $\endgroup$ – Pål GD Sep 27 '15 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 Sep 27 '15 at 14:07

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.