Teoria algorítmica de matroides

Abstract

The Matroid Matching problem consists in finding a maximum matching in a graph G such that the vertices touched by this matching form an independent set on a matroid M. This problem is a generalization of the Maximum Matching and Matroid Intersection problems. Although Matroid Matching is NP-complete, Lovász presented a polynomial algorithm and a min-max formula in the case where M is a linear matroid. In 2003, Szigeti presented a proof of Lovász’s min-max formula in the case where M is a graphic matroid, a subclass of linear matroids. Although simpler than Lovász’s proof, this proof is still reasonably complex and uses the formulas min-max for the Matroid Intersection and Matroid Union problems. The main result of this dissertation is a revised proof of Szigeti’s min-max formula for the Matroid Matching problem. To make a text self-contained and increase its accessibility, we present all the matroid base necessary for its understanding. This base starts with the basic definitions of matroids and goes through the demonstration of min-max formulas for Matroid Intersection and Matroid Union problems. Although it is not necessary for the proof of the main result, we contextualize the partial results by presenting applications of the min-max formula for Matroid Intersection and Matroid Union problems. For this, we show how they serve to prove characterizations known in the literature as common transversal, multicolored spanning tree, disjoint bases in a matroid, among others. In order to increase the scope of this text, we also present polynomial algorithms for these two problems.