Finding small node sets that can not be avoided on paths from source to sink

Question

In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. <10 for example) set S of nodes such that every possible path from the starting node to the ending node contains at least one member of set S. The graph may have loops. This may be NP hard. Is there an approximate method to find one or several such S from the graph? Enumerating and testing every candidate seems not work. thanks.

Answer 1

Finding the smallest number of edges instead of vertices is the famous Minimum Cut problem which can be solved using any of the Max-Flow-Min-Cut algorithms. Picking vertices is a specific case of the generalised max-flow-min-cut theorem and similar algorithms can be used to solve it. In any case, it can be formulated as a linear program with polynomial complexity, which can be solved in polynomial time using any of the LP-solvers.