论文标题
在电源图上分布近似
Distributed Approximation on Power Graphs
论文作者
论文摘要
我们在以下设置中调查了图问题：我们将获得图形$ g $，并且我们需要在$ g^2 $上解决问题。虽然我们主要关注分布式的交货模型中探索这个主题，但我们展示了与集中计算模型的新结果和令人惊讶的联系。在Escest模型中，自然可以期望由于拥塞而在$ G $上有效地解决$ G^2 $的问题。但是，我们证明了图片既复杂又有趣。 具体来说，我们遇到了两个现象，这些现象在相反的方向上起作用：（i）由于结构属性的$ g^2 $而引起的拥塞和（ii）加速。 我们通过两个基本图问题（即最小顶点覆盖率（MVC）和最小占主导地位（MDS））证明了这两种现象。在我们的许多贡献中，亮点是以下内容。 - 在Conlest型号中，我们显示了$ o（1+ε）$ - $ g^2 $的MVC近似算法的$ O（N/ε）$（1+ε）$（NO $ O（N^2）$ - 圆形算法以$ G $上的MVC的任何更好的MVC近似而闻名。 - 我们在$ g^2 $上显示了一个集中式多项式时间$ 5/3 $ - Approximation算法，而$ G $的UGC-HARD比$ G $更好。 - 相比之下，对于MDS而言，在Escest型号中，我们显示了$ \tildeΩ（n^2）$下限MDS在$ G^2 $上的MDS持续近似系数，而$ω（n^2）$在$ g $上的MDS $ lund Bung on $ g $仅用于精确计算。 除了这些突出显示的结果外，我们还证明了分布的混乱模型中的许多其他结果，包括$ \\tildeΩ（n^2）$下限，以计算$ g^2 $的MVC的精确解决方案，这是获得$（1+ε）$ - $ g^2 $的$ g^2 $ o（$ g^2 $ o（$ g^2 $ o）的条件硬度结果，并获得$ g^2 $（$ o）。在$ \ mbox {poly} \ log n $ rounds中。
We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$. While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on $G^2$ would be quite difficult to solve efficiently on $G$, due to congestion. However, we show that the picture is both more complicated and more interesting. Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of $G^2$. We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following. - In the CONGEST model, we show an $O(n/ε)$-round $(1+ε)$-approximation algorithm for MVC on $G^2$, while no $o(n^2)$-round algorithm is known for any better-than-2 approximation for MVC on $G$. - We show a centralized polynomial time $5/3$-approximation algorithm for MVC on $G^2$, whereas a better-than-2 approximation is UGC-hard for $G$. - In contrast, for MDS, in the CONGEST model, we show an $\tildeΩ(n^2)$ lower bound for a constant approximation factor for MDS on $G^2$, whereas an $Ω(n^2)$ lower bound for MDS on $G$ is known only for exact computation. In addition to these highlighted results, we prove a number of other results in the distributed CONGEST model including an $\tildeΩ(n^2)$ lower bound for computing an exact solution to MVC on $G^2$, a conditional hardness result for obtaining a $(1+ε)$-approximation to MVC on $G^2$, and an $O(\log Δ)$-approximation to the MDS problem on $G^2$ in $\mbox{poly}\log n$ rounds.
