摘要 Abstract
我们证明了排除$K_{2,t}$为次刻图的图允许一个$f(t)$轮$50$-近似的确定性分布式算法来解决\minDS问题。该结果也适用于\minVC问题。尽管对于排除$H$为次刻图的图,这些问题已经存在快速且近似的分布式算法,但所有这些算法的近似比都依赖于$H$的大小。据我们所知,这是首次出现的大规模非平凡排除次刻图导致的快速且恒定近似的分布式算法,其中近似比独立于$H$的大小。在这些分布式算法的分析中,一个新的关键工具是使用了\textit{渐近维数}。
We show that graphs excluding $K_{2,t}$ as a minor admit a $f(t)$-round $50$-approximation deterministic distributed algorithm for \minDS. The result extends to \minVC. Though fast and approximate distributed algorithms for such problems were already known for $H$-minor-free graphs, all of them have an approximation ratio depending on the size of $H$. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of $H$. A new key ingredient in the analysis of these distributed algorithms is the use of \textit{asymptotic dimension}.