Help needed in graph question

Given an directed graph and two vertices u and v, remove minimum number of vertices such that v becomes unreachable from u. How to approach this problem?

Note: This question was asked in Juspay Hiring challenge on Hackerearth and contest has been ended.

Hey @galencolin, can you help me out??

What are the constraints? Looks like min cut. You can model the graph as one you can run maxflow on by splitting each vertex v into two vertices: in_v and out_v. All edges that previously went into v will instead go to in_v and edges that previous went out of v now go out of out_v, and all original edges have infinite capacity. Then, create an edge between each in_v and out_v with capacity 1, then run maxflow and you’ll have your answer.

1 Like

There were no constraints… Will have to learn min-cut max flow algorithm.
Thank you for answering!!

Jeez… what kind of problem would require a possibly O(n^3) runtime (with ford-fulkerson) and not give constraints?

2 Likes

Problem was badly framed, I even sent a mail to setter at Hackerearth but no replies! Even the sample test case was too confusing… but still I solved the test-cases which had only 1 path between them.
Anyway thanks for taking your time & helping me out!

1 Like