Balanced bisubmodular systems and bidirected flows

For a nonempty finite set V let 3^V be the set of all the ordered pairs of disjoint subsets of V, i.e. 3^V = {(X,Y)|X,Y ⊆ V,X ∩ Y = ∅}. We define two operations, reduced union ⊔ and intersection ⊓, on 3^V as follows: for each (Xi,Yi) ∈ 3^V (i = 1,2) (X1,Y1) ⊔ (X2, Y2) = ((X1 ∪ X2) – (Y1 ∪ Y2), (Y1 ∪ Y2) – (X1 ∪ X2)), (X1,Y1) ⊓ (X2,Y2) = (X1 ∩ X2,Y1 ∩ Y2). Also, for a {⊔,⊓}-closed family ℱ ⊆ 3^V a function f : ℱ → R is called bisubmodular if for each (Xi,Yi) ∈ ℱ (i = 1,2) we have f(X1,Y1) + f(X2,Y2) ≥ f((X1,Y1) ⊔ (X2,Y2)) + f((X1,Y1) ⊓ (X2,Y2)). For a {⊔,⊓}-closed family ℱ ⊆ 3^V with (∅,∅) ∈ ℱ and a so-called bisubmodular function f : ℱ → R on ℱ with f(∅,∅) = 0, the pair (ℱ, f) is called a bisubmodular system on V. In this paper we consider two classes of bisubmodular systems which are closely related to base polyhedra. The first one is the class of balanced bisubmodular systems. We give a characterization of balanced bisubmodular systems and show that their associated polyhedra are the convex hulls of reflections of base polyhedra. The second one is that of cut functions of bidirected networks. It is shown that the polyhedron determined by the cut function of a bidirected network is the set of the boundaries of flows in the bidirected network and is a projection of a section of base polyhedron of boundaries of an associated ordinary network.