I have got an undirected weighted connected graph. If I select one vertex I automatically select all the vertices connected directly with it. What will be the algorithm so that I am able to select all the vertices of the graph using minimum number of tries? In each try I select one vertex. For example for adjacency matrix a[][]={1,1,0,0,0, 1,1,1,1,0 ,0,1,1,0,0 0,1,0,1,1 0,0,0,1,1} I have to either select vertex 2 and 4 or vertex 2 and 5.
+2
A:
This seems equivalent to the vertex cover problem. It's NP Complete. One of the algorithms that Wikipedia suggests is:
"One algorithmic technique that works here is called bounded search tree algorithm, and its idea is to repeatedly choose some vertex and recursively branch, with two cases at each step: place either the current vertex or all its neighbours into the vertex cover."
edit
here's a proof that solving vertex cover will solve your problem, provided there is no vertex that has no edge:
(*) A solution to vertex cover also solves your problem
For every edge, at least one of the endpoints is selected by vertex cover. If there is at least one edge connected to every vertex, then all vertices end up selected (either directly or by virtue of neighboring a directly-selected vertex), solving the problem.
Note that the converse does not hold:
(*) A solution to your problem does not necessarily solve vertex cover.
consider this graph:
[ ] ----- [X] ¦ ¦ ¦ ¦ [ ] ----- [X]
Directly-selected nodes are marked with an "X". This graph solves your problem as stated, yet the leftmost edge is not covered (so this is not a vertex cover solution).
redtuna
2009-08-20 11:47:40
Thanks for the reply. But I know for sure this is not np complete.
2009-08-20 13:05:19
You're welcome! I'm curious as to how you know that it's not NP-complete: Ire-and-curses points out that this is exactly the dominating set problem, and Wikipedia indicates that the dominating set problem is NP-Complete, by reduction to vertex cover. It does allow some exceptions, for example if you know the cover'll be small (or constant size, even better). In the general case, though, it really does look to me like this problem is NP-Complete.
redtuna
2009-08-20 13:58:27
I dont have any proof.This problem is a coding competition practice problem and admin told that it is not np complete. Here is the link ..http://www.codechef.com/problems/MMADNESS/. I would like to get some clue on how to approach the problem and i will try solving it.
2009-08-20 14:12:14
Given that you have at most 26 machines and 100 links, brute force might work fairly well. Try the bounded search I suggest above. Or you could try enumerating all the choices of n selected nodes, for increasing values of n, until you find a satisfying assignment.
redtuna
2009-08-20 14:22:07
Well then, who do we trust? Armies of complexity theory books stating that Vertex Cover is in NP or codechef.com?
Christoph
2009-08-20 16:09:01
@redtuna -The solution to vertex cover doesn't necessarily solve my problem as nodes(minimum)<=nodes in the vertex cover.I need to find minimum number of nodes and minimum vertex cover will always more nodes than minimum nodes in my problem. @christoph-This problem is different from vertex cover.This is pointed by redtuna also above.
2009-08-20 17:36:20
you're right that I didn't prove that a minimal vertex cover was a minimal dominating set. I would just go for an exhaustive search, with an increasing number of selected nodes. Start by selecting |V|/(|E|+1) nodes: since each node can cause at most |E| others to be selected, there cannot exist a dominating set smaller than that size. As for Christoph, his point still stands if you believe that there are armies of books that state that dominating sets is NP-Complete (I didn't check).
redtuna
2009-08-21 10:25:25
@redtuna-yes you are right this is dominating set problem and is np complete.I will try to solve it with greedy set cover heuristic.
2009-08-21 19:20:22
+4
A:
As already pointed out by red tuna, this is a type of vertex cover problem. Specifically, it's a dominating set problem, the main difference being that a dominating set can be much smaller than a correct vertex cover.
You can model this as a set cover problem. Each vertex is represented as a subset containing itself and all adjoining vertices. If you don't need to guarantee an exact optimal solution (just a very good one), you can then apply the greedy set cover heuristic to achieve an approximation to the optimal set in lg n time.
ire_and_curses
2009-08-20 12:13:05