Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

We study the following characterization problem. Given a set $T$ of terminals and a $(2^{\mathrm{\mid }T\mathrm{\mid }}-2)$-dimensional vector $\pi$ whose coordinates are indexed by proper subsets of $T$, is there a graph $G$ that contains $T$, such that for all subsets $\mathrm{\varnothing }⊊S⊊T$, ${\pi }_S$ equals the value of the min-cut in $G$ separating $S$ from $T\setminus S$? The only known necessary conditions are submodularity and a special class of linear inequalities given by Chaudhuri, Subrahmanyam, Wagner and Zaroliagis. Our main result is a new class of linear inequalities concerning laminar families, that generalize all previous ones. Using our new class of inequalities, we can generalize Karger’s approximate min-cut counting result to graphs with terminals.