Flow trees for vertex-capacitated networks

Given a graph G=(V,E)G=(V,E) with a cost function c(S)⩾0∀S⊆V, we want to represent all possible min-cut values between pairs of vertices ii and jj. We consider also the special case with an additive cost cc where there are vertex capacities c(v)⩾0c(v)⩾0∀v∈V∀v∈V, and for a subset S⊆VS⊆V, c(S)=∑v∈Sc(v)c(S)=∑v∈Sc(v). We consider two variants of cuts: in the first one, separation  , {i}{i} and {j}{j} are feasible cuts that disconnect ii and jj. In the second variant, vertex-cut  , a cut-set that disconnects ii from jj does not include ii or jj. We consider both variants for undirected and directed graphs. We prove that there is a flow-tree for separations in undirected graphs. We also show that a compact representation does not exist for vertex-cuts in undirected graphs, even with additive costs. For directed graphs, a compact representation of the cut-values does not exist even with additive costs, for neither the separation nor the vertex-cut cases.