Given a digraph $ G = (V,A)$ with a source $ s \in V$ and a sink $ t \in V$ , I need to adapt the graph to known if a pair of vertices $ u \in V$ and $ v \in V$ belongs to the min-cut $ S$ between $ s$ and $ t$ . That is, a new vertex $ a$ belongs to the min-cut $ S$ if and only if $ u \in S$ and $ v \in S$ . This new vertex must preserve the original max-flow from $ s$ to $ t$ . I tried creating new arcs $ (u,a)$ and $ (a,v)$ with infinity capacities, but while $ a$ belongs to $ S$ when $ u \in S$ , this immediately forces $ v$ to belong to $ S$ also, which is not necessarily true if the max-flow was computed in the original graph $ G$ . So, is there a way to force a new node to be in the min-cut set $ S$ if a pair of vertices belongs to $ S$ ?