Dynamic rank-maximal and popular matchings

We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph $$G=(\mathcal {A}\cup \mathcal {P},E)$$ G = ( A ∪ P , E ) , where $$\mathcal {A}$$ A denotes a set of applicants, $$\mathcal {P}$$ P is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on. We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple $$O(r(m+n))$$ O ( r ( m + n ) ) -time algorithm to update an existing rank-maximal matching under each of these changes. When $$r=o(n)$$ r = o ( n ) , this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al. (ACM Trans Algorithms 2(4):602–610, 2006), which takes time $$O(\min ((r+n,r\sqrt{n})m)$$ O ( min ( ( r + n , r n ) m ) . Our algorithm can also be used for maintaining a popular matching in the one-sided preference model in $$O(m+n)$$ O ( m + n ) time, whenever one exists.