Noogler_from_Google's blog

remove minimum number of vertices such that there is no path from start node to end node
By Noogler_from_Google, 3 years ago, In English

Given a directed graph we need to find a set of minimum vertices to be removed so that there will be no path from the given start node to the end node.

I tried to find the solution for this and I got to know that there is a solution with max-flow min-cut but I didn't get that. Or is there any other solution for this. By seeing the problem statement it looks pretty standard. Can anyone help me?

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

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

This seems suspiciously like a question from an ongoing hiring test ;)

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

I'm pretty sure this is from an ongoing contest, I got messaged the same question by someone else who I don't even know

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

Remove the end node, answer is 1 :)

→ Reply