FOCS 2019 · 60th Annual IEEE Symposium on Foundations of Computer Science, Baltimore, MD, USA, November 2019 · doi:10.1109/FOCS.2019.00037
FOCS 2019 Best Paper Award
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in
However, the dependency on
We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in
As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in
2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 481–497, IEEE, Piscataway, 2019
ISBN 978-1-7281-4952-3