[Solved]: Connected Graph: Select the minimum number of nodes such that the node and neighbor covers everything

Problem Detail: 

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.

Asked By : nepee

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47589