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

  • 1
    $\begingroup$ 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 $\endgroup$ – narek Bojikian Jan 1 '20 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 [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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.