P-SLOCAL-Completeness of Maximum Independent Set Approximation
arXiv:1907.10499
Abstract
We prove that the maximum independent set approximation problem with polylogarithmic approximation factor is P-SLOCAL-complete. Thus an efficient algorithm for the maximum independent set approximation in the LOCAL model implies efficient algorithms for many problems in the LOCAL model including the computation of (polylog n, polylog n) network decompositions.
added author's name. Please note the breakthrough: arXiv:1907.10937