Persistency in combinatorial optimization problems on matroids (Q5936456)

Algorithms on matroids to find maximum weight bases or to solve the cardinality intersection problem of two matroids are analyzed to obtain a persistency partition of the elements into 1-persistent elements, which belong to all optimal solutions, 0-persistent ones which do not belong to any optimal solution, and non-persistent elements which belong to some, but not all optimal solutions. As an application, the persistency of edges of a bipartite graph with respect to maximum cardinality matching is characterized.