主导集的最大覆盖范围

Question

主导集合问题是：

给定 $ n $ 顶点图 $ g=（v，e）$ ，找到一个set $ s（\ subseteq v）$ 这样 $ | n [s] | $ 正好<跨越类=“math-container”> $ n $ ，其中 $$ n [s]：={x〜| \ text {$ x $或$ x $的邻居以$ s $} \} $$

我的问题是如果以下（新问题）有一个文学中的一个明确的名称，如果不是应该是最合适的名字。

新问题：给定 $ n $ 顶点图 $ g=（v， e）$ 和一个整数 $ k $ ，找到一个set $ s（\ subseteq v）$ < / span>大小 $ k $ 这样 $ | n [s] | $ 最大化。< / p>

对于第二个问题，我在文献中看到的一些名称是最大图形覆盖范围;部分覆盖; K-Domining-Set，（但是，完全相同的名称也用于其他上下文）。

Answer 1

您必须选择 $ k $ 顶点以最大化主导的顶点的数量被称为预算主导集合问题 。问题或其连接的变体至少由Lamprou，Sigalis和Zissimopoulos [1]和Khuller，Purohit和Sarpatwar [2]研究。它还出现在最近对Narayanaswamy和Vijayaragunathan的调查中[3]。

---

[1] lamprou，ioannis，ioannis sigalas和vassilis zissimopoulos。 “改善了预算的联系统治和预算的边缘统治。” arxiv预印迹arxiv：1907.06576（2019）。

[2] khuller，samir，manish purohit和kanthi k. sarpatwar。 “分析最佳邻域：预算和部分连接的主导集合问题的算法。”第25届年度ACM-SIAM研讨会上的诉讼程序在离散算法上。工业和应用数学协会，2014年。

[3] Narayanaswamy，N. S.和R. Vijayaragunathan。 “在不确定的图表中参数化优化 - 调查和一些结果。”算法13.1（2020）：3。