Online matching games in bipartite expanders: Hall-type results and applications to non-blocking connectors

Abstract

The classical Hall Theorem shows the equivalence between \emph{offline} matching in bipartite graphs and a certain expansion property. We show that lossless expansion implies efficient online matching. Online matching is defined by the following game: an opponent switches on and off nodes on the left side and, at any moment, at most $K$ nodes may be on. Each time a node is turned on, it must be irrevocably matched with one of its neighbors. A bipartite graph has $e$-expansion up to $K$ if every set $S$ of at most $K$ left nodes has at least $e\#S$ neighbors. If all left nodes have degree $D$ and $e$ is close to $D$, then the graph is a lossless expander. We show that lossless expanders allow for a polynomial-time strategy in the above game, and, furthermore, a slight modification of such a graph allows a strategy running in time $O(D\log N)$, where $N$ is the number of left nodes. From this, improved non-blocking connectors are obtained. These are graphs with a set of input and a set of output nodes. In online fashion, requests of the form (input node, output node) are given, and each time, a path connecting the two nodes must be constructed that is vertex disjoint from paths constructed for previous requests. We obtain constant depth $N$-connectors of optimal size with efficient path-finding algorithms. For non-explicit connectors, the run time is poly$(\log N)$ and the size is optimal within poly($\log N)$ factor. For explicit connectors, both the runtime and optimality factor are $\exp (O({\log }^2\log N))$. Previous path-finding algorithms for such connectors were double-exponentially slower. In the companion papers~\cite{companion-DS} and~\cite{companion-construction}, we consider some variants of the above online matching game and present several applications to data structures and minimum descriptions.

arXiv commentWe have improved significantly some results, and found new applications of online matching. Therefore, we have split this project into 3 companion papers, of which this is one. The 3 companion papers can be read separately