论文标题
当最大独立集算法和最大匹配量
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
论文作者
论文摘要
最大独立集（MIS），最大匹配（mm）和$（δ+1）$ - 最大程度$δ$的颜色是最突出的算法图形理论问题之一。它们都可以通过简单的线性时间贪婪算法来解决，直到最近才构成最新的。在2019年的汽水中，Assadi，Chen和Khanna以$（δ+1）$ - 颜色的随机算法给出了$ \ widetilde {o}（n \ sqrt {n}）$ time的颜色，即使对于中等程度的图形，它在输入尺寸中也是浓度的。 Assadi等人的工作。然而，包含MIS和MM的扰流板：这两个问题都不能证明在一般图中接受了均匀的时间算法。在这项工作中，我们更深入地研究了获得MIS和MM的Sublrinear时间算法的可能性。 图$ g $的社区独立数是$β（g）$表示的，是任何顶点附近最大的独立设置的大小。 We identify $β(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β(G))$ and $O(n\log{n}\cdotβ(G))$ time分别在任何$ n $ vertex Graph $ g $上。我们通过观察到Assadi等人的下限的简单扩展来补充这种积极的结果。意味着任何算法都需要$ω（nβ（g））$时间，以解决所有$β（g）$从$ 1 $到$θ（n）$的问题。我们注意到，我们的MIS算法是确定性的，而对于MM，我们使用的随机化是不可避免的：MM的任何确定性算法都需要$ω（n^2）$时间，即使对于$β（g）= 2 $也需要$ω（n^2）$。
Maximal independent set (MIS), maximal matching (MM), and $(Δ+1)$-coloring in graphs of maximum degree $Δ$ 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 $(Δ+1)$-coloring that runs in $\widetilde{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 $β(G)$, is the size of the largest independent set in the neighborhood of any vertex. We identify $β(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β(G))$ and $O(n\log{n}\cdotβ(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 $Ω(nβ(G))$ time is also necessary for any algorithm to either problem for all values of $β(G)$ from $1$ to $Θ(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 $Ω(n^2)$ time even for $β(G) = 2$.
