Packing and covering of crossing families of cuts

The author's summary: Let \({\mathcal C}\) be a crossing family of subsets of the finite set V (i.e., if T,\(U\in {\mathcal C}\) and \(T\cap U\neq \emptyset\). \(T\cup U\neq V\), then \(T\cap U\in {\mathcal C}\) and \(T\cup U\in {\mathcal C})\). If \(D=(V,A)\) is a directed graph on V, then a cut induced by \({\mathcal C}\) is the set of arcs entering some set in \({\mathcal C}\). A covering for \({\mathcal C}\) is a set of arcs entering each set in \({\mathcal C}\), i.e., intersecting all cuts induced by \({\mathcal C}\). It is shown that the following three conditions are equivalent for any given crossing family \({\mathcal C}:\) (P1) For every directed graph \(D=(V,A)\), the minimum cardinality of a cut induced by \({\mathcal C}\) is equal to the maximum number of pairwise disjoint coverings for \({\mathcal C}.\) (P2) For every directed graph \(D=(V,A)\), and for every length function l: \(A\to {\mathbb{Z}}\), the minimum length of a covering for \({\mathcal C}\) is equal to the maximum number t of cuts \(C_ 1,...,C_ t\) induced by \({\mathcal C}\) (repetition allowed) such that no arc a is in more than l(a) of these cuts. (P3) \(\emptyset \in {\mathcal C}\), or \(V\in {\mathcal C}\), or there are no \(V_ 1\), \(V_ 2\), \(V_ 3\), \(V_ 4\), \(V_ 5\) in \({\mathcal C}\) such that \(V_ 1\subseteq V_ 2\cap V_ 3\), \(V_ 2\cup V_ 3=V\), \(V_ 2\cup V_ 4\subseteq V_ 5\), \(V_ 3\cap V_ 4=\emptyset.\) Directed graphs are allowed to have parallel arcs, so that (P1) is equivalent to its capacity version. (P1) and (P2) assert that certain hypergraphs, as well as their blockers, have the \({\mathbb{Z}}_+\)-max-flow min-cut property. The equivalence of (P1), (P2), and (P3) implies Menger's theorem, the König-Egervary theorem, the König-Gupta edge- colouring theorem for bipartite graphs, Fulkerson's optimum branching theorem, Edmonds' disjoint branching theorem, and theorems of Frank, Feofiloff and Younger, and the present author.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Packing and covering of crossing families of cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q789399)