改进的预算连接控制和预算边缘 - 顶点控制

作者：Ioannis Lamprou,Ioannis Sigalas,Vassilis Zissimopoulos

摘要：我们考虑经典\ emph {连接支配集}问题（BCDS）的\ emph {budgeted}版本。给定graphGand整数budgetk，我们寻求找到最多关联的连通子集，其最大化G中的支配顶点的数量。我们在[Khuller，Purohit和Sarpatwar，\ \ emph {SODA 2014}]中回答了一个没被解决的问题，因此我们改进了之前的（1-1 / e）/ 13近似。我们的算法通过采用改进的方法来强制连接和执行树分解来提供（1-1 / e）/ 7近似保证。

我们还考虑\ emph {edge-vertex domination}变体，其中边缘支配其端点以及与它们相邻的所有顶点。在\ emph {预算边缘 - 顶点统治}（BEVD）中，我们给出了一个graphG和一个budgetk，并且我们寻求找到一个（不一定是连接的）边的子集，使得格中的支配顶点的数量最大化。我们证明存在（1-1 / e） - 近似算法。此外，对于任何ε> 0，我们通过来自\ emph {最大覆盖率}问题的间隙保持减少来呈现（1-1 / e +ε） - 相似性结果。我们注意到，在连接的情况下，BEVD变得等同于BCDS。此外，我们研究了“双重”'\ emph {部分边缘 - 顶点控制}（PEVD）问题，其中给出了一个图形和一个“指南”。目标是选择一组最小尺寸的边缘来支配至少n个转换。在这种情况下，我们通过减少\ emph {部分覆盖}问题来呈现aH（n'） - 近似算法。

原文标题：Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

原文摘要：We consider the \emph{budgeted} version of the classical \emph{connected dominating set} problem (BCDS). Given a graphGand an integer budgetk, we seek to find a connected subset of at mostkvertices which maximizes the number of dominated vertices inG. We answer an open question in [Khuller, Purohit, and Sarpatwar,\ \emph{SODA 2014}] and thus we improve over the previous(1−1/e)/13approximation. Our algorithm provides a(1−1/e)/7approximation guarantee by employing an improved method for enforcing connectivity and performing tree decompositions.

We also consider the \emph{edge-vertex domination} variant, where an edge dominates its endpoints and all vertices neighboring them. In \emph{budgeted edge-vertex domination} (BEVD), we are given a graphG, and a budgetk, and we seek to find a, not necessarily connected, subset of edges such that the number of dominated vertices inGis maximized. We prove there exists a(1−1/e)-approximation algorithm. Also, for anyϵ>0, we present a(1−1/e+ϵ)-inapproximability result by a gap-preserving reduction from the \emph{maximum coverage} problem. We notice that, in the connected case, BEVD becomes equivalent to BCDS. Moreover, we examine the ``dual'' \emph{partial edge-vertex domination} (PEVD) problem, where a graphGand a quotan′are given. The goal is to select a minimum-size set of edges to dominate at leastn′vertices inG. In this case, we present aH(n′)-approximation algorithm by a reduction to the \emph{partial cover} problem.

地址：https://arxiv.org/abs/1907.06576