maximum coverage version of dominating set

Question

The dominating set problem is :

Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ lies in $S$}\}$$

My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name.

New Problem: Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(\subseteq V)$ of size $k$ such that $|N[S]|$ is maximized.

For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).

Answer 1

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3].

---

[1] Lamprou, Ioannis, Ioannis Sigalas, and Vassilis Zissimopoulos. "Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination." arXiv preprint arXiv:1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit, and Kanthi K. Sarpatwar. "Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems." Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

[3] Narayanaswamy, N. S., and R. Vijayaragunathan. "Parameterized Optimization in Uncertain Graphs—A Survey and Some Results." Algorithms 13.1 (2020): 3.