14
$\begingroup$

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$?


I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\textsf{NL}$:

Bipartite Perfect Matching (BPM)
Input: bipartite $2n$-vertex graph $G$
Question: does $G$ contain a matching with $n$ edges?

Maximum Bipartite Matching is the version where the required size of a matching is given as part of the input. By Chandra-Stockmeyer-Vishkin, this is equivalent to BPM via $\textsf{AC}^0$-reductions, and these problems are hard for $\textsf{NL}$ via $\textsf{AC}^0$-reductions.

Recall the following sequence of inclusions (see the Zoo): $$\textsf{L} \subseteq \textsf{UL} \subseteq \textsf{NL} \subseteq \textsf{NC}^2 \subseteq \textsf{RNC}^2.$$

Looking at a more general problem, maximum matching for general graphs is in $\textsf{RNC}^2$, by Mulmuley-Vazirani-Vazirani (preprint), and according to Allender-Reinhardt-Zhou this problem was (in 1999) not known to be in NL. The latter paper also shows that BPM is in a nonuniform version of $\textsf{SPL}$, but $\textsf{SPL}$ is not known to be comparable to $\textsf{NL}$. (The Zoo also claims that BPM is in $\textsf{coRNC}$ by Karloff, although it is not obvious to me how this follows from the results in Karloff's paper.)

All of the usual approaches to finding a maximum bipartite matching are polynomial-time. Moreover, these algorithms have polynomial time bounds of quite low degree. In particular, an $O(n^{2.5})$ time upper bound follows from the reduction of Hopcroft-Karp and Karzanov to maximum flow. So it is not impossible that BPM (and perhaps even maximum matching) is in $\textsf{NL}$.

However, all the approaches I've looked at seem to be rather space-intensive. The usual algorithms essentially keep track of subsets of the vertices, and therefore seem to require something like $\Omega(n)$ bits (although proving such a bound rigorously seems likely to be difficult).

Looking at a more specific problem, if the input graphs are further restricted to be planar as well as bipartite, then Planar BPM is in $\textsf{UL}$ and hence $\textsf{NL}$, by Datta-Gopalan-Kulkarni-Tewari.

So BPM is $\textsf{NL}$-hard, but is in some complexity classes "not much larger than" $\textsf{NL}$, and is in $\textsf{NL}$ for restricted classes of bipartite graphs. It therefore seems reasonable to ask: if $\text{BPM} \not\in\textsf{NL}$, would anything interesting follow?

$\endgroup$
  • 2
    $\begingroup$ btw, the "proof" showing Planar BPM in UL from DGKT is buggy. The part of the proof that shows it is in NL is however correct. $\endgroup$ – SamiD May 17 '16 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.