trek's blog

A GRAPH PROBLEM
By trek, 10 years ago, In English

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.

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For general graph, this is an NP complete problem. That means there is no known efficient algorithm.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What about constraints?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    he has just updated the constraints (n ≤ 3000).

    → Reply
»
10 years ago, # |
← Rev. 9   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually, this problem is not Minimum Vertex Cover.
    consider the case of a triangle (K3 graph). MVC will return 2, but correct answer is 1.

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please dont reply to this guys posts. He is asking questions from an ongoing contest @ http://www.hackerearth.com/jda-hackathon/problems/

→ Reply