On adaptive algorithms for maximum matching In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this problem, due to Micali and Vazirani, runs in time mathcalO(sqrtnm) and stands unbeaten since 1980. It is complemented by faster, often lineartime, algorithms for various special graph classes. Moreover, there are fast parameterized algorithms, e.g., time mathcalO(kmlog n) relative to treewidth k, which outperform mathcalO(sqrtnm) when the parameter is sufficiently small.  :80,show that the MicaliVazirani algorithm, and in fact any algorithm following the phase framework of Hopcroft and Karp, is adaptive to beneficial input structure. We exhibit several graph classes for which such algorithms run in linear time mathcalO(nm). More strongly, we :80,show that they run in time mathcalO(sqrtkm) for graphs that are k vertex deletions away from any of several such classes, without explicitly computing an optimal or approximate deletion set; before, most such bounds were at least Omega(km). Thus, any phasebased matching algorithm with lineartime phases obliviously interpolates between linear time for kmathcalO(1) and the worst case of mathcalO(sqrtnm) when kTheta(n). We complement our findings by proving that the phase framework by itself still allows Omega(sqrtn) phases, and hence time Omega(sqrtnm), even on paths, cographs, and bipartite chain graphs.

Iterative Graph Alignment via Supermodular Approximation Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NPxe2x80x93hard in the worstcase, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this paper, we approach the task of designing an efficient polynomialtime approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorizationmaximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically nondecreasing objective value while always adhering to the combinatorial matching constraints. Experiments on realworld data demonstrate the empirical effectiveness of the algorithm relative to the prevailing stateoftheart.