Reminder: This post contains 961 words
· 3 min read
· by Xianbin
This post is based on [1]. In lower bound of maximal matching, we show how to obtain a lower bound of maximal matching in distributed sketching model. Notice that since we consider it in “one-round” model, the major challenge is to show that each player will send enough messages to the referee.
In the following, we show how to prove a lower bound MIS in the distributed sketching model.
\(\textbf{Observation}\). If we ignore the public vertices in the instance \(G\) in lower bound of maximal matching, the remaining private nodes induces an induced matching.
The MIS is equal to MM!
So, it is enough to show that we can create such an instance, all public nodes are not in MIS.
How to do that?
We can create two copies of \(G\),i.e, \(H_L\) and \(H_R\), and connect all public vertices together. Once a public node is in MIS, there must be a case: all public nodes in \(H_L\) (or \(H_R\)) are not in MIS. It is done.
Reference
[1]. Assadi, S., Kol, G. and Oshman, R., 2020, July. Lower bounds for distributed sketching of maximal matchings and maximal independent sets. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 79-88).