Dynamic Matchings in Convex Bipartite Graphs

Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen and Irit Katriel

Abstract

We consider the problem of maintaining a maximum matching in a convex bipartite graph $G=(V,E)$ under a set of update operations which includes insertions and deletions of vertices and edges. It isnot hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in $O(\log^2{|V|})$ amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case $O(\min \{ k \log^2{|V|} + \log{|V|}, |V| \log{|V|}\})$ time, where $k$ is the number of update operations since the last query for the same pair of vertices was made. Also, we give an $O(\sqrt{|V|} \log^2{|V|})$-time amortized bound for this pair query.