Abstract
Maximal independent set (MIS), maximal matching (MM), and (Delta+1)(vertex) coloring in graphs of maximum degree Delta are among the most prominent algorithmic graph theory problems. They are all solvable by a simple lineartime greedy algorithm and up until very recently this constituted the stateoftheart. In SODA 2019, Assadi, Chen, and Khanna gave a randomized algorithm for (Delta+1)coloring that runs in O~(n sqrt{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 sublineartime algorithm in general graphs. In this work, we dig deeper into the possibility of achieving sublineartime 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(n beta(G)) and O(n log{n} * beta(G)) time respectively on any nvertex graph G. We complement this positive result by observing that a simple extension of the lower bound of Assadi et al. implies that Omega(n beta(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.
Graphs with bounded neighborhood independence, already for constant beta = beta(G), constitute a rich family of possibly dense graphs, including line graphs, proper interval graphs, unitdisk graphs, clawfree graphs, and graphs of bounded growth. Our results suggest that even though MIS and MM do not admit sublineartime algorithms in general graphs, one can still solve both problems in sublinear time for a wide range of beta(G) << n.
Finally, by observing that the lower bound of Omega(n sqrt{n}) time for (Delta+1)coloring due to Assadi et al. applies to graphs of (small) constant neighborhood independence, we unveil an intriguing separation between the time complexity of MIS and MM, and that of (Delta+1)coloring: while the time complexity of MIS and MM is strictly higher than that of (Delta+1) coloring in general graphs, the exact opposite relation holds for graphs with small neighborhood independence.
BibTeX  Entry
@InProceedings{assadi_et_al:LIPIcs:2019:10593,
author = {Sepehr Assadi and Shay Solomon},
title = {{When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {17:117:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10593},
URN = {urn:nbn:de:0030drops105931},
doi = {10.4230/LIPIcs.ICALP.2019.17},
annote = {Keywords: Maximal Independent Set, Maximal Matching, SublinearTime Algorithms, Bounded Neighborhood Independence}
}
Keywords: 

Maximal Independent Set, Maximal Matching, SublinearTime Algorithms, Bounded Neighborhood Independence 
Collection: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Issue Date: 

2019 
Date of publication: 

04.07.2019 