## Michael Kapralov

I am a Herman Goldstine Postdoctoral Fellow at the IBM T. J. Watson Research Center in the Department of Business Analytics and Mathematical Sciences.

I completed my PhD at Stanford iCME, where I was advised by Ashish Goel. After graduating from Stanford I spent two years as a postdoc at the Theory of Computation Group at MIT CSAIL, working with Piotr Indyk.

E-mail: michael dot kapralov at gmail dot com

My research interests lie in theoretical computer science, in particular algorithm design. I enjoy working on classical combinatorial optimization problems as well as problems motivated by modern data models, such as streaming, sketching and online algorithms. More recent interests include sparse recovery and Fourier sampling.

Teaching:
Recent papers:
• Streaming Lower Bounds For Approximating MAX-CUT, to appear in SODA 2015
M. Kapralov, S. Khanna and M. Sudan
[Abstract]
We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem that uses only $O(\log n)$ space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows $\tilde{O}(n)$ space, then a near-optimal solution to the max cut value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor $2$). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space.
Our main result is that any streaming algorithm that breaks the $2$-approximation barrier requires $\tilde{\Omega}(\sqrt{n})$ space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or $\frac{1}{2}$-far from being bipartite, and establishing that $\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$ space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far from being bipartite. We also show that for any $\epsilon > 0$, any streaming algorithm that obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that $\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to the max cut value.
• Single Pass Spectral Sparsification in Dynamic Streams, to appear in FOCS 2014
Invited to the SICOMP special issue for FOCS 2014
M. Kapralov, YT Lee, C. Musco, C. Musco and A. Sidford
[Abstract]
We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph $G$, our algorithm maintains a randomized linear sketch of the incidence matrix of $G$ into dimension $O(\frac{1}{\epsilon^2}n\text{poly}(\log n))$. Using this sketch, at any point, the algorithm can output a $(1 \pm \epsilon)$ spectral sparsifier for $G$ with high probability.
While $O(\frac{1}{\epsilon^2} n \text{poly}(\log n))$ space algorithms are known for computing cut sparsifiers in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in insertion-only streams [KL11], prior to our work, the best known single pass algorithm for maintaining spectral sparsifiers in dynamic streams required sketches of dimension $\Omega(\frac{1}{\epsilon^2}n^{5/3})$ [AGM14].
To achieve our result, we show that, using a coarse sparsifier of $G$ and a linear sketch of $G$'s incidence matrix, it is possible to sample edges by effective resistance, obtaining a spectral sparsifier of arbitrary precision. Sampling from the sketch requires a novel application of $\ell_2/\ell_2$ sparse recovery, a natural extension of the $\ell_0$ methods used for cut sparsifiers in [AGM12b]. Recent work of [MP12] on row sampling for matrix approximation gives a recursive approach for obtaining the required coarse sparsifiers.
Under certain restrictions, our approach also extends to the problem of maintaining a spectral approximation for a general matrix $A^\top A$ given a stream of updates to rows in $A$.
• Sample-Optimal Fourier Sampling in Any Constant Dimension, to appear in FOCS 2014
P. Indyk and M. Kapralov
[Abstract]
We give an algorithm for $\ell_2/\ell_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of [DIPW] for non-adaptive algorithms up to constant factors for any $k\leq N^{1-\delta}$. The algorithm runs in $\tilde O(N)$ time. Our algorithm extends to higher dimensions, leading to sample complexity of $O_d(k\log N)$, which is optimal up to constant factors for any $d=O(1)$. These are the first sample optimal algorithms for these problems.
A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.
• Spanners and Sparsifiers in Dynamic Streams, PODC 2014
Invited to the special issue for PODC 2014 in Distributed Computing
M. Kapralov and D. Woodruff
[Abstract]
Linear sketching is a popular technique for computing in dynamic streams, where one needs to handle both insertions and deletions of elements. The underlying idea of taking randomized linear measurements of input data has been extremely successful in providing space-efficient algorithms for classical problems such as frequency moment estimation and computing heavy hitters, and was very recently shown to be a powerful technique for solving graph problems in dynamic streams [AGM'12]. Ideally, one would like to obtain algorithms that use one or a small constant number of passes over the data and a small amount of space (i.e. sketching dimension) to preserve some useful properties of the input graph presented as a sequence of edge insertions and edge deletions.
In this paper, we concentrate on the problem of constructing linear sketches of graphs that (approximately) preserve the spectral information of the graph in a few passes over the stream. We do so by giving the first sketch-based algorithm for constructing multiplicative graph spanners in only two passes over the stream. Our spanners use $\tilde{O}(n^{1+1/k})$ bits of space and have stretch $2^k$. While this stretch is larger than the conjectured optimal $2k-1$ for this amount of space, we show for an appropriate $k$ that it implies the first $2$-pass spectral sparsifier with $n^{1+o(1)}$ bits of space. Previous constructions of spectral sparsifiers in this model with a constant number of passes would require $n^{1+c}$ bits of space for a constant $c > 0$. We also give an algorithm for constructing spanners that provides an additive approximation to the shortest path metric using a single pass over the data stream, also achieving an essentially best possible space/approximation tradeoff.
• Approximating matching size from random streams, SODA 2014
M. Kapralov, S. Khanna and M. Sudan
[Abstract]
We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore $\tilde{O}(\sqrt{n})$ approximation with polylogarithmic space in an $n$ vertex graph and a constant approximation with $\Omega(n)$ space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in $n$.
Our algorithm is obtained by effecting a streaming implementation of a simple local'' algorithm that we design for this problem. The local algorithm produces a $O(k\cdot n^{1/k})$ approximation to the size of a maximum matching by exploring the radius $k$ neighborhoods of vertices, for any parameter $k$. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for $k = \Omega(\log n/\log\log n)$. Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.
• (Nearly) sample-optimal sparse Fourier transform, SODA 2014
P. Indyk, M. Kapralov and E. Price
[Abstract]
We consider the problem of computing a $k$-sparse approximation to the discrete Fourier transform of an $n$-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using $O(k \log n (\log\log n)^{O(1)})$ signal samples in time $O(k \log^2 n (\log\log n)^{O(1)})$, assuming that the entries of the signal are polynomially bounded. The sampling complexity improves over the recent bound of $O(k \log n \log (n/k))$ given in [HIKP12], and matches the lower bound of $\Omega(k \log (n/k)/\log \log n)$ from the same paper up to $\mbox{poly}(\log \log n)$ factors when $k=O(n^{1-\delta})$ for a constant $\delta>0$.
• Better bounds for matchings in the streaming model, SODA 2013
M. Kapralov
[Abstract]
In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input when $\tilde O(n)$ space is allowed, where $n$ is the number of vertices in the input graph. Two natural variants of this problem have been considered in the literature: (1) the edge arrival setting, where edges arrive in the stream and (2) the vertex arrival setting, where vertices on one side of the graph arrive in the stream together with all their incident edges. The latter setting has also been studied extensively in the context of online algorithms, where each arriving vertex has to either be matched irrevocably or discarded upon arrival.
In the online setting, the celebrated algorithm of Karp-Vazirani-Vazirani achieves a $1-1/e$ approximation by crucially using randomization (and using $\tilde O(n)$ space). Despite the fact that the streaming model is less restrictive in that the algorithm is not constrained to match vertices irrevocably upon arrival, the best known approximation in the streaming model with vertex arrivals and $\tilde O(n)$ space is the same factor of $1-1/e$.
Our main result in this paper shows that no (possibly randomized) single pass streaming algorithm constrained to use $\tilde O(n)$ space can achieve a better than $1-1/e$ approximation to maximum matching, even in the vertex arrival setting. This leads to the striking conclusion that no single pass streaming algorithm can get any advantage over online algorithms unless it uses significantly more than $\tilde O(n)$ space. Additionally, our bound yields the best known impossibility result for approximating matchings in the edge arrival model (improving upon the bound of $2/3$ proved by Goel at al[SODA'12]).
We also consider the problem of approximating matchings in multiple passes in the vertex arrival setting. We show that a simple fractional load balancing approach achieves approximation ratio $1-e^{-k}k^{k-1}/(k-1)!=1-\frac1{\sqrt{2\pi k}}+o(1/k)$ in $k$ passes using linear space. Thus, our algorithm achieves the best possible $1-1/e$ approximation in a single pass and improves upon the $1-O(\sqrt{\log\log k/k})$ approximation in $k$ passes due to Ahn and Guha[ICALP'11]. Additionally, our approach yields an efficient solution to the Gap-Existence problem considered by Charles et al[EC'10].
• On differentially private low rank approximation, SODA 2013
M. Kapralov and K. Talwar
[Abstract]
Low rank approximation is a fundamental computational primitive widely used in data analysis. In many applications the dataset that the algorithm operates on may contain sensitive information about contributing individuals (e.g. user/movie ratings in the Netflix challenge), motivating the need to design low rank approximation algorithms that preserve privacy of individual entries of the input matrix.
In this paper, we give a polynomial time algorithm that, given a privacy parameter $\epsilon>0$, for a symmetric matrix $A$, outputs an $\epsilon$-differentially approximation to the principal eigenvector of $A$, and then show how this algorithm can be used to obtain a differentially private rank-$k$ approximation. We also provide lower bounds showing that our utility/privacy tradeoff is close to best possible.
While there has been significant progress on this problem recently for a weaker notion of privacy, namely $(\epsilon, \delta)$-differential privacy [HR12, BBDS12], our result is the first to achieve $(\epsilon, 0)$-differential privacy guarantees with a near-optimal utility/privacy tradeoff in polynomial time.
• Online submodular welfare maximization: greedy is optimal, SODA 2013
M. Kapralov, I. Post and J. Vondrak
[Abstract]
We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless NP = RP. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i.i.d. items and valuations satisfying diminishing returns is (1-1/e)-competitive, which is optimal even for coverage valuations, unless NP=RP. For online budget-additive allocation, we prove that no algorithm can be 0.612-competitive with respect to a natural LP which has been used previously for this problem.
• Embedding paths into trees: VM placement to minimize congestion, ESA 2012
D. Dutta, M. Kapralov, I. Post, R. Shinde
[Abstract]
Modern cloud infrastructure providers allow customers to rent compute capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. Typical requests are in the form of a chain of VMs with an uplink bandwidth to the gateway node of the network (rooted path requests), and most data center architectures route network packets along a spanning tree of the physical network. VMs are instantiated inside servers which reside at the leaves of this network, leading to the following optimization problem: given a rooted tree network $T$ and a set of rooted path requests, find an embedding of the requests that minimize link congestion.
Our main result is an algorithm that given a rooted tree network $T$ with $n$ leaves and set of weighted rooted path requests, embeds a $1-\epsilon$ fraction of the requests with congestion at most $poly(\log{n}, \log \theta ,\epsilon^{-1})\cdot\text{OPT}$ (approximation is necessary since the problem is NP-hard). Here $\text{OPT}$ is the congestion of the optimal embedding and $\theta$ is the ratio of the maximum to minimum weights of the path requests. We also obtain a $O(H\log n/\epsilon^2)$ approximation if node capacities can be augmented by a $1+\epsilon$ factor (here $H$ is the height of the tree). Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of subtrees of $T$ with a given number of leaves that may be of independent interest.
• NNS lower bounds via metric expansion for $l_\infty$ and EMD, ICALP 2012
M. Kapralov and R. Panigrahy
[Abstract]
We give new lower bounds for randomized NNS data structures in the cell probe model based on robust metric expansion for two metric spaces: $l_\infty$ and Earth Mover Distance (EMD) in high dimensions. In particular, our results imply stronger non-embedability for these metric spaces into $l_1$. The main components of our approach are a strengthening of the isoperimetric inequality for the distribution on $l_\infty$ introduced by Andoni et al [FOCS'08] and a robust isoperimetric inequality for EMD on quotients of the boolean hypercube.
• Spectral sparsification via random spanners, ITCS 2012
M. Kapralov and R. Panigrahy
[Abstract]
In this paper we introduce a new notion of distance between nodes in a graph that we refer to as robust connectivity . Robust connectivity between a pair of nodes $u$ and $v$ is parameterized by a threshold $\kappa$ and intuitively captures the number of paths between $u$ and $v$ of length at most $\kappa$. Using this new notion of distances, we show that any black box algorithm for constructing a spanner can be used to construct a spectral sparsifier. We show that given an undirected weighted graph $G$, simply taking the union of spanners of a few (polylogarithmically many) random subgraphs of $G$ obtained by sampling edges at different probabilities, after appropriate weighting, yields a spectral sparsifier of $G$. We show how this be done in $\tilde O(m)$ time, producing a sparsifier with $\tilde O(n/\epsilon^2)$ edges. While the cut sparsifiers of Benczur and Karger are based on weighting edges according to (inverse) strong connectivity, and the spectral sparsifiers are based on resistance, our method weights edges using the robust connectivity measure. The main property that we use is that this new measure is always greater than the resistance when scaled by a factor of $O(\kappa)$ ($\kappa$ is chosen to be $O(\log n)$), but, just like resistance and connectivity, has a bounded sum, i.e. $\tilde O(n)$, over all the edges of the graph.
• On the communication and streaming complexity of maximum bipartite matching, SODA 2012
A. Goel, M. Kapralov and S. Khanna
[Abstract]
Consider the following communication problem. Alice holds a graph $G_A=(P, Q, E_A)$ and Bob holds a graph $G_B=(P, Q, E_B)$, where $|P|=|Q|=n$. Alice is allowed to send Bob a message $m$ that depends only on the graph $G_A$. Bob must then output a matching $M\subseteq E_A\cup E_B$. What is the minimum message size of the message $m$ that Alice sends to Bob that allows Bob to recover a matching of size at least $(1-\epsilon)$ times the maximum matching in $G_A\cup G_B$? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a $1-\epsilon$-approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a $\frac{1}{2}$-approximation was known for both these problems.
In order to study these questions, we introduce the concept of an $\epsilon$-matching cover of a bipartite graph $G$, which is a sparse subgraph of the original graph that preserves the size of maximum matching between every subset of vertices to within an additive $\epsilon n$ error. We give a polynomial time construction of a $\frac{1}{2}$-matching cover of size $O(n)$ with some crucial additional properties, thereby showing that Alice and Bob can achieve a $\frac{2}{3}$-approximation with a message of size $O(n)$. While we do not provide bounds on the size of $\epsilon$-matching covers for $\epsilon<1/2$, we prove that in general, the size of the smallest $\epsilon$-matching cover of a graph $G$ on $n$ vertices is essentially equal to the size of the largest so-called $\epsilon$-Ruzsa Szemeredi graph on $n$ vertices. We use this connection to show that for any $\delta>0$, a $(\frac{2}{3}+\delta)$-approximation requires a communication complexity of $n^{1+\Omega(1/\log\log n)}$.
We also consider the natural restrictingon of the problem in which $G_A$ and $G_B$ are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a $\frac{3}{4}$-approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation.
Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated $(1- \frac{1}{e})$-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming $(1-\frac{1}{e})$-approximation algorithm using $O(n)$ space for this setting.
• Prediction strategies without loss, NIPS 2011
M. Kapralov and R. Panigrahy
[Abstract]
Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say predict 0' or predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. For a sequence of length $T$ our algorithm has regret $5\epsilon T$ and loss $2\sqrt{T}e^{-\epsilon^2 T}$ in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors.
The algorithm extends to the general setting of $N$ experts, yielding essentially zero loss with respect to the special expert and optimal loss/regret tradeoff, improving upon the results of Even-Dar et al (COLT'07) and settling the main question left open in their paper.
The strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal regret bounds with respect to $k$-shifting optima, i.e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for any window of size $n$ the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon, while maintaining the essentially zero loss property.
• Multiplicative approximations of random walk transition probabilities, APPROX 2011
M. Kapralov and R. Panigrahy
[Abstract]
We study the space and time complexity of approximating distributions of $l$-step random walks in simple (possibly directed) graphs $G$. While very efficient algorithms for obtaining additive $\epsilon$-approximations have been developed in the literature, no non-trivial results with multiplicative guarantees are known, and obtaining such approximations is the main focus of this paper. Specifically, we ask the following question: given a bound $S$ on the space used, what is the minimum threshold $t>0$ such that $l$-step transition probabilities for all pairs $u, v\in V$ such that $P_{uv}^l\geq t$ can be approximated within a $1\pm \epsilon$ factor? How fast can an approximation be obtained?
We show that the following surprising behavior occurs. When the bound on the space is $S=o(n^2/d)$, where $d$ is the minimum out-degree of $G$, no approximation can be achieved for non-trivial values of the threshold $t$. However, if an extra factor of $s$ space is allowed, i.e. $S=\tilde \Omega(sn^2/d)$ space, then the threshold $t$ is exponentially small in the length of the walk $l$ and even very small transition probabilities can be approximated up to a $1\pm \epsilon$ factor. One instantiation of these guarantees is as follows: any almost regular directed graph can be represented in $\tilde O(l n^{3/2+\epsilon})$ space such that all probabilities larger than $n^{-10}$ can be approximated within a $(1\pm \epsilon)$ factor as long as $l\geq 40/\epsilon^2$. Moreover, we show how to estimate of such probabilities faster than matrix multiplication time.
For undirected graphs, we also give small space oracles for estimating $P^l_{uv}$ using a notion of bicriteria approximation based on approximate distance oracles of Thorup and Zwick [STOC'01].
• Improved bounds for online stochastic matching, ESA 2010
B. Bahmani and M. Kapralov
[Abstract]
We study the online stochastic matching problem in a form motivated by Internet display advertisement. Recently, Feldman et al. gave an algorithm that achieves $0.6702$ competitive ratio, thus breaking through the $1-1/e$ barrier. One of the questions left open in their work is to obtain a better competitive ratio by generalizing their two suggested matchings (TSM) algorithm to $d$-suggested matchings ($d$-SM).
We show that the best competitive ratio that can be obtained with the static analysis used in the $d$-SM algorithm is upper bounded by $0.76$, even for the special case of $d$-regular graphs, thus suggesting that a dynamic analysis may be needed to improve the competitive ratio significantly. We make the first step in this direction by showing that the RANDOM algorithm, which assigns an impression to a randomly chosen eligible advertiser, achieves $1-e^{-d}d^d/d!=1-O(1/\sqrt{d})$ competitive ratio for $d$-regular graphs, which converges to $1$ as $d$ increases. On the hardness side, we improve the upper bound of $0.989$ on the competitive ratio of any online algorithm obtained by Feldman et al. to $1-1/(e+e^2)\approx 0.902$. Finally, we show how to modify the TSM algorithm to obtain an improved $0.699$ approximation for general bipartite graphs.
• Perfect matchings in O(n log n) time in regular bipartite graphs, STOC 2010 (invited to SICOMP special issue for STOC 2010 papers)
A. Goel, M. Kapralov and S. Khanna
[Abstract]
In this paper we consider the well-studied problem of finding a perfect matching in a $d$-regular bipartite graph on $2n$ nodes with $m=nd$ edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time $O(m\sqrt{n})$. In regular bipartite graphs, however, a matching is known to be computable in $O(m)$ time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the $O(m)$ time algorithm was improved first to $\tilde O\left(\min\{m, n^{2.5}/d\}\right)$ and then to $\tilde O\left(\min\{m, n^2/d\}\right)$. It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect matching in a $d$-regular graph and runs in $O(n\log n)$ time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time $O(n\log^2 n)$, with $O(m)$ pre-processing time; this gives a simple $O(m+mn\log^2 n)$ time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix.
We show that randomization is crucial for obtaining $o(nd)$ time algorithms by establishing an $\Omega(nd)$ lower bound for any deterministic algorithm. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes $o(n\log n)$ time with high probability.
• Perfect matchings in Õ(n1.5) time in regular bipartite graphs, 2009, accepted to Combinatorica
A. Goel, M. Kapralov and S. Khanna
[Abstract]
We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m \sqrt{n})$ time, in regular bipartite graphs, a perfect matching is known to be computable in $O(m)$ time. Very recently, the $O(m)$ bound was improved to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$ expected time, an expression that is bounded by $\tilde{O}(n^{1.75})$. In this paper, we further improve this result by giving an $O(\min\{m, \frac{n^2\ln^3 n}{d}\})$ expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of $n$ alone, the algorithm takes expected time $O((n\ln n)^{1.5})$.
To obtain this result, we design and analyze a two-stage sampling scheme that reduces the problem of finding a perfect matching in a regular bipartite graph to the same problem on a subsampled bipartite graph with $O(n\ln n)$ edges. The first-stage is a sub-linear time uniform sampling that reduces the size of the input graph while maintaining certain structural properties of the original graph. The second-stage is a non-uniform sampling that takes linear-time (on the reduced graph) and outputs a graph with $O(n\ln n)$ edges, while preserving a matching with high probability. This matching is then recovered using the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karp also gives us an $\tilde{O}(n^{1.5})$ running time, we present a tighter analysis for our special case that results in the stronger $\tilde{O}(\min\{m, \frac{n^2}{d} \})$ time mentioned earlier.
Our proof of correctness of this sampling scheme uses a new correspondence theorem between cuts and Hall's theorem witnesses'' for a perfect matching in a bipartite graph that we prove. We believe this theorem may be of independent interest; as another example application, we show that a perfect matching in the support of an $n \times n$ doubly stochastic matrix with $m$ non-zero entries can be found in expected time $\tilde{O}(m + n^{1.5})$.
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to König's work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(\min\{m, \frac{n^{2.5}\ln n}{d}\})$; this minimum can never be larger than $O(n^{1.75}\sqrt{\ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(m\sqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $\ln^2 n$).