Families of cuts with the MFMC-property (Q1082240): Difference between revisions

Let \({\mathcal F}\) be a family of nonempty subsets of a finite set E. Let a labelling \(\ell \in R^ E_+\) and a function \(f: {\mathcal F}\to R_+\) be given. For \(F\subseteq E\) let \(f(F)=\sum \{f(e):\) \(e\in F\}\). Then f is \(\ell\)-admissible if \(\sum (f(F):\) \(e\in F\in {\mathcal F})\leq \ell (e)\) for all \(e\in E\). The maximum of \(\ell \cdot f=\sum (f(F):\) \(F\in {\mathcal F}\}\) for \(\ell\)-admissible functions f on \({\mathcal F}\) is denoted by p(\({\mathcal F},\ell)\). A subset B of E meets \({\mathcal F}\) if \(B\cap F\neq \emptyset\) for all \(F\in {\mathcal F}\). The blocker b(\({\mathcal F})\) is the collection of minimal subsets of E meeting \({\mathcal F}\cdot {\mathcal F}\) is said to have the weak maximum flow-minimum cut (MFMC) property if p(\({\mathcal F},\ell)=\min \{\ell (B):\) \(B\in b({\mathcal F})\}\) for any \(\ell \in R^ E_+.\) It is known that a family \({\mathcal F}\) of cuts of a complete graph have the MFMC property if it is obtained from one of the three types of 'schemes' known as (i) an odd, (ii) a two-commodity, or (iii) a lattice scheme. In this paper it is shown that for a suitably restricted class of schemes, the family of cuts \({\mathcal F}\) has the MFMC property iff the scheme is of one of the above types.