above lower bound of Erdös and Pósa9 on the number of
Let us repeat the procedure of eliminating a maximum
size set of edge-disjoint cycles. It follows from the lemma
that after O(log2 n) rounds, each component of the obtained
graph will have a constant difference between the number of
edges and vertices. At this stage, each component will have
only constantly many cycles. And so, in one more round we
will eliminate all cycles.
A different view on the third approach is by considering
the dimension of the perfect matching polytope. For a connected bipartite graph, where each of its edges belong to
some perfect matching, the perfect matching polytope has
dimension m − n + 1 [Lovász and Plummer,
20 Theorem 7. 6. 2].
Thus, the argument of this approach can also be viewed as
decreasing the dimension of the perfect matching polytope
by a fraction in each round and eventually reaching dimension zero, that is, just one perfect matching point.
4. FURTHER DEVELOPMENTS
After years of inactivity, our result inspired a series of follow-up works on parallel algorithms for perfect matching and the
Isolation Lemma. In one direction, our isolation approach
was generalized to the broader settings of matroid intersection and polytopes with totally unimodular faces, respectively.
15, 16 For these general settings, the right substitute for
cycles are integer vectors parallel to a face of the associated
polytope. Following our first approach, if one eliminates
vectors of length ≤2i, then there are only polynomially many
vectors of length ≤2i+ 1, in their respective settings (see15, 16
for details). It is not clear, however, if our second and third
approaches work in these settings.
In another direction, Svensson and Tarnawski24 generalized the isolation result to perfect matchings in general
graphs. They use the basic framework of our first approach as
the starting point, but they need to combine the technique
of eliminating cycles with a second parameter (
contractabil-ity) to control the progress in subsequent rounds.
The techniques developed by us and by Svensson and
Tarnawski were used by Anari and Vazirani3 to compute a
perfect matching in planar graphs in NC (see also22), which
also was a long-standing open problem. They show that the
sets to be contracted, odd sets of vertices that form a tight
cut in the LP-constraints, can be computed in NC. In a subsequent work, the NC algorithm was further generalized to
The Isolation Lemma has applications in many different
settings—in particular, in design of randomized algorithms.
The main open question that remains is for what other settings
can one derandomize the Isolation Lemma. We conjecture
that our isolation approach works for any family of sets whose
corresponding polytopes are described by 0/1 constraints.
We would like to thank Manindra Agrawal and Nitin Saxena
for their constant encouragement and very helpful discussions. We thank Arpita Korwar for discussions on some
other techniques used in this research, Jacobo Torán for
1. Agrawal, M., Hoang, T.M., Thierauf, T.
The polynomially bounded perfect
matching problem is in NC2. In 24th
International Symposium on Theoretical
Aspects of Computer Science (STACS),
volume 4393 of Lecture Notes in
Computer Science (Berlin Heidelberg,
2007). Springer, 489–499.
2. Alon, N., Hoory, S., Linial, N. The
Moore bound for irregular graphs.
Graphs Comb. 18, 1 (2002), 53–57.
3. Anari, N., Vazirani, V.V. Planar graph
perfect matching is in NC. Technical
Report arXiv:1709.07822, CoRR, 2017.
4. Berkowitz, S. J. On computing the
determinant in small parallel time using
a small number of processors. Inform.
Process. Lett. 18, 3 (1984), 147–150.
5. Dahlhaus, E., Karpinski, M. Matching
and multidimensional matching in
chordal and strongly chordal graphs.
Discrete Appl. Math. 84 (1998), 79–91.
6. Datta, S., Kulkarni, R., Roy, S.
Deterministically isolating a perfect
matching in bipartite planar graphs.
Theory Comput. Syst. 47 (2010),
7. Edmonds, J. Paths, trees, and owers.
Can. J. Math. 17 (1965), 449–467.
8. Eppstein, D., Vazirani, V.V. NC
algorithms for perfect matching
and maximum ow in one-crossing-minor-free graphs. Technical Report
arXiv:1802.00084, CoRR, 2018.
9. Erdös, P., Pósa, L. On the maximal
number of disjoint circuits of a graph.
Publ. Math. Debrecen 9 (1962), 3–12.
10. Fenner, S., Gurjar, R., Thierauf, T.
Bipartite Perfect Matching is in
quasi-NC. In Proceedings of the
48th ACM Symposium on the Theory
of Computing (S TOC) (Cambridge,
MA, USA, June 18–21, 2016).
arXiv:1601.06319; ECCC TR15-177.
11. Fenner, S., Gurjar, R., Thierauf, T.
Guest column: Parallel algorithms for
perfect matching. SIGACT News 48,
1 (Mar. 2017), 102–109.
12. Fredman, M.L., Komlós, J., Szemerédi, E.
Storing a sparse table with O( 1) worst
case access time. J. ACM,
31, 3 (June
13. Goldwasser, S., Grossman, O.
Bipartite perfect matching in
pseudo-deterministic NC. In
44th International Colloquium
on Automata, Languages, and
Programming (Warsaw, Poland,
July 10–14, 2017), ICALP 2017, 13,
14. Grigoriev, D., Karpinski, M. The
matching problem for bipartite
graphs with polynomially bounded
permanents is in NC (extended
abstract). In 28th Annual Symposium
on Foundations of Computer Science
(FOCS) (Los Angeles, California, USA,
October 27–29, 1987), 166–172.
15. Gurjar, R., Thierauf, T. Linear matroid
intersection is in quasi-NC. In
Proceedings of the 49th Annual ACM
SIGACT Symposium on Theory of
Computing (Montreal, QC, Canada, June
19–23, 2017), STOC 2017, 821–830.
16. Gurjar, R., Thierauf, T., Vishnoi, N.K.
Isolating a vertex via lattices: Polytopes
with totally unimodular faces. In 45th
International Colloquium on Automata,
Languages, and Programming (ICALP)
(Prague, Czech Republic, July 9–13,
2018), 74:1–74: 14.
17. Kane, D., Lovett, S., Rao, S. The
independence number of the birkhoff
polytope graph, and applications to
maximally recoverable codes. In
58th IEEE Annual Symposium on
Foundations of Computer Science
(Berkeley, CA, USA, October 15–17,
2017), FOCS 2017, 252–259.
18. Karp, R.M., Upfal, E., Wigderson, A.
Constructing a perfect matching is
in random NC. Combinatorica,
19. Lovász, L. On determinants,
matchings, and random algorithms.
In Fundamentals of Computation
Theory (Berlin/Wendisch-Rietz (GDR),
September 17–21, 1979), 565–574.
20. Lovász, L., Plummer, M.D. Matching
Theory. North-Holland mathematics
studies. Elsevier Science Ltd, 1986.
21. Mulmuley, K., Vazirani, U.V., Vazirani, V.V.
Matching is as easy as matrix inversion.
7 (1987), 105–113.
22. Sankowski, P. NC algorithms
for weighted planar perfect
matching and related problems.
In 45th International Colloquium
on Automata, Languages, and
Programming (ICALP) (Prague, Czech
Republic, July 9–13, 2018), 97:1–97: 16.
23. Subramanian, A. A polynomial bound
on the number of light cycles in an
undirected graph. Inform. Process.
Lett. 53, 4 (1995), 173–176.
24. Svensson, O., Tarnawski, J. The
matching problem in general graphs
is in quasi-NC. In 58th IEEE Annual
Symposium on Foundations of Computer
Science (Berkeley, CA, USA, October
15–17, 2017), FOCS 2017, 696–707.
25. Teo, C. P., Koh, K. M. The number of
shortest cycles and the chromatic
uniqueness of a graph. J. Graph
Theory 16, 1 (1992), 7–15.
26. Tewari, R., Vinodchandran, N. Green’s
theorem and isolation in planar graphs.
Inform. Comput. 215 (2012), 1–7.
discussions on the number of shortest cycles, and Nisheeth
Vishnoi for helpful comments.
Stephen Fenner ( firstname.lastname@example.org),
University of South Carolina, Columbia,
Rohit Gurjar (rohitgurjar0@gmail.
com), California Institute of Technology,
Pasadena, CA, USA.
Thomas Thierauf (thomas.
email@example.com), Aalen University,
© 2019 ACM 0001-0782/19/3 $15.00