I am working on a bipartite matching problem where I need to solve an initial graph and then solve multiple variants of the graph where different nodes have been removed. The goal is to solve all of the variants as quickly as possible, so I would like to use the information gained from solving the original graph to solve the variants faster.
I have experience solving linear programming problems with the simplex method, which benefits from having an initial guess for the solution, but I am new to bipartite matching algorithms.
Is there a bipartite matching algorithm that can utilize an initial guess to speed up the solver?
@sascha's mention of decremental bipartite matching should be useful; another possibly useful candidate for search keywords would be "fully dynamic maximum mathing".
At the end of the day, what works best will depend on what exactly is removed; the algorithms will take whatever knowledge about the problem structure you might have.
But, maybe your problem is so that an offline algorithm is good enough: If G = (V, E) is the bipartite graph you start with, and M a matching of G, and if G' = (V', E') is the graph obtained by removing some of the vertices, so that E' is what you get by removing from E all edges incident to vertices in V \ V', then clearly M ∩ E' is a (not necessarily maximum) matching of G', and you're looking to extend that. The most common maximum matching algorithms work by extending existing matchings (primal feasible solutions if you like); this includes those based on augmenting path search, so you could take one of those with your restricted matching as an input, and maybe be good to go. A concrete classical example that's also easy to implement is the Hopcroft–Karp algorithm.