When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
复制标题
当最大独立集和最大匹配算法在亚线性时间内运行时
DOI：
10.4230/lipics.icalp.2019.17
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Shay Solomon
极大独立集（MIS）、极大匹配（MM）和(Delta+1)-（顶点）上色是最大阶Delta图中最突出的算法图论问题。它们都可以通过一个简单的线性时间贪婪算法来求解，直到最近，这都是最先进的。在SODA 2019中，Assadi、Chen和Khanna给出了一种（Delta+1）着色的随机算法，该算法在O~（n sqrt{n}）时间内运行，即使对于中等密度的图，其输入大小也是次线性的。然而，Assadi等人的工作包含了MIS和MM的剧透：在一般图中，这两个问题都不能证明存在亚线性时间算法。在这项工作中，我们深入研究了实现MIS和MM的亚线性时间算法的可能性。
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 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 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 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(n beta(G)) and O(n log{n} * beta(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(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, unit-disk graphs, claw-free graphs, and graphs of bounded growth. Our results suggest that even though MIS and MM do not admit sublinear-time 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.
影响因子：
1.1
作者：
Levi, Reut;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak