When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time

Maximal independent set (MIS), maximal matching (MM), and $(Delta+1)$-coloring in graphs of maximum degree $Delta$ are among the most prominent algorithmic graph theory problems. They are all solvable by a simple linear-time greedy algorithm and up until very recently this constituted the state-of-the-art. In SODA 2019, Assadi, Chen, and Khanna gave a randomized algorithm for $(Delta+1)$-coloring that runs in $widetilde{O}(nsqrt{n})$ time, which even for moderately dense graphs is sublinear in the input size. The work of Assadi et al. however contained a spoiler for MIS and MM: neither problems provably admits a sublinear-time algorithm in general graphs. In this work, we dig deeper into the possibility of achieving sublinear-time algorithms for MIS and MM. The neighborhood independence number of a graph $G$, denoted by $beta(G)$, is the size of the largest independent set in the neighborhood of any vertex. We identify $beta(G)$ as the ``right parameter to measure the runtime of MIS and MM algorithms: Although graphs of bounded neighborhood independence may be very dense (clique is one example), we prove that carefully chosen variants of greedy algorithms for MIS and MM run in $O(nbeta(G))$ and $O(nlog{n}cdotbeta(G))$ time respectively on any $n$-vertex graph $G$. We complement this positive result by observing that a simple extension of the lower bound of Assadi et.al. implies that $Omega(nbeta(G))$ time is also necessary for any algorithm to either problem for all values of $beta(G)$ from $1$ to $Theta(n)$. We note that our algorithm for MIS is deterministic while for MM we use randomization which we prove is unavoidable: any deterministic algorithm for MM requires $Omega(n^2)$ time even for $beta(G) = 2$.