2016/08/19 by Kristóf Bérczi, András Frank, Bérczi, Kristóf +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1608.05722
The main result of the paper is motivated by the following two, apparently\nunrelated graph optimization problems: (A) as an extension of Edmonds' disjoint\nbranchings theorem, characterize digraphs comprising k disjoint branchings\nBi each having a specified number \μ i of arcs, (B) as an extension of\nRyser's maximum term rank formula, determine the largest possible matching\nnumber of simple bipartite graphs complying with degree-constraints. The\nsolutions to these problems and to their generalizations will be obtained from\na new min-max theorem on covering a supermodular function by a simple\ndegree-constrained bipartite graph. A specific feature of the result is that\nits minimum cost extension is already NP-complete. Therefore classic polyhedral\ntools themselves definitely cannot be sufficient for solving the problem, even\nthough they make some good service in our approach.\n