5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.