Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings

Bérczi, Kristóf and Frank, András (2018) Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings. MATHEMATICS OF OPERATIONS RESEARCH, 43 (3). pp. 726-753. ISSN 0364-765X

Preview

Text 1608.05722.pdf Download (714kB) | Preview

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 mu(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.

Actions (login required)

Edit Item