hi friends !!!!!!!
i have one problem.... please help me in solving it...
problem : given the nodes of the graph.All nodes are connected in such a manner that we can go any other node from any node.we need to keep marking at some of the nodes so that all nodes become protected. A node is said to be protected if that node has marked or the immediate adjacent node has marked.so,we need to to find the minimum number of markings we should place so that all nodes become protected.
for example :
input: N — no. of nodes, M — no.of edges
a[1] a[2]....... a[n]
m queries showing edges between nodes.
ex:
7 6
1 2 3 4 5 6 7
1 2
2 4
2 3
3 6
3 5
5 7
output:
answer — minimum no.of marks to be placed.
ex:
3
--for the above test case.
constraints :no. of nodes <=3000
task 1: if it is a tree..means having no cycles.
task 2: if it is a graph.
For general graph, this is an NP complete problem. That means there is no known efficient algorithm.
What about constraints?
he has just updated the constraints (n ≤ 3000).
It is an NP-hard problem. See set cover problem for more details.
Here is my previous comment where I misread it to be a vertex cover problem.
This is called the Minimum Vertex Cover problem. For a general graph, the problem is NP-hard. However, it can be done in linear time using a depth-first-search if the given graph is a tree. Also, if your graph is a Bipartite Graph, you can use [Konig's theorem](http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory)) to solve it using maximum matching.
It's not a vertex cover, because he wants to cover nodes, not edges. That doesn't change the situation too much, because it's still NP-hard on the general case and the tree solution doesn't change significantly.
actually, this problem is not Minimum Vertex Cover.
consider the case of a triangle (K3 graph). MVC will return
2, but correct answer is1.Please dont reply to this guys posts. He is asking questions from an ongoing contest @ http://www.hackerearth.com/jda-hackathon/problems/
He can never become a hacker :P