Graph: Finding minimum number of nodes, so that every path from a to b crosses at least one of them

Question

I have a undirected graph, that has start point node (lets say A) and end point node (B). How to find minimum number of nodes so that every path from A to B crosses at least one of them? P.S. Node A and B does not count.

Answer 1

This problem can be solved efficiently using max flow.

Given a graph G' = (V, E), create a new graph G' = (V', E' where V' = V × {in, out} consists of vertices v_in and v_out for each vertex in V, and E' = E_∞ ∪ E₁ where E_∞ = {v_out → w_in | (v → w) ∈ E} has an arc for each edge in E, and E₁ = {(v_in → v_out) | v ∈ V} has an arc for each vertex in V. The capacity of each arc in E_∞ is infinite, and the capacity of each arc in E₁ is 1. Find a max flow from A_out to B_in and the corresponding min cut C. For each arc in E₁ that crosses C, the corresponding vertex should be removed from G.

Answer 2

One solution to this problem would be to find every path from A to B and then find the minimum set of nodes that is contained in every path. But this will only work for small graphs because both of this problems are NP-Hard. So for small graphs (like up to about 1000 nodes maybe) this solution might work in a acceptable time, but for bigger graphs it would probably take much too long.

To find all possible paths from A to B you can check this answer or an implementation here.

After you have found all pathes you can handle the pathes as sets S (where S is a set of sets) and try to find a new set T that contains at least one element of each of the sets in S. Like explained in this answer this problem is known as Hitting-Set-Problem which has some known algorithms for calculating the solution to this problem like this approximation algorithm (but I didn't find an implementation of the algorithm).