The b ‐bibranching problem: TDI system, packing, and discrete convexity

In this article, we introduce the b ‐bibranching problem in digraphs, which is a common generalization of the bibranching and b ‐branching problems. The bibranching problem, introduced by Schrijver, is a common generalization of the branching and bipartite edge cover problems. Previous results on bibranchings include polynomial algorithms, a linear programming formulation with total dual integrality, a packing theorem, and an M‐convex submodular flow formulation. The b ‐branching problem, recently introduced by Kakimura, Kamiyama, and Takazawa, is a generalization of the branching problem admitting higher indegree, that is, each vertex v can have indegree at most b ( v ). For b ‐branchings, a combinatorial algorithm, a linear programming formulation with total dual integrality, and a packing theorem for branchings are extended. A main contribution of this article is to extend those previous results on bibranchings and b ‐branchings to b ‐bibranchings. That is, we present a linear programming formulation with total dual integrality, a packing theorem, and an M‐convex submodular flow formulation for b ‐bibranchings. In particular, the linear program and M‐convex submodular flow formulations, respectively, imply polynomial algorithms for finding a shortest b ‐bibranching.