TY - GEN

T1 - Fully dynamic maximal independent set with sublinear update time

AU - Assadi, Sepehr

AU - Schieber, Baruch

AU - Onak, Krzysztof

AU - Solomon, Shay

N1 - Funding Information:
Partially supported by NSF grant CCF-1617851.

PY - 2018/6/20

Y1 - 2018/6/20

N2 - A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{∆,m3/4}), where ∆ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(min{∆,m3/4}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

AB - A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{∆,m3/4}), where ∆ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(min{∆,m3/4}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

KW - Dynamic distributed algorithms

KW - Dynamic graph algorithms

KW - Maximal independent set

UR - http://www.scopus.com/inward/record.url?scp=85049793626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049793626&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188922

DO - 10.1145/3188745.3188922

M3 - Conference contribution

AN - SCOPUS:85049793626

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 431

EP - 444

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -