Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings

Source abstract

The main result of this paper is motivated by the following two apparently unrelated graph optimization problems: (A) As an extension of Edmonds’ disjoint branchings theorem, characterize digraphs comprising k disjoint branchings B i each having a specified number μ i of arcs. (B) As an extension of Ryser’s maximum term rank formula, determine the largest possible matching number of simple bipartite graphs complying with degree-constraints. The solutions to these problems and to their generalizations will be obtained from a new min-max theorem on covering a supermodular function by a simple degree-constrained bipartite graph. A specific feature of the result is that its minimum cost extension is already NP-hard. Therefore classic polyhedral tools themselves definitely cannot be sufficient for solving the problem, even though they make some good service in our approach.