  The shortest bibranching problem is a common generalization of the
minimum-weight edge cover problem in bipartite graphs and the minimum-weight
arborescence problem in directed graphs. For the shortest bibranching problem,
an efficient primal-dual algorithm is given by Keijsper and Pendavingh (1998),
and the tractability of the problem is ascribed to total dual integrality in a
linear programming formulation by Schrijver (1982). Another view on the
tractability of this problem is afforded by a valuated matroid intersection
formulation by Takazawa (2012). In the present paper, we discuss the
relationship between these two formulations for the shortest bibranching
problem. We first demonstrate that the valuated matroid intersection
formulation can be derived from the linear programming formulation through the
Benders decomposition, where integrality is preserved in the decomposition
process and the resulting convex programming is endowed with discrete
convexity. We then show how a pair of primal and dual optimal solutions of one
formulation is constructed from that of the other formulation, thereby
providing a connection between polyhedral combinatorics and discrete convex
analysis.
