Supermodularity in unweighted graph optimization I: Branchings and matchings

Kristóf Bérczi, András Frank


The main result of the 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-complete and therefore classical polyhedral tools do not help.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s},
TITLE = {Supermodularity in unweighted graph optimization I: Branchings and matchings},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-09}

Last modification: 29.12.2020. Please email your comments to Tamás Király!