Premium
The b ‐bibranching problem: TDI system, packing, and discrete convexity
Author(s) -
Takazawa Kenjiro
Publication year - 2022
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22035
Subject(s) - submodular set function , mathematics , combinatorics , convexity , linear programming , generalization , regular polygon , flow network , packing problems , vertex (graph theory) , discrete mathematics , time complexity , mathematical optimization , graph , mathematical analysis , geometry , financial economics , economics
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.