The b-bibranching Problem: TDI System, Packing, and Discrete Convexity
share
In this paper, 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 (1982), 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 (2018), is a generalization of the branching problem admitting higher indegree, i.e., 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 paper 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.
READ FULL TEXT