Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

DOI10.1137/1.9781611975482.116MaRDI QIDQ5236302zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.10051

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et.al. STOC'18]. The algorithm is deterministic and its update time is $O(m^{3/4})$, where $m$ is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of $O(m^{2/3})$ and $O(m^{2/3}sqrtlogm)$, respectively. Du and Zhang also gave a randomized algorithm with update time $widetildeO(sqrtm)$. Moreover, they provided some partial (conditional) hardness results hinting that update time of $m^{1/2-epsilon}$, and in particular $n^{1-epsilon}$ for $n$-vertex dense graphs, is a natural barrier for this problem for any constant $epsilon>0$, for both deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an $widetildeO(sqrtn)$ expected amortized update time algorithm. We also show that a simpler variant of our algorithm can already achieve an $widetildeO(m^{1/3})$ expected amortized update time, which results in an improved performance over our $widetildeO(sqrtn)$ update time algorithm for sufficiently sparse graphs, and breaks the $m^{1/2}$ barrier of Du and Zhang for all values of $m$.

Recommendations

• Fully dynamic maximal independent set with sublinear update time
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• scientific article; zbMATH DE number 1522948
• Fully dynamic maximal matching in O( n) update time
• A bottom-up method and fast algorithms for Max Independent Set
• Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Fully dynamic maximal matching in O( n) update time (corrected version)

Cited in

(13)

• Fully dynamic MIS in uniformly sparse graphs
• Fully dynamic MIS in uniformly sparse graphs
• Dominating sets and connected dominating sets in dynamic graphs
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Distributed detection of cliques in dynamic networks
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Fully dynamic maximal independent set with sublinear update time
• Optimal dynamic distributed MIS
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• Fast deterministic algorithms for highly-dynamic networks
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• Massively parallel computation in a heterogeneous regime
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs

This page was built for publication: Fully Dynamic Maximal Independent Set with Sublinear in n Update Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236302)