Dynamic popular matchings with two-sided preference lists

Abstract

Popular matching is a matching that no majority vote can force a migration to another matching. Given a bipartite graph $G = (\mathcal{A} \cup \mathcal{B}, E)$ where each vertex has a strict order of preference on its neighbors and a popular matching $\mathcal{M}$ of $G$, we propose two dynamic algorithms that maintains the popular matching when a vertex is added or deleted, and when a vertex changes its preference list. We also prove that the lower bound of the dynamic popular matching problem is linear. The worst-case time complexity of our first algorithm is $O(d*(n+m))$, where $n$ is the number of vertices, $m$ is the number of edges, and $d$ is the degree of the vertex that is involved in the graph change. The second algorithm runs in $O(n+m)$. It is the first attempt to extend the two-sided popular matching problem to the dynamic environment.