Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions
Yi‐Jun Chang, Hsin-Hao Su · 2022
Many combinatorial optimization problems, including maximum weighted matching and maximum independent set, can be approximated within (1 ± ε) factors in poly(log n, 1/ε) rounds in the LOCAL model via network decompositions [Ghaffari, Kuhn, and Maus, STOC 2018]. These approaches, however, require sending messages of unlimited size, so they do not extend to the more realistic CONGEST model, which restricts the message size to be O(log n) bits. For example, despite the long line of research devoted to the distributed matching problem, it still remains a major open problem whether an (1-ε)-approximate maximum weighted matching can be computed in poly(log n, 1/ε) rounds in the CONGEST model.