# maximum coverage version of dominating set

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).

• This problem is equivalent to the partial dominating set problem, where you need to find a dominating set that dominates a minimum number of vertices. You can binary search the number of vertices that can be covered by $k$ and solve the partial dominating set for each Jan 1, 2020 at 15:56

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  and Khuller, Purohit and Sarpatwar . It also appears in the recent survey of Narayanaswamy and Vijayaragunathan .