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 - Publisher Copyright:
© 2018 Association for Computing Machinery.
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 -