作者：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
